8皇后问题——解法.c

8皇后问题

• ​​八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。​​

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

可根据更改line、queennumberd的值，任意更改游戏规则

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define line 8
#define queennumber 8

void fun(int i, int j);
bool judge(int i, int j);
void print(void);

int map[line][line];
int ans = 0;
int main(void)
{
fun(0, 0);
system("pause");
return 0;
}
void fun(int i, int j)
{
if (i == line) { //如果下侧越界
return;
}
if (judge(i, j) == true) { //如果能放
map[i][j] = 1; //放皇后
if (j == line - 1) { //如果是最右侧一列，记录情况
ans++;
print();
} else {
fun(0, j + 1); //不是最右一列就分析右一列
}
}
map[i][j] = 0; //如果此位置不能放，就置空（0），判断下列的格子。
//如果此位置能放，走到这里就意味着上面的代码全部执行了，把皇后拿走（置零），再讨论其他情况，拿下列位置试探。
fun(i + 1, j);
}
bool judge(int i, int j)
{
int k;
for (k = 0; k < line; k++) {
if (map[i][k] == 1)
return false; //0=不能放
}
for (k = 0; k < line; k++) {
if (map[k][j] == 1)
return false;
}
for (k = -line; k <= line; k++) { //两对角线
if (i + k >= 0 && i + k < line && j + k >= 0 && j + k < line) //从左上到右下对角线
if (map[i + k][j + k] == 1)
return false;
if (i - k >= 0 && i - k < line && j + k >= 0 && j + k < line) //从左下到右上对角线
if (map[i - k][j + k] == 1)
return false;
}
return true;
}
void print(void)
{
printf("%d.\n\t", ans);
for (int i = 0; i < line; i++) {
for (int j = 0; j < line; j++) {
if (map[i][j] == 0)
printf("* ");
else
printf("0 ");
}
printf("\n\t");
}
printf("\n========================\n\n");
}