0 前言
还有一年就要毕业了，希望自己每天都能够刷几题，为找工作做好准备。
1 问题介绍
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解
八皇后摆法示例
如上图所示，是八皇后问题的其中几种解法，棋盘中所有皇后都不在同一行同一列同一对角线上，因此符合要求，现在的问题是，设计一种算法，求出所有的符合要求的皇后摆法。
2 解题思路
可以用到递归的思想，我们可以把问题用函数_solve(row)来表示，其中，参数row表示前0~row-1的皇后都满足要求，此时，问题可以拆分成两个
- 放一个皇后在第row行的棋盘，使得他与前面的0~row-1行放的皇后都不冲突
- 递归求解_solve(row+1)
3 代码讲解
主函数
_solve(0);//从第0行开始摆放
用上面的思路暴力求解
// 参数表示第row行前面都已经摆好了
void _solve(int row) {
int i;
for (i=0;i<8;i++) {
board[row][i] = '1';
// 判断当前位置是否可以摆
if (check(row, i)) {
if (row == 7) print();
else _solve(row+1);
}
//同一行下一列进行比较
board[row][i] = '0';
}
判断当前摆放的皇后与前面已经摆好的皇后有无冲突
bool check(int row, int col) {
int i,j;
// 棋子不能在同一列
for (i=0;i<row;i++) {
if (board[i][col] == '1') {
return false;
}
}
// 棋子不能在左上角
i = row-1, j = col-1;
while (i>=0 && j >=0) {
if (board[i][j] == '1') {
return false;
}
i--;
j--;
}
// 棋子不能再右上角
i = row-1, j = col+1;
while (i>=0 && j <8) {
if (board[i][j] == '1') {
return false;
}
i--;
j++;
}
return true;
}
完整代码
namespace alg {
class Queen8 {
private:
// 建立一个8*8棋盘
char board[8][8];
// 记录有多少种摆法
int cnt;
public:
void solve() {
memset(board, '0', sizeof(board));
cnt = 0;
_solve(0);//从第0行开始摆放
}
private:
// 参数表示第row行前面都已经摆好了
void _solve(int row) {
int i;
for (i=0;i<8;i++) {
board[row][i] = '1';
// 判断当前位置是否可以摆
if (check(row, i)) {
if (row == 7) print();
else _solve(row+1);
}
//同一行下一列进行比较
board[row][i] = '0';
}
}
void print() {
printf("chessboard: %d\n",++cnt);
int i,j;
for (i=0;i<8;i++) {
for (j=0;j<8;j++) {
printf("%c ", board[i][j]);
}
printf("\n");
}
}
bool check(int row, int col) {
int i,j;
// 棋子不能在同一列
for (i=0;i<row;i++) {
if (board[i][col] == '1') {
return false;
}
}
// 棋子不能在左上角
i = row-1, j = col-1;
while (i>=0 && j >=0) {
if (board[i][j] == '1') {
return false;
}
i--;
j--;
}
// 棋子不能再右上角
i = row-1, j = col+1;
while (i>=0 && j <8) {
if (board[i][j] == '1') {
return false;
}
i--;
j++;
}
return true;
}
};
}
