此文章转自:
http://bbs./thread-61414-1-1.html (这个排版系统,真垃圾。。。) #if 1 #include <stdio.h> #include <stdlib.h> // Eight Queens Problem : int count; int queen [10], column[20],left[20],right[20]; /* 函数功能:打印出八皇后的结果 */ void prt1() { int j; printf("No.%d ",++count); for (j=1;j<=8;j++) { printf("%3d",queen[j]); } printf("\n"); } /* 函数功能:筛选出符合条件的八皇后的位置 函数入口:第几行 */ void try(int i) { int j; for (j=1;j<=8;j++) { if (column[j] && left[i-j+8] && right[i+j]) { queen[i]=j; column[j]=0; left[i-j+8]=0; right[i+j]=0; if (i<8) { try(i+1); } else { prt1(); } column[j]=left[i-j+8]=right[i+j]=1; } } } int main() { int i; for (i=1;i<=16;i++) { column[i]=left[i]=right[i]=1; } try(1); system("PAUSE"); return 0; } #endif 八皇后:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8*8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。 int count; int queen [10], column[20],left[20],right[20]; /* { int j; printf("No.%d ",++count); for (j=1;j<=8;j++) printf("%3d",queen[j]); printf("\n"); } void try(int i) {int j; for (j=1;j<=8;j++) if (column[j] && left[i-j+8] && right[i+j]) /*如果第i行所对应的列上为1且沿y=x方向线上的为1且沿y=-x方向线上的值为1,则说明这个[i][j]这个坐标是合适的,可以放皇后*/ { queen[i]=j; column[j]=0; /*放上皇后后,对应的列置0,表示这列的位置不能再放皇后*/ left[i-j+8]=0; right[i+j]=0; /*同理,沿y=x方向线和沿y=-x方向线都不能再放皇后*/ if (i<8) try(i+1); /*如果还没执行到第八行,递归继续执行*/ else prt1(); /*如果已经执行到第八行,则可以打印出八皇后的位置结果*/ column[j]=left[i-j+8]=right[i+j]=1; /*还原初始状态,以便使for(j=1;j<=8;j++)这个循环继续有效执行*/ } } main() {int i; for (i=1;i<=16;i++) column[i]=left[i]=right[i]=1; /*设置初始状态*/ count=0; try(1); /*记数置0,进入函数计算*/ } |
|
来自: happy123god > 《算法》