八皇后问题

八皇后问题

在算法课程里面,常用来作为回溯法例子的就是八皇后问题.

回溯法

遇到一个问题,从一个点出发有多重选择、可能性,但在一一尝试前不知道具体哪一个才是最终正确的选择。这个时候,可以挨个尝试,一旦发现不对,则返回到上一个点,进行其他选项,最终找到解决方法或尝试所有可能。

回溯法要满足两个条件:

  • 能够从失败的地方返回上一步
  • 能够尝试所有可能性

八皇后问题

把8个皇后放到棋盘中,使之不会相互攻击。

根据国际象棋规则,皇后可以吃掉放在同行、同列或同一个斜线上的任一个棋子。

算法

先放第1个皇后,然后在下一个位置放第2个皇后,依次类推;一旦发现不能放下一个皇后,则退到上一个皇后,换一个位置继续尝试;直到尝试所有可能。

如果从棋盘的角度思考,一一尝试的方式太慢,改从皇后的角度来思考,以递归的方式减少一个循环。

C++版本实现

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
using namespace std;
class ChessBoard{
public:
ChessBoard();
ChessBoard(int);
void findSolutions();
private:
const bool available;
const int squares,norm;
bool *column, *leftDiagonal, *rightDiagonal;
int *positionInRow, howMany;
void putQueen(int);
void printBoard();
void initialiszeBoard();
};
ChessBoard::ChessBoard():available(true),squares(8),norm(squares-1){
initialiszeBoard();
}
ChessBoard::ChessBoard(int n): available(true),squares(n),norm(squares-1){
initialiszeBoard();
}
void ChessBoard::initialiszeBoard(){
register int i;
column = new bool[squares];
positionInRow = new int[squares];
leftDiagonal = new bool[squares*2-1];
rightDiagonal = new bool[squares*2-1];
for(i = 0; i < squares; i++){
positionInRow[i] = -1;
}
for(i = 0; i < squares; i++){
column[i] = available;
}
for(i = 0; i < squares*2-1; i++){
leftDiagonal[i] = rightDiagonal[i] = available;
}
howMany = 0;
}
void ChessBoard::putQueen(int row){
for(int col = 0; col < squares; col++){
if(column[col] == available &&
leftDiagonal[row+col] == available &&
rightDiagonal[row-col+norm] == available){
positionInRow[row] = col;
column[col] = !available;
leftDiagonal[row+col] = !available;
rightDiagonal[row-col+norm] = !available;
if(row < squares-1){
putQueen(row+1);
} else {
printBoard();
howMany++;
}
column[col] = available;
leftDiagonal[row+col] = available;
rightDiagonal[row-col+norm] = available;
}
}
}
void ChessBoard::printBoard(){
for(int col=0; col < squares; col++){
std::cout << positionInRow[col]+1 << " ";
for(int i = 0; i < positionInRow[col]; i++){
std::cout << ". ";
}
std::cout << "X ";
for(int i = positionInRow[col]+1;i < squares;i++){
std::cout << ". ";
}
std::cout << std::endl;
if((col+1)%squares == 0){
std::cout << std::endl;
}
}
}
void ChessBoard::findSolutions(){
putQueen(0);
cout << howMany << " solutions found.\n";
}
int main(){
int num = atoi(argv[argc-1]);
std::cout << num << " X " << num << " Chess" << std::endl << std::endl;
ChessBoard chess = ChessBoard(num);
chess.findSolutions();
}

结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
4 X 4 Chess
2 . X . .
4 . . . X
1 X . . .
3 . . X .
3 . . X .
1 X . . .
4 . . . X
2 . X . .
2 solutions found.

Python版本实现

Python里面的生成器是逐渐产生结果的复杂递归算法的理想实现工具,这里是使用了递归生成器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def conflict(state,nextX):
nextY = len(state)
for i in range(nextY):
if abs(state[i]-nextX) in (0, nextY-i):
return True
return False
def queens(num=8, state=()):
for pos in range(num):
if not conflict(state,pos):
if len(state) == num-1:
yield (pos,)
else:
for result in queens(num, state + (pos,)):
yield (pos,) + result
print list(queens(4))
print len(list(queens(8)))

结果:

1
2
[(1, 3, 0, 2), (2, 0, 3, 1)]
92

资料

  • 《C++数据结构与算法》
  • 《Python基础教程》
吴羽舒 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!