Ex5_3.cpp
上传用户:wuzhousb
上传日期:2022-07-12
资源大小:380k
文件大小:2k
源码类别:

书籍源码

开发平台:

Visual C++

  1. //【例5.3】八皇后问题:在8×8的国际象棋棋盘上安放八个皇后,为避免她们之间相互攻击,
  2. //要求没有任何两个皇后在棋盘的同一行、同一列及在同一对角线上。
  3. #include <iostream>
  4. #include <cmath>
  5. using namespace std;
  6. int main(){
  7. int queen[8];
  8. int total = 0;      //方案计数
  9. int i, j, k;
  10. for (i=0;i<8;i++)  queen[i] = 0;           //八皇后全放在第0列
  11. for (i=1;;){                               //首先安放第0行皇后
  12. if(queen[i]<8){                          //皇后还可调整
  13. k=0;                                   //检查与第k个皇后是否互相攻击
  14. while(k<i&&(queen[k]-queen[i])&&(abs(queen[k]-queen[i])-abs(k-i)))  k++;
  15. if (k<=i-1){                           //与第k个皇后互相攻击
  16. queen[i]++;                          //第i个皇后右移一列,重测
  17. continue;
  18. }
  19. i++;                                   //无冲突,安置下一行皇后
  20. if(i<8) continue;
  21. for(j=0;j<8;j++) cout<<queen[j];       //已完成,输出结果
  22. cout<<"  ";
  23. total++;                               //方案数加1
  24. if(total%5==0) cout<<endl;
  25. queen[7]++;                            // 将第7个皇后右移一列,前7个不动
  26. i=7;                           //此处是制造机会,如不成功则回溯,关键一步
  27. }
  28. else                                     //当前行皇后无法安置,回溯
  29. {
  30. queen[i]=0;                            //当前行皇后回归0列
  31. i--;                                   //回溯到前一行皇后
  32. if(i<0){                               //回溯到数组0行之前,结束
  33. cout<<" 总数:"<<total<<endl;
  34. return 0;
  35. }
  36. else queen[i]++;             //前一行皇后右移一列
  37. }
  38. }
  39. }