递归回溯解决八皇后问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

介绍

八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。 当且仅当 n = 1n ≥ 4 时问题有解。

如下图,放入第一个皇后之后,绿色的格子就不能放皇后了。

eight-queens

所谓回溯递归其实本质就是枚举,只是加了个试探性。遇到死路,然后原路倒回去一步,看看还有别的出口么。

下面的代码是找出全部的正确摆放方式,从维基百科上我们可以知道八皇后一共有 92 种解。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
bool check(const int k, vector<int> &positions, const int location) {
for (int i = 0; i < k; ++i) {
if (location == positions[i]) {
return false;
}
if (k - i == abs(positions[i] - location)) {
return false;
}
}
return true;
}

void solve(const int k, vector<int> &positions) {
if (k == number) {
++ counter;
cout << "solution " + to_string(counter) << ": ";
for (int i : positions) {
cout << i;
}
cout << endl;
} else {
for (int i = 0; i < number; ++i) {
if (check(k, positions, i)) {
positions[k] = i;
solve(k + 1, positions);
}
}
}
}

void queens(const int n) {
number = n;
positions = vector<int>(n, n);
for (int i = 0; i < n; ++i) {
positions[0] = i;
solve(1, positions);
}
cout << "number of solutions: " << counter << endl;
}

int counter = 0;
int number;
vector<int> positions;
};

int main() {
Solution s;
s.queens(8);
return 0;
}

queens 函数初始化第一个皇后在第一行所在的位置,然后利用当前情况,找下一个皇后的位置。
solve 函数遍历第 k 行,来找出第 k 个皇后在第 k 行的纵坐标。
check 函数来根据当前的摆放信息,来确定第 k 个皇后在哪些纵坐标下可以摆放。

回溯法原理

在所有解的解空间树中,对于某一个节点,先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。