首页 > 代码库 > 经典回溯算法——八后问题
经典回溯算法——八后问题
/************************************************************************/ /* 八后问题 */ /************************************************************************/ #include <stdio.h> int count = 0; //判断当前位置是否能放皇后 int IsCorrect(int i, int j, int (*Q)[8]) { int s,t; //判断某一行上是否能放皇后 for(s=i,t=0;t<8;t++) if (Q[s][t]==1 && t!=j) return 0; //判断某一列上是否能放皇后 for(t=j,s=0;s<8;s++) if(Q[s][t]==1 && s!=i) return 0; //判断左上是否能放皇后 for(s=i-1,t=j-1;s>=0&&t>=0;s--,t--) if(Q[s][t]==1) return 0; //判断右下是否能放皇后 for(s=i+1,t=j+1;s<8&&t<8;s++,t++) if(Q[s][t]==1) return 0; //判断右上是否能放皇后 for(s=i-1,t=j+1;s>=0&&t<8;s--,t++) if(Q[s][t]==1) return 0; //判断左下是否能放皇后 for(s=i+1,t=j-1;s<8&&t>=0;s++,t--) if(Q[s][t]==1) return 0; //其它情况 return 1; } //放置皇后 void Queen(int j, int (*Q)[8]) { int i,k; if(j==8) //如果8个皇后全部放置完毕 { for(i=0;i<8;i++) { for(k=0;k<8;k++) printf("%d ",Q[i][k]); printf("\n"); } printf("\n"); count++; return; } for(i=0;i<8;i++) if(IsCorrect(i,j,Q)) { Q[i][j]=1; Queen(j+1,Q); Q[i][j]=0; } } int main() { int Q[8][8]; int i,j; for(i=0;i<8;i++) for(j=0;j<8;j++) Q[i][j]=0; Queen(0,Q); printf("%d\n",count); return 0; }
经典回溯算法——八后问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。