皇后问题(回溯法初学推荐)

水深无声 2023-07-13 15:10 3阅读 0赞

皇后问题

First question:八皇后问题
在棋盘上放置8个皇后,使得它们互不攻击,此时每个皇后的攻击范围为同行同列和同对角线,要求找出所有解,如图所示。
皇后攻击范围
先上代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int tot=0, n, C[5];
  4. void search(int cur)
  5. {
  6. if(cur==n)
  7. {
  8. tot++;
  9. return;
  10. }
  11. //每行每列只有一个皇后
  12. for(int i=0; i<n; i++)
  13. {
  14. int ok=1;
  15. C[cur]=i; //尝试把第cur行的皇后放在第i列 C[y]=x
  16. for(int j=0; j<cur; j++) //检查是否和前面的皇后冲突
  17. { //检查纵向 检查斜向 巧妙
  18. //不用检查横向,因为皇后是逐行放置
  19. if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j])
  20. { //y-x x+y
  21. ok=0;
  22. break;
  23. }
  24. }
  25. if(ok)
  26. search(cur+1); //如果合法,则继续递归
  27. }
  28. }
  29. int main()
  30. {
  31. n=5;
  32. search(0);
  33. cout<<tot<<endl;
  34. return 0;
  35. }

注意:皇后是逐行放置的,皇后肯定不会横向攻击(因为横向不可能有皇后),因此只需检查是否纵向和斜向攻击即可。
条件“cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]”用来判断皇后(cur,C[cur])和(j,C[j])是否在同一条对角线上。
(神秘的操作)其原理可以用下图解释。
原理
(a)格子(x,y)的y-x值标识了主对角线

原理
(b)格子(x,y)的x+y值标识了副对角线
在“八皇后”代码中并没有用到回溯的方法,但是我们可以模仿“八皇后”的代码,写出接下来的这道题——2n皇后问题

Second question:2n皇后问题
问题描述
  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
输入格式
  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
输出格式
  输出一个整数,表示总共有多少种放法。

样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2

我采用的方法是用一个类似棋盘的二维数组qp[10][10]来模拟全局的状态。在棋盘上,任意同色的皇后任都不在同一行、同一列或同一条对角线上。
换句话说,黑白皇后之间没有影响,要考虑2个问题:
1、该位置有没有被占或不能下?
2、会不会与同色皇后冲突?
如果你有做过八皇后的题目,那你可以直接套用在这个2n皇后的题目,只要添加回溯即可。

如何添加回溯?
想象一下,你要下一步棋,现在你有很多个下棋位置可以选择。
第一种情况:你下了几步后发现输了,你想悔棋。于是你就把棋局回到你一开始要下的棋局,选择其他可能赢的下棋位置。
第二种情况:你下了几步后发现赢了,你获胜的可能多了一种,但是你觉得赢的方式有很多种。于是你就把棋局回到你一开始要下的棋局,选择其他可能赢的下棋位置。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long tot=0, n, tot1=0;
  4. int C[10], C1[10], qp[10][10];
  5. void black(int cur)
  6. {
  7. if(cur==n) //放好黑皇后、白皇后
  8. {
  9. tot++;
  10. return;
  11. }
  12. for(int i=0; i<n; i++)
  13. {
  14. int ok=1, j;
  15. C1[cur]=i;
  16. for(j=0; j<cur; j++)
  17. {
  18. if(C1[cur]==C1[j]||cur-C1[cur]==j-C1[j]||cur+C1[cur]==j+C1[j])
  19. {
  20. ok=0;
  21. break;
  22. }
  23. }
  24. if(ok&&qp[cur][i]==1)
  25. {
  26. qp[cur][i]=2;
  27. black(cur+1);
  28. qp[cur][i]=1;
  29. }
  30. }
  31. }
  32. void white(int cur)
  33. {
  34. if(cur==n) //白皇后放置完毕
  35. {
  36. black(0);//开始放黑皇后
  37. for(int i=0; i<n; i++)
  38. cout<<C[i]<<" ";
  39. return;
  40. }
  41. for(int i=0; i<n; i++)
  42. {
  43. int ok=1, j;
  44. C[cur]=i; //尝试把第cur行的皇后放在第i列 (对应讲解图C[y]=x)
  45. for(j=0; j<cur; j++)
  46. {
  47. //不得不说这里的一维数组用得很巧妙,甚至有点神秘
  48. //判断同列有没有同色皇后、斜边有没有同色皇后
  49. //由于该判断有点抽象,具体请看上面原理图
  50. if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j])
  51. {
  52. ok=0;
  53. break;
  54. }
  55. }
  56. if(ok&&qp[cur][i]==1)//判断该位置是否符合条件、是否为空
  57. {
  58. qp[cur][i]=2;
  59. white(cur+1);
  60. qp[cur][i]=1; //回溯:
  61. } //想象一下,你要下一步棋,现在你有很多个选择
  62. } //你下了几步后发现输了,你想悔棋
  63. } //于是你就把棋局回到你一开始要下的棋局
  64. //选择其他可能赢的选择
  65. int main()
  66. {
  67. cin>>n;
  68. for(int i=0; i<n; i++)
  69. for(int j=0; j<n; j++)
  70. cin>>qp[i][j];
  71. white(0); //先放白皇后
  72. cout<<tot<<endl;
  73. return 0;
  74. }

希望能够将自己的一些学习经验分享给有需要的人。
我是小郑,一个坚持不懈的小白。

参考资料:《算法竞赛入门经典》

发表评论

表情:
评论列表 (有 0 条评论,3人围观)

还没有评论,来说两句吧...

相关阅读