N-Queens II 经典问题：8皇后问题 题解

时间：2020-12-13 11:07:51

题目

上一篇我们使用了回溯法，然而提到回溯法就不得不提一个1848年提出的经典题目：8皇后问题，这个问题描述非常简单，一个8*8的棋盘上，放置8个皇后，使得每个皇后都不行相互攻击，既每个皇后的所在行、所在列、所在斜线上都不能有其他皇后，问有多少种解法，题目初看非常像图论问题，实际上也确实是，对图论感兴趣的同学可以去看离散数学的相关内容，这里我们用一种更巧妙也更直观的方法来解决这个问题，那就是——回溯法
在这道经典题目和后面的几篇微博所讨论的题目，我们可以感受到回溯法在解决一些限定某些条件求解（求路径）的问题上是一个多么万能又精巧的的算法
题目:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
N-Queens II 经典问题：8皇后问题 题解
return the total number of distinct solutions.

Difficulty: Hard

分析：

题目没有局限于8皇后而是进行了延伸，扩展到n皇后，实际上原理是一模一样的
初看题目可能没有头绪，想到回溯法却不知道切入点在哪，实际上，对于回溯法问题，无非是给定的“图”和限定条件：
N-Queens II 经典问题：8皇后问题 题解

这里图就是一个n*n的方格，我们先抽象成一个n*n的矩阵，用二维数组代替，皇后可以抽象为矩阵中的元素，用二维数组中的元素代替，不妨设0是没有放皇后，1是放了皇后
限定条件既矩阵中的元素互相不在同一行同一列同一斜线，转化为二维数组后我们发现对于不同行不同列是很好判断的，比如，方格坐标为(i,j)，只要在决定一个方格放不放皇后的时候检查第i行第j列是否有其他皇后就可以，斜线似乎有点棘手，实际上我们抽象出两个皇后就可以看出来解决方案：

N-Queens II 经典问题：8皇后问题 题解

看看这两条线，假设方程分别为： y=kx+b; 其中 A(x1,y1) B(x2,y2) 两点分别是两条线上的点，我么代入原方程然后相减就可以得到： y2−y1=k(x2−x1) 因为是棋盘，这里 k 只有 +1,−1 两个取值，于是我们就可以得到 |y2−y1|=|x2−x1|
最后一个问题就是怎样保存已经放置皇后的位置，最直观的想法就是把二位数组放置皇后的位置置1

方案：

解决了这三个个问题，我们很直观得出解法：

start：
初始化数组
放置皇后{
if(放置位置超出范围){
 求解数自增，返回
 }
else{
for(从第一行开始到最后一行){
if(位置可放皇后) 放置
 递归检查下一个放置皇后位置
 }
 }
}
end

代码

这里我们可以发现，由于规则中同一行只能有一个皇后，所以我们不必要用一个二维数组来模拟棋盘，只要一个一位数组，每个元素代表是否存在皇后就可以完成记录放置点的任务，所以最终的代码如下：

class Solution {
private:
vector<int> queen;
//记录解的个数
int count = 0;
public:
//检查位置是否可放皇后
bool CheckPlace(int Checkline, int Checkrow) {
for (int i = 0; i < Checkline; i++) {
if (queen[i] == Checkrow || abs(Checkline - i) == abs(Checkrow - queen[i])) {
return false;
            }
        }
return true;
    }
//放置皇后
void PlaceQueen(int Checkline, int n) {
if (Checkline == n) {
            count++;
return;
        }
//如果没有完成一个解就继续
else {
for (int i = 0; i < n; i++) {
if (CheckPlace(Checkline, i)) {
                    queen[Checkline] = i;
                    PlaceQueen(Checkline + 1, n);
                }
            }
        }
    }
int totalNQueens(int n) {
        queen.resize(n);
        PlaceQueen(0, n);
return count;
    }
};

通过上面的分析，这个代码是很容易理解的，但是岁回溯法或者对递归不熟悉的同学肯定会有疑问（就是当初的我。。。），代码里只有一个0-n的循环，如何保证求出所有解，没有足够的判断语句又是如何保证不会出现相同的解的呢？
而这实际上就是递归实现回溯法的优点，要想说明这个问题，我们需要看这段代码：

void PlaceQueen(int Checkline, int n) {
if (Checkline == n) {
count++;
return;
    }
//如果没有完成一个解就继续
else {
for (int i = 0; i < n; i++) {
if (CheckPlace(Checkline, i)) {
                queen[Checkline] = i;
                PlaceQueen(Checkline + 1, n);
            }
        }
    }
}

一个重要问题

我们跟着代码走一遍，看看他做了什么，第一个解的求解非常好理解，我们假设第一个解求完，由于每次都是for循环只进行一次就从PlaceQueen(Checkline + 1, n) 进入了下次递归，所以我们已经进入了8次递归嵌套，此时for循环中 依然i==0，然后放置皇后，Checkline==7，代表第8行皇后放置完毕PlaceQueen(Checkline + 1, n) 语句会进入下一次递归，然后Checkline==8 if (Checkline == n) 条件成立，执行return命令，返回到哪里了呢？
返回到了上一层进入点，就是这里：PlaceQueen(Checkline + 1, n) 下面，既这条语句已经执行完，i++，此时继续循环
由于我们每次递归的退出都是确定了8个点的位置，然后改变最后的点，求下个解，这样一步步的回退，保证不会有重复解，而且，一个8次的循环，每次要嵌套8层递归，实际上是做了8^8次探测，保证不会漏解
从上面的分析可以看出来，N皇后的结题时间是指数倍增长，上面的算法，解8皇后不到1ms，解10皇后20ms，12皇后就需要596ms之多

总结

回溯法的递归实现对于解决这样的大规模复杂问题不是最高效的，但往往是最直观也是最容易理解的，毕竟当年数学之王高斯都只算出76中解法的问题我们用回溯法，不用1ms就求出了正确答案
当然，想只凭这一道题就掌握回溯法是不可能的，下面我会写一系列的回溯法题解，只有大量的练习，才是真正理解问题并能够实际解决问题的唯一途径
标签：

相关文章