语言dijkstra_C语言经典算法05八皇后问题

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

说明&＃xff1a;西洋棋中的皇后可以直线前进&＃xff0c;吃掉遇到的所有棋子&＃xff0c;如果棋盘上有八个皇后&＃xff0c;则这八个皇后如何相安无事的放置在棋盘上&＃xff0c;1970年与1971年&＃xff0c; E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。

解法&＃xff1a;关于棋盘的问题&＃xff0c;都可以用递回求解&＃xff0c;然而如何减少递回的次数&＃xff1f;在八个皇后的问题中&＃xff0c;不必要所有的格子都检查过&＃xff0c;例如若某列检查过&＃xff0c;该该列的其它格子就不用再检查了&＃xff0c;这个方法称为分支修剪。

#include #include #define N 8int column[N&＃43;1]; // 同栏是否有皇后&＃xff0c;1表示有int rup[2*N&＃43;1]; // 右上至左下是否有皇后int lup[2*N&＃43;1]; // 左上至右下是否有皇后int queen[N&＃43;1] &＃61; {0};int num; // 解答编号void backtrack(int); // 递回求解int main(void) {int i;num &＃61; 0;for(i &＃61; 1; i <&＃61; N; i&＃43;&＃43;)column[i] &＃61; 1;for(i &＃61; 1; i <&＃61; 2*N; i&＃43;&＃43;)rup[i] &＃61; lup[i] &＃61; 1;backtrack(1);return 0;}void showAnswer() {int x, y;printf("解答 %d