这几天刷知乎看到一个帖子如何用 C++ 在 10 行内写出八皇后？，答案内大神云集，用位运算解决的方案令人叹为观止，于是我也复习了一下这个问题，用 java 把主流方案尝试了一遍，收获很大。
N 皇后问题
N 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。这就要求每行，每列，以及每个棋子对角线上只有一个皇后。详情可以参考 leecode-cn n皇后问题
8-queens.png
例如，上图就是8皇后问题的一种解决方案
问题分析
解决8皇后问题的关键点在于：
1. 数据结构：棋子摆放的数据结构如何表示
- 二维数组；
最直观，用二维数组表示棋盘，每个位置用0，1表示是否有棋子；
private Integer[][] chessBoard;
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
这样，判断当前位置是否合法的函数应当为
public boolean isValidPosition(int inputX, int inputY) {
//current row, current column is empty
for (int i = 0; i < DIMENSION; i++) {
if (chessBoard[i][inputX] == 1) {
return false;
}
if (chessBoard[inputY][i] == 1) {
return false;
}
}
// check diagonal
for (int y = 0; y < DIMENSION; y++) {
for (int x = 0; x < DIMENSION; x++) {
// get a chess
if (chessBoard[y][x] == 0) {
continue;
}
// check if chess is on diagonal line;
// y = kx+b; k = 1, -1
if (Math.abs(y - inputY) == Math.abs(x - inputX)) {
return false;
}
}
}
return true;
}
- 一维数组；
仔细观察上面的二维数组，由于每行只有一个棋子，所以每行有大量的剩余空间，因此可以设计一个一维数组表示棋子的摆放位置。一维数组的下标就是行号y，一维数组的值就是x。
例如：上面的这个解
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
可以用一维数组表示为
0 4 7 5 2 6 1 3
private int[] position;
因此，判断当前位置是否合法的函数可以表示为：
public boolean isAvailable(int y) {
for (int i = 0; i < y; i++) {
// delta y = delta x; not same column;
if (Math.abs(y - i) == Math.abs(position[y] - position[i])
|| position[y] == position[i]) {
return false;
}
}
return true;
}
- 比特位表示；
实际上是一维数组的优化版本。最终10行代码解决问题的方案，就采用比特位的数据结构。感兴趣的话可以看一下下面这个版本，本文限于篇幅不再展开。
#include <cstdio>
int queen(int l, int r, int m, int k){
int ans = 0;
for (int i = (~(l | r | m)) & 0xff; i; i -= i & -i)
ans += queen((l | (i & -i)) << 1, (r | (i & -i)) >> 1 , m | (i & -i), k + 1);
return k == 8 ? 1 : ans;
}
int main(){
printf("%d\n", queen(0, 0, 0, 0));
}
作者：Comzyh
链接：https://www.zhihu.com/question/28543312/answer/41233325
来源：知乎
2. 算法：回溯法的实现方案
解决n皇后问题有多种方案，例如全排列暴力破解等；其中最常用的方案是回溯法，深度优先遍历解空间：
- 从上往下逐行遍历棋盘
- 每行逐一试探放置棋子
- 如果当前位置可以摆放棋子（横、竖、对角线都没有冲突），摆放下一行
- 如果当前位置不能放棋，尝试下一个位置
- 直到当前行都没有合适位置，需要回退到上一行，让上一行的棋子移动到下一个位置，继续试探。
- 如果当前行号是最大行号，则问题解决，找到一个n皇后问题的解。
算法实现
回溯法有两种常用的实现方案：
递归回溯
函数递归的方式编码较为容易，利用编程语言的递归方式，自然形成一个调用栈，方便回溯。
Talk is cheap，show me the code
public int getSolutionCount(int currentLayer) {
if (currentLayer == DIMENSION) {
solutionCount++;
} else {
for (int x = 0; x < DIMENSION; x++) {
position[currentLayer] = x;
if (isAvailable(currentLayer)) {
getSolutionCount(currentLayer + 1);
}
}
}
return solutionCount;
}
迭代回溯
由于递归方式依赖编程语言本身的调用栈，在N非常大的场景下存在效率问题，在正常工作中我们都会采用迭代的方式实现相同的逻辑。
如下代码利用 currentLayer 指针自增和自减实现类似的入栈和出栈的逻辑：
public int getSolutionCountIter() {
position[0] = POSITION_NOT_SET;
int currentLayer = 0;
while (currentLayer >= 0) {
position[currentLayer]++;
// find a valid position in current layer
while (position[currentLayer] < DIMENSION && !isAvailable(currentLayer)) {
position[currentLayer]++;
}
// successfully find a position in current layer
if (position[currentLayer] < DIMENSION) {
if (currentLayer == DIMENSION - 1) {
// get a solution.
solutionCount++;
} else {
// continue to check next layer.
currentLayer++;
position[currentLayer] = POSITION_NOT_SET;
}
} else {
// failed to find a position in current layer
// move to upper layer.
currentLayer--;
}
}
return solutionCount;
}
打印结果
如果不是需要获取N皇后解的数量，而是需要输出所有的解，则上述算法在solutionCount++的地方保存position数组即可，这里不再详述。详细代码可以参考github。
总结
N皇后问题的关键是回溯算法,算法可以利用递归实现,也可以利用指针和数组迭代实现。基于比特位表示的算法，复杂度和一维数组是同一个数量级，只是系数更小，相对快一些。从学习的角度，一维数组的算法已经足够了。
GitHub
最后本文完整程序代码的github链接为，欢迎参考：
https://github.com/lixiangthinker/NQueens
网友评论