8皇后问题——解法.c

8皇后问题——解法.c

8皇后问题

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

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

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

#include #include #include #define line 8#define queennumber 8void 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");}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。