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

八皇后问题的实现（C语言） 八皇后问题主要靠回溯的方法实现, 与迷宫的实现相似, 但又困难了一些. 如迷宫的路径不因为上一步而改变, 八皇后的每一步都受约束于以前的步数, 并且, 迷宫只要找出一条路径就行,但八皇后则有很多的解法. 等等.#include stdio.h#define N 8?????????? // 定义棋盘的格数, 通过改变,也可以是4皇后, 16皇后, 9皇后什么的.int chess[N][N] = {0}; // 棋盘int count = 0; // 有多少种放法int canput(int row, int col) // 确定某一格能不能放{int i,j;for(i = 0; i N; i ++){ if(chess[i][col] == 1) //有 同列的 { return 0; } for(j = 0; j N; j++) { if(chess[row][j]==1) //有同行的 { return 0; } if(((i-row)==(j-col)||(i-row)==(col-j))chess[i][j]==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 , chess[i][j]); } printf(\n);}printf(\n);}int put(int row)???? // 放置棋子, row是从哪一行开始, 通常是0{int j, s;for(j = 0; j N; j++) // 此一行的每一个格子都要试试能不能放{ if(canput(row, j)) // 假如这格能放的话 { chess[row][j] = 1; // 放置 if(row == N-1) // 已经到了最后一行, 那么肯定成功****************************************************** { count = count +1; print_chess(); chess[row][j] = 0; //成功后, 寻找下一种方法 continue; } s = put(row+1); // 放置下一行的 if(s == 0)??? // 假如下一行不能放 { chess[row][j] = 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 %d\n, count); //打印信息return 0;} 这个程序有个奇怪的地方, 就是在有星号的那一行, 当把chess[row][j] = 0, continue;两句去掉时,发现程序依然能正常运行. 原因就是: 当行比列多时, 假如皇后是的数目是列那么多, 是肯定放不成功的, 所以, 当程序要在最后一行的下一行放皇后时,怎么放也不成功,所以, 程序会不断调整以前的方法,但打印信息却在这里执行, 所以能打出正确信息. 但不建议去掉, 因为操作未知内存终究不是件好事.盲目的枚举法#include stdio.h#include stdlib.hint check(int a[],int n){int i,j; for(i=2;i=n;i++) for(j=1;j=i-1;j++) if ((a[i]==a[j])||(abs(a[i]-a[j])==abs(i-j))) return(0); return(1);} void queen1( ){ int i;int a[9];for(a[1]=1;a[1]=8;a[1]++) for(a[2]=1;a[2]=8;a[2]++) for(a[3]=1;a[3]=8;a[3]++) for(a[4]=1;a[4]=8;a[4]++) for(a[5]=1;a[5]=8;a[5]++) for(a[6]=1;a[6]=8;a[6]++) for(a[7]=1;a[7]=8;a[7]++) for(a[8]=1;a[8]=8;a[8]++){ if(check(a,8)==0) continue; else for(i=1;i=8;i++) printf(%