回溯——八皇后

回溯——八皇后

题意解析

八皇后问题（英文：Eight

queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是==回溯算法==的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

解题思路

二、如何解决八皇后问题？

所谓递归回溯，本质上是一种枚举法。（我们更愿意称之为“有技巧的枚举”）这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。说起来有些抽象，我们来看一看递归回溯的详细过程。

1.第一层递归，尝试在第一行摆放第一个皇后：

img

2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：

img

3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：

img

4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：

img

5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：

img

6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。：

img

7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。：

img

8.继续摆放第五个皇后，以此类推......

代码实现

123456789101112131415161718192021222324#include using namespace std;const int ArSize = 8;//这个数等于几，就是几皇后。int num = 0;void solve(bool arr[ArSize][ArSize], int row);bool check(bool arr[ArSize][ArSize], int row, int column);void outPut(bool arr[ArSize][ArSize]);int main(){ bool chessboard[ArSize][ArSize]; // 数组初始化 for (auto &i : chessboard) { for (auto &j : i) { j = false; } } solve(chessboard, 0); cout << "八皇后问题共有" << num << "种解！" << endl; system("pause"); return 0;}

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677// 回溯法void solve(bool arr[ArSize][ArSize], int row){ for (int column = 0; column < ArSize; ++column) { arr[row][column] = true; //在确定的某一行，遍历每一列放下棋子 if (check(arr, row, column)) //满足条件：1.继续在下一行放下棋子；2.如果是最后一行，输出矩阵 { if (row + 1 == ArSize) { outPut(arr); } else { solve(arr, row + 1); } } arr[row][column] = false; }}// 判断皇后的落点是否合规bool check(bool arr[ArSize][ArSize], int row, int column){ if (row == 0) { return true;//第一行不需要判断 } int i, j; // 判断纵向是否有冲突 for (i = 0; i < row; ++i) { if (arr[i][column]) { return false; } } i = row - 1; j = column - 1; // 判断正斜对角线是否有冲突 while (i >= 0 && j >= 0) { if (arr[i][j]) { return false; } --i; --j; } i = row - 1; j = column + 1; // 判断负斜对角线是否有冲突 while (i >= 0 && j <= ArSize - 1) { if (arr[i][j]) { return false; } --i; ++j; } return true;}// 打印每种正确的解法void outPut(bool arr[ArSize][ArSize]){ ++num; cout << "**********************" << num << "*********************" << endl; for (int i = 0; i < ArSize; ++i) { for (int j = 0; j < ArSize; ++j) { cout << arr[i][j] << " "; } cout << endl; } cout << "*********************************************" << endl;}

参考资料

[1]https://www.cnblogs.com/smile233/p/8483729.html

[2]https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98