• 递归--回溯法--N皇后问题


    完成8皇后问题,若棋盘为5X5

    1. //完成8皇后问题,若棋盘为5X5或9X9结果如何
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. //x,y表示放置皇后的坐标,二维数组attack表示棋盘是否可放置皇后
    7. void put_queen(int x,int y,vectorint> >&attack)
    8. {
    9. //定义方向数组,周围8个方向
    10. static const int dx[]={-1,1,0,0,-1,-1,1,1};
    11. static const int dy[]={0,0,-1,1,-1,1,-1,1};
    12. attack[x][y]=1;//将皇后位置标记为1
    13. //将该皇后可能攻击的位置进行标记
    14. for(int i;isize();i++)
    15. {
    16. for(int j=0;j<8;j++)
    17. //遍历8个方向
    18. {
    19. int nx=x+i*dx[j];
    20. int ny=y+i*dy[j];
    21. //新位置要在棋盘范围内
    22. if(nx>=0&&nxsize()&&ny>=0&&nysize())
    23. {
    24. attack[nx][ny]=1;
    25. }
    26. }
    27. }
    28. }
    29. //回溯法函数,k表示当前的行,n表示n皇后
    30. //queen储存皇后位置,attack标记皇后攻击位置,solve储存全部解法
    31. void backtrack(int k,int n,vector&queen,
    32. vectorint> >&attack,
    33. vector >&solve)
    34. {
    35. if(k==n)//找到一组解
    36. {
    37. solve.push_back(queen);
    38. return;
    39. }
    40. for(int i=0;i
    41. {
    42. if(attack[k][i]==0)
    43. //判断k行i列能否放皇后
    44. {
    45. vectorint> >tmp=attack;
    46. queen[k][i]='Q';
    47. put_queen(k,i,attack);//更新attack数组
    48. backtrack(k+1,n,queen,attack,solve);//递归试探k+1行皇后放置
    49. //如果失败,回溯至此恢复两个数组
    50. attack=tmp;
    51. queen[k][i]='.';
    52. }
    53. }
    54. }
    55. vector >solveNQueen(int n)
    56. {
    57. vector >solve;
    58. vectorint> >attack;
    59. vectorqueen;
    60. //初始化attack和queen
    61. for(int i=0;i
    62. {
    63. attack.push_back((std::vector<int>()));
    64. for(int j=0;j
    65. {
    66. attack[i].push_back(0);
    67. }
    68. queen.push_back("");
    69. queen[i].append(n,'.');
    70. }
    71. backtrack(0,n,queen,attack,solve);
    72. return solve;
    73. }
    74. int main()
    75. {
    76. int n;
    77. cout<<"请输入皇后数:"<
    78. cin>>n;
    79. vector >result;
    80. result=solveNQueen(n);
    81. cout<"皇后有"<size()<<"种解法。"<
    82. for(int i=0;isize();i++)
    83. {
    84. cout<<"解法"<1<<":"<
    85. for(int j=0;jsize();j++)
    86. {
    87. cout<c_str()<
    88. }
    89. cout<
    90. }
    91. return 0;
    92. }

    或9X9结果如何

  • 相关阅读:
    【C进阶】动态内存管理
    枚举类型的使用
    Ef Core实现数据审计与软删除
    2022前端面试题上岸手册-React部分
    自动驾驶学习笔记(三)——场景设计
    python每日学5:python工程(大型项目)的组织架构:包、模块、类、方法
    Ubuntu宝塔显示磁盘被占满的解决方法
    mysql root允许远程连接
    2022.9.20 go语言课程作业
    JS——初始DOM的相关操作练习
  • 原文地址:https://blog.csdn.net/Shenrunchen/article/details/126506620