八皇后问题 (Eight queens puzzle)
问题
在 8*8 的国际象棋棋盘上有 8 个皇后，如何摆放使这 8 个皇后互不威胁对方。 换句话说就是，没有任何 2 个皇后在同一行，同一列，同一对角线上
思路
利用回溯法，将行作为深度，列作为 n 叉树的分叉
假设将棋盘分成 8 行，从上到下编号为 8-1
分成 8 列，从左到右编号为 A-H
求解过程如下：
一行一行放，首先保证了皇后放在不同的行
-
是否放满了 8 个皇后，否，继续
在 8-A 放上一个皇后
查看是否可放，可行，继续下一步（深度 + 1）
-
是否放满了 8 个皇后，否，继续
在 7-A 放上一个皇后
查看是否可放，不可行（与 8-A 这个皇后在同一列上），放弃这个子树，继续搜索下一个（列 + 1）
-
是否放满了 8 个皇后，否，继续
在 7-B 放上一个皇后
查看是否可放，不可行（与 8-A 这个皇后在同一列上），放弃这个子树，继续搜索下一个（列 + 1）
-
是否放满了 8 个皇后，否，继续
在 7-C 放上一个皇后
查看是否可放，可行，继续下一步（深度 + 1）
-
是否放满了 8 个皇后，否，继续
在 6-A 放上一个皇后
查看是否可放，不可行（与 8-A 这个皇后在同一列上），放弃这个子树，继续搜索下一个（列 + 1）
-
...
-
是否放满了 8 个皇后，否，继续
在 1-D 放上一个皇后
查看是否可放，可行继续下一步（深度 + 1）
-
是否放满了 8 个皇后，是，输出解，回到上一步（深度 - 1）
-
直到搜索完所有情况
代码
#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define NUM_QUEENS 8
void output(int *queens)
{
for (int i = 0; i < NUM_QUEENS; i++) {
printf("%d ", queens[i]);
}
printf("\n");
}
/*
* 查看是否和 row 以上几行的皇后在同一列或同一对角线
*/
int constraint(int *queens, int row)
{
for (int i = 0; i < row; i++) {
if (queens[row] == queens[i]
|| abs(i - row) == abs(queens[row] - queens[i])) {
return FALSE;
}
}
return TRUE;
}
void eight_queens_puzzle_iter(int *queens, int row)
{
if (row == NUM_QUEENS) {
output(queens);
return;
}
for (int col = 0; col < NUM_QUEENS; col++) {
queens[row] = col;
if (constraint(queens, row) == TRUE) {
eight_queens_puzzle_iter(queens, row + 1);
}
}
}
void eight_queens_puzzle(int *queens)
{
eight_queens_puzzle_iter(queens, 0);
}
int main(int argc, char *argv[])
{
int queens[NUM_QUEENS] = {0};
eight_queens_puzzle(queens);
return 0;
}