八皇后及N皇后的回溯与递归算法
// 8 queens #include <stdio.h> int position[9]; // 第i个皇后的列号是position[i] (i:1-8) int check(int step){ int i; if(position[step]>8) return 0; for(i=1; i<step; i++){ if (position[i] == position[step] || position[i] - position[step] == i - step || position[i] - position[step] == step - i) { return 0; } } return 1; } int main(){ int step,count,i; count = 0; step = 1; position[1] = 1; while (step>0) { if (check(step)) { if (step == 8) { //输出,回溯到前一个皇后的位置 step-- count++; printf("%d: ",count); for(i=1; i<9; i++) printf("%d ",position[i]); printf("\n"); step--; position[step]++; } else{ //放下一个皇后 step++ step++; position[step]=1; } } else{ //放下一个位置(如果试探完8列,则应该回溯到前一个皇后 step--) if(position[step]>=8) step--; position[step]++; } } return 0; } //递归算法 #include<stdio.h> #include<time.h> typedef int Bool; int a[8][8]={0}; int count=0; Bool Check(int row,int colum) { int i,j; if(row==1) return 1; for(i=0;i<row-1;i++) if(a[i][colum-1]==1) return 0; i=row-2; j=i-(row-colum); while(i>=0&&j>=0) { if(a[i][j]==1) return 0; j--; i--; }//检查左上至右下 i=row-2; j=row+colum-i-2; while(i>=0&&j<=7) { if(a[i][j]==1) return 0; i--; j++; }//检查右上至左下 return 1; } void Output() { int i,j; count++; printf("Answer %d:\n ",count); for(i=0;i<8;i++) { for(j=0;j<8;j++) { printf("%d ",a[i][j]); } printf("\n"); } } void Solve(int row) { int j; for(j=0;j<8;j++) { a[row-1][j]=1; if(Check(row,j+1)==1) { if(row==8) Output(); else Solve(row+1); } a[row-1][j]=0;//回溯 } } int main(void) { clock_t start=clock(); Solve(1); printf("Processor time: %g sec.\n",(clock()-start)/(double)CLOCKS_PER_SEC); return 0; }
N皇后:只需改改参数即可,我们可以看到回溯算法比递归算法要快的多,毕竟回溯省去了重复的一些计算。。。