八皇后問題就是在一個8*8的棋盤上任何兩列的行、列、對角線上都不允許有其他元素，問在棋盤上放8個棋子共有多少種放法？

題目不難，想必很多人都有解決思路。但是你的解決思路是最簡的嗎？

假如第一行放一個那么第二行有7種放法，然后第3行又有6種放法，以此類推，共有8！=40320個。

遞歸都會寫，關鍵是判斷條件，如何簡化判斷。

int tot = 0; int c[100]; void search(int cur) {if (cur == n) { tot++; //累積多少種放法for (int i = 0; i < n; i++)cout << c[i] << " ";//輸出可行的排列cout << endl;}else for (int i = 0; i < n; i++) {int ok = 1;c[cur] = i;//將i列賦給cur行for (int j = 0; j < cur; j++) {if (c[cur] == c[j] || cur - c[cur] == j - c[j] || cur + c[cur] == j + c[j]) {//判斷是否有對角線上存在或者行上存在ok = 0; break;}}if (ok)search(cur + 1);//遞歸下一行} }

第12行是判斷是否可行語句，本來我們的判斷可能就是建立一個二維數組找出這個點所在的列是否有其他元素和它兩個對角線上是否有其他元素（方法就是（x--，y--）每次循環判斷是否用過，直到到達邊界）這樣一來又是三個for循環，提高了復雜度。原書作者采用一維數組存放位置信息。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

副對角線

0	1	2	3	4	5	6	7
1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	9
3	4	5	6	7	8	9	10
4	5	6	7	8	9	10	11
5	6	7	8	9	10	11	12
6	7	8	9	10	11	12	13
7	8	9	10	11	12	13	14

主對角線

0	1	2	3	4	5	6	7
-1	0	1	2	3	4	5	6
-2	-1	0	1	2	3	4	5
-3	-2	-1	0	1	2	3	4
-4	-3	-2	-1	0	1	2	3
-5	-4	-3	-2	-1	0	1	2
-6	-5	-4	-3	-2	-1	0	1
-7	-6	-5	-4	-3	-2	-1	0

?

?

?

?

?

?

?

?

?

其中c[cur]==c[j]就是搜索前面的行有沒有用過這一列（cur表示行，c[cur]表示這一行的列元素）；cur-c[cur]就是主對角線上的值相等。所以只需要判斷cur-c[cur]==j-c[j]（j-c[j]表示前面的元素如果c[j]用過的話，那么它所在的對角線就符合上面的主對角線上的值。）同理，副對角線只需要將j+c[j]即可，同樣判斷是否符合條件。

改進版：

其中遞歸已經是最簡了，那么我們想是否可以簡化判斷呢？

將判斷的for循環去掉，怎么去？上面對角線上的元素是相等的，那么就可以想到將對角線映射到一個一維數組里，比如第一個就是-7，-6，-5，-4，-3，-2，-1，0，1，2，3，4，5，6，7，每次只需要判斷當前點所在的對角線的一維數組下標是否等于1。一共需要3個判斷-兩個對角線，一個列。所以使用三個數組存放。

int vis[3][1000]; int n; int tot = 0; int c[100]; void search(int cur) {if (cur == n) { tot++; for (int i = 0; i < n; i++)cout << c[i] << " ";//輸出可行的排列cout << endl;}else for (int i = 0; i < n; i++) {if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]) { //cur-i+n之所以要加n，是因為下標可能為負c[cur] = i;vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;//將這個點的列全置為1，對角線置為1search(cur + 1);//搜索下一層vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;//循環搜索第二種情況時需要將列和對角線清除}} }

數學方法簡單的解決了8皇后問題，主要就是簡化判斷。

?

總結

以上是生活随笔為你收集整理的回溯法之八皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。