主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。
如下图所示,八皇后问题的唯一对称解(不包括旋转和反射变换):
2. 计算方法 #
2.1 枚举法 #
八皇后问题如果用穷举法需要尝试88=16,777,216种情况。每一列放一个皇后,可以放在第 1 行,第 2 行,……,直到第8行。穷举的时候从所有皇后都放在第1行的方案开始,检验皇后之间是否会相互攻击。如果会,把列H的皇后挪一格,验证下一个方案。移到底了就“进位”到列G的皇后挪一格,列H的皇后重新试过全部的8行。这种方法是非常低效率的,因为它并不是哪里有冲突就调整哪里,而是盲目地按既定顺序枚举所有的可能方案。
2.2 回溯法 #
其实搜索皇后的位置,可以抽象为一棵树。
下面用一个3 * 3 的棋盘,将搜索过程抽象为一颗树,如图:
用皇后们问题的约束条件,来回溯搜索这颗树,只要搜索到了树的叶子节点,说明就找到了皇后们的合理位置了。
按照之前的模版来进行分析:
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:选择列表)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
递归传递参数
依然是定义全局变量二维数组result来记录最终结果。
参数n是棋盘的大小,然后用row来记录当前遍历到棋盘的第几层了。
vector<vector<string>> result; void backtracking(int n, int row, vector < string>& chessboard) {
递归终止条件
当递归到棋盘最底层(也就是叶子节点)的时候,就可以收集结果并返回了。
代码如下:
if (row == n) { result.push_back(chessboard); return; }
单层循环的逻辑
递归深度就是row控制棋盘的行,每一层里for循环的col控制棋盘的列,一行一列,确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜,所以都是从0开始。
代码如下:
for (int col = 0; col < n; col++) { if (isValid(row, col, chessboard, n)) { // 验证合法就可以放 chessboard[row][col] = 'Q'; // 放置皇后 backtracking(n, row + 1, chessboard); chessboard[row][col] = '.'; // 回溯,撤销皇后 } }
验证放置的皇后是否合法
按照如下标准去重:
1. 不能同行
2. 不能同列
3. 不能同斜线 (45度和135度角)
代码如下:
bool isValid(int row, int col, vector < string > & chessboard, int n) { int count = 0; // 检查列 for (int i = 0; i < row; i++) { // 这是一个剪枝 if (chessboard[i][col] == 'Q') { return false; } } // 检查 45度角是否有皇后 for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) { if (chessboard[i][j] == 'Q') { return false; } } // 检查 135度角是否有皇后 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] == 'Q') { return false; } } return true; }
3. 参考代码 #
按照上面的模版,不难写出如下的代码:
#include < iostream > #include < vector > #include < string > using namespace std; //用'.'表示空白的棋格,用'Q'表示皇后 vector < vector < string > > result; // n 为输入的棋盘大小 // row 是当前递归到棋盘的第几行了 bool isValid(int row, int col, vector < string > & chessboard, int n) { int count = 0; // 检查列 for (int i = 0; i < row; i++) { // 这是一个剪枝 if (chessboard[i][col] == 'Q') { return false; } } // 检查 45度角是否有皇后 for (int i = row - 1, j = col - 1; i > =0 && j >= 0; i--, j--) { if (chessboard[i][j] == 'Q') { return false; } } // 检查 135度角是否有皇后 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] == 'Q') { return false; } } return true; } void backtracking(int n, int row, vector < string > & chessboard) { //注意传递参数的类型 if (row == n) { result.push_back(chessboard); return; } for (int col = 0; col < n; col++) { if (isValid(row, col, chessboard, n)) { // 验证合法就可以放 chessboard[row][col] = 'Q'; // 放置皇后 backtracking(n, row + 1, chessboard); chessboard[row][col] = '.'; // 回溯,撤销皇后 } } } vector < vector < string > > solveNQueens(int n) { result.clear(); vector < string > chessboard(n, string(n, '.')); backtracking(n, 0, chessboard); return result; } int main(){ int n; cin >> n; solveNQueens(n); //输出结果 cout << "共有" << result.size() << "种解法: " << endl; for(int i = 0; i < result.size(); ++i){ for(int j = 0; j < n; ++j){ cout << result[i][j] << endl; } cout << endl; } }