八皇后问题的实现(从简单到难得各种解法).docx

八皇后问题的实现（C语言） 八皇后问题主要靠回溯的方法实现, 与迷宫的实现相似, 但又困难了一些. 如迷宫的路径不因为上一步而改变, 八皇后的每一步都受约束于以前的步数, 并且, 迷宫只要找出一条路径就行,但八皇后则有很多的解法. 等等.#include #define N 8 / 定义棋盘的格数, 通过改变,也可以是4皇后, 16皇后, 9皇后什么的.int chessNN = 0; / 棋盘int count = 0; / 有多少种放法int canput(int row, int col) / 确定某一格能不能放int i,j;for(i = 0; i N; i +) if(chessicol = 1) /有 同列的 return 0; for(j = 0; j N; j+) if(chessrowj=1) /有同行的 return 0; if(i-row)=(j-col)|(i-row)=(col-j)&chessij=1) / 对角线上有的 return 0; return 1;void print_chess() / 打印放置的方案int i, j;for(i = 0; i N; i+) for(j = 0; j N; j+) printf(%d , chessij); printf(n);printf(n);int put(int row) / 放置棋子, row是从哪一行开始, 通常是0int j, s;for(j = 0; j N; j+) / 此一行的每一个格子都要试试能不能放 if(canput(row, j) / 假如这格能放的话 chessrowj = 1; / 放置 if(row = N-1) / 已经到了最后一行, 那么肯定成功* count = count +1; print_chess(); chessrowj = 0; /成功后, 寻找下一种方法 continue; s = put(row+1); / 放置下一行的 if(s = 0) / 假如下一行不能放 chessrowj = 0; / 那么这格是放错了的, 清除 continue; / 找本行的下一个方格 else break; if(j=N) / 如果这一行的每个空格都不能放置 return 0; / 那么本行放置失败else return 1; / 本行放置成功int main()int s ;s = put(0); / 放置printf(the number of put way is %dn, count); /打印信息return 0; 这个程序有个奇怪的地方, 就是在有星号的那一行, 当把chessrowj = 0, continue;两句去掉时,发现程序依然能正常运行. 原因就是: 当行比列多时, 假如皇后是的数目是列那么多, 是肯定放不成功的, 所以, 当程序要在最后一行的下一行放皇后时,怎么放也不成功,所以, 程序会不断调整以前的方法,但打印信息却在这里执行, 所以能打出正确信息. 但不建议去掉, 因为操作未知内存终究不是件好事.盲目的枚举法#include #include int check(int a,int n)int i,j; for(i=2;i=n;i+) for(j=1;j=i-1;j+) if (ai=aj)|(abs(ai-aj)=abs(i-j) return(0); return(1); void queen1( ) int i;int a9;for(a1=1;a1=8;a1+) for(a2=1;a2=8;a2+) for(a3=1;a3=8;a3+) for(a4=1;a4=8;a4+) for(a5=1;a5=8;a5+) for(a6=1;a6=8;a6+) for(a7=1;a7=8;a7+) for(a8=1;a8=8;a8+) if(check(a,8)=0) continue; else for(i=1;i=8;i+) printf(%d ,ai); printf(n);int main(int argc, char* argv) queen1();return 0;#include #include int check(int a,int n)int i; for(i=1;i=n-1;i+) if (ai=an)|(abs(ai-an)=abs(i-n) return(0); return(1); void queen1( ) int i; int a9; for(a1=1;a1=8;a1+) for(a2=1;a2=8;a2+) if(check(a,2)=0) continue; for(a3=1;a3=8;a3+) if(check(a,3)=0) continue; for(a4=1;a4=8;a4+) if(check(a,4)=0) continue; for(a5=1;a5=8;a5+) if(check(a,5)=0) continue; for(a6=1;a6=8;a6+)if(check(a,6)=0) continue; for(a7=1;a7=8;a7+) if(check(a,7)=0) continue; for(a8=1;a8=8;a8+) if(check(a,8)=0) continue; else for(i=1;i=8;i+) printf(%d ,ai); printf(n); int main(int argc, char* argv) queen1();return 0;加约束的递归#include #include int a9 = 0; int n = 8, count = 0; int check(int a,int n)int i,j; for(i=2;i=n;i+) for(j=1;j n) /kn：即k8表示最后一个皇后摆放完毕 printf(第%d种情况：,+count); for (i = 1; i = n; i+) printf(%d,%d) ,i,ai);/打印情况 printf(n); else /8个皇后未全部摆放完毕 for (i = 1; i = n