N + 1皇后算法

我正在尋求提高我的算法的速度來計算N + 1皇后問題的解決方案的數量（位置N+1皇后在NxN與1個棋子棋盤）。我基本上使用蠻力與回溯相結合，我首先將一個棋子放在棋盤上的一個隨機位置（沒有無邊緣的正方形的邊緣和角落），然後我開始使用回溯來放置皇后。這種方法很容易，但也很慢。什麼算法會更快？N + 1皇后算法

我在考慮首先在棋子的每邊放置一個棋子和4個皇后，但我不確定它會提高計算速度。

來源

2013-04-18 user2295594

您是否考慮將其作爲一個約束問題進行表達並使用標準CP求解器來解決它？ –

這是一個比殘酷的力量更需要紙張，筆和邏輯的問題。 – Sulthan

這本身並不是一個好的答案，但對於這個問題，在[wikipedia page]（http://en.wikipedia.org/wiki/Eight_queens_puzzle）上描述了很多優化。 –

當你正在計算所有問題的解決方案，首先將棋子放置在隨機位置不會。您必須將棋子放置在的每個位置。我相信這裏最好的算法是回溯，但仍然可以進行一些優化。在n皇后問題中，重要的一點是利用解的對稱性，所以我想你也可以在這裏做到這一點。有一個解決方案，其所有4個旋轉和他們的鏡像也是解決方案。

來源

2013-04-18 14:55:59

只是想寫同樣的。使用旋轉，他可以立即減少4倍的可能性。 – Sulthan

因子8其實你也可以在對角線上鏡像。 – TemplateRex

好的，我會試試。謝謝。 – user2295594

您自己的建議聽起來是正確的，因爲它始於任何解決方案需要滿足的基本約束，而不是驗證每個候選解決方案的事實之後。

對於窮盡搜索的問題，最大的speedoff通常是當你實現一個早早出局規則：只要一個大號攻擊他人，不要將任何更多的皇后，並進入一個新的正方形最後女王。與詳盡的搜索相比，這將大大減少搜索空間，當您將所有棋子放置在棋盤上時，只檢查相互攻擊。

上NxN板上的棋子位置可以減小到內(N-2)x(N-2)扣板，並且可以使用8倍旋轉/鏡像對稱，以進一步減小該內部正方形的八分圓中的一個。

來源

2013-04-18 14:54:13 TemplateRex

那麼，這基本上是我正在做的回溯.. – user2295594

回答

相關問題