华师一附中OI组

标题: P1219 八皇后 [打印本页]
作者: admin    时间: 2018-5-11 10:51
标题: P1219 八皇后
https://www.luogu.org/problemnew/show/P1219

题目描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。



上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

//以下的话来自usaco官方，不代表洛谷观点

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！

输入输出格式
输入格式：
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出格式：
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例
输入样例#1：
6
输出样例#1：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明
题目翻译来自NOCOW。

USACO Training Section 1.5

作者: 吴语林    时间: 2018-7-30 14:52
采用类似pmn的做法，因为每航只有一个皇后，所以我们设第i行的皇后摆在a(i)位置，那么如何选择a(i)就可以用dfs法，于是得到代码
  1. #include <iostream>
  2. using namespace std;
  3. int s=0,a[10];
  4. bool canp(int i,int k) ///第i行能否放在k位置
  5. {
  6.         bool b=1;
  7.         return 1;  ///这里先不写
  8. }
  9. void pr()
  10. {
  11.         cout<<endl<<++s<<':';
  12.         for (int i=1; i<=8; i++) cout<<a[i]<<' ';
  13. }
  14. void dfs(int i)
  15. {
  16.         if (i>8) pr();
  17.         else
  18.                 for (int k=1; k<=8; k++)
  19.                         if (canp(i,k))
  20.                                 {
  21.                                         a[i]=k;
  22.                                         dfs(i+1);
  23.                                 }
  24. }
  25. int main()
  26. {
  27.         dfs(1);
  28.         return 0;
  29. }
复制代码



中间canp函数用来判断第i行能否放在k位置上，先不写，检测下主函数是否正确，得到好多解，答案有问题但是思路是对的。
现在在canp里面加入一句，判断这一列是否有冲突的语句，这个简单，主要前面i-1行中某一个a(i)==k就表明有冲突
  1. bool canp(int i,int k) ///第i行能否放在k位置
  2. {
  3.         bool b=1;
  4.         for (int j=1; j<=i-1; j++)
  5.                 if (a[j]==k) b=0;
  6.         return b;
  7. }
复制代码


加上后运行，答案少了很多，说明是有效的判断，然后再思考如何加上对角线的限制，看图
javascript:;

我们找到规律 同对角线的i+a(i)的值是一样的，反对角线的i-a(i)的值是一样的，那么再加上这两个判断
  1. bool canp(int i,int k) ///第i行能否放在k位置
  2. {
  3.         bool b=1;
  4.         for (int j=1; j<=i-1; j++)
  5.                 if (a[j]==k) b=0;
  6.         for (int j=1; j<=i-1; j++)
  7.                 if (a[j]+j==k+i) b=0;
  8.         for (int j=1; j<=i-1; j++)
  9.                 if (j-a[j]==i-k) b=0;
  10.         return b;
  11. }
复制代码


程序答案就是92种解
作者: admin    时间: 2020-3-28 19:31
  1. #include <iostream>
  2. using namespace std;
  3. int s=0,a[10];
  4. bool canp(int i,int k) ///第i行能否放在k位置
  5. {
  6.         bool b=1;
  7.         for (int j=1; j<=i-1; j++)
  8.                 if (a[j]==k) b=0;
  9.         for (int j=1; j<=i-1; j++)
  10.                 if (a[j]+j==k+i) b=0;
  11.         for (int j=1; j<=i-1; j++)
  12.                 if (j-a[j]==i-k) b=0;
  13.         return b;
  14. }
  15. void pr()
  16. {
  17.         return ;
  18.         cout<<endl<<++s<<':';
  19.         for (int i=1; i<=8; i++) cout<<a[i]<<' ';
  20. }
  21. void dfs(int i)
  22. {
  23.         if (i>8) pr();
  24.         else
  25.                 for (int k=1; k<=8; k++)
  26.                         if (canp(i,k))
  27.                                 {
  28.                                         a[i]=k;
  29.                                         dfs(i+1);
  30.                                 }
  31. }
  32. int main()
  33. {
  34.         dfs(1);
  35.         return 0;
  36. }
复制代码
作者: admin    时间: 2020-3-28 19:41
  1. 1:1 5 8 6 3 7 2 4
  2. 2:1 6 8 3 7 4 2 5
  3. 3:1 7 4 6 8 2 5 3
  4. 4:1 7 5 8 2 4 6 3
  5. 5:2 4 6 8 3 1 7 5
  6. 6:2 5 7 1 3 8 6 4
  7. 7:2 5 7 4 1 8 6 3
  8. 8:2 6 1 7 4 8 3 5
  9. 9:2 6 8 3 1 4 7 5
  10. 10:2 7 3 6 8 5 1 4
  11. 11:2 7 5 8 1 4 6 3
  12. 12:2 8 6 1 3 5 7 4
  13. 13:3 1 7 5 8 2 4 6
  14. 14:3 5 2 8 1 7 4 6
  15. 15:3 5 2 8 6 4 7 1
  16. 16:3 5 7 1 4 2 8 6
  17. 17:3 5 8 4 1 7 2 6
  18. 18:3 6 2 5 8 1 7 4
  19. 19:3 6 2 7 1 4 8 5
  20. 20:3 6 2 7 5 1 8 4
  21. 21:3 6 4 1 8 5 7 2
  22. 22:3 6 4 2 8 5 7 1
  23. 23:3 6 8 1 4 7 5 2
  24. 24:3 6 8 1 5 7 2 4
  25. 25:3 6 8 2 4 1 7 5
  26. 26:3 7 2 8 5 1 4 6
  27. 27:3 7 2 8 6 4 1 5
  28. 28:3 8 4 7 1 6 2 5
  29. 29:4 1 5 8 2 7 3 6
  30. 30:4 1 5 8 6 3 7 2
  31. 31:4 2 5 8 6 1 3 7
  32. 32:4 2 7 3 6 8 1 5
  33. 33:4 2 7 3 6 8 5 1
  34. 34:4 2 7 5 1 8 6 3
  35. 35:4 2 8 5 7 1 3 6
  36. 36:4 2 8 6 1 3 5 7
  37. 37:4 6 1 5 2 8 3 7
  38. 38:4 6 8 2 7 1 3 5
  39. 39:4 6 8 3 1 7 5 2
  40. 40:4 7 1 8 5 2 6 3
  41. 41:4 7 3 8 2 5 1 6
  42. 42:4 7 5 2 6 1 3 8
  43. 43:4 7 5 3 1 6 8 2
  44. 44:4 8 1 3 6 2 7 5
  45. 45:4 8 1 5 7 2 6 3
  46. 46:4 8 5 3 1 7 2 6
  47. 47:5 1 4 6 8 2 7 3
  48. 48:5 1 8 4 2 7 3 6
  49. 49:5 1 8 6 3 7 2 4
  50. 50:5 2 4 6 8 3 1 7
  51. 51:5 2 4 7 3 8 6 1
  52. 52:5 2 6 1 7 4 8 3
  53. 53:5 2 8 1 4 7 3 6
  54. 54:5 3 1 6 8 2 4 7
  55. 55:5 3 1 7 2 8 6 4
  56. 56:5 3 8 4 7 1 6 2
  57. 57:5 7 1 3 8 6 4 2
  58. 58:5 7 1 4 2 8 6 3
  59. 59:5 7 2 4 8 1 3 6
  60. 60:5 7 2 6 3 1 4 8
  61. 61:5 7 2 6 3 1 8 4
  62. 62:5 7 4 1 3 8 6 2
  63. 63:5 8 4 1 3 6 2 7
  64. 64:5 8 4 1 7 2 6 3
  65. 65:6 1 5 2 8 3 7 4
  66. 66:6 2 7 1 3 5 8 4
  67. 67:6 2 7 1 4 8 5 3
  68. 68:6 3 1 7 5 8 2 4
  69. 69:6 3 1 8 4 2 7 5
  70. 70:6 3 1 8 5 2 4 7
  71. 71:6 3 5 7 1 4 2 8
  72. 72:6 3 5 8 1 4 2 7
  73. 73:6 3 7 2 4 8 1 5
  74. 74:6 3 7 2 8 5 1 4
  75. 75:6 3 7 4 1 8 2 5
  76. 76:6 4 1 5 8 2 7 3
  77. 77:6 4 2 8 5 7 1 3
  78. 78:6 4 7 1 3 5 2 8
  79. 79:6 4 7 1 8 2 5 3
  80. 80:6 8 2 4 1 7 5 3
  81. 81:7 1 3 8 6 4 2 5
  82. 82:7 2 4 1 8 5 3 6
  83. 83:7 2 6 3 1 4 8 5
  84. 84:7 3 1 6 8 5 2 4
  85. 85:7 3 8 2 5 1 6 4
  86. 86:7 4 2 5 8 1 3 6
  87. 87:7 4 2 8 6 1 3 5
  88. 88:7 5 3 1 6 8 2 4
  89. 89:8 2 4 1 7 5 3 6
  90. 90:8 2 5 3 1 7 4 6
  91. 91:8 3 1 6 2 5 7 4
  92. 92:8 4 1 3 6 2 7 5
复制代码
作者: admin    时间: 2020-3-28 19:55
上面用函数canp来判断第i行能否放在k位置上，每次重复判断比较多，能不能像pmn那样用布尔数组来做限制呢?当然可以，但是此题有三个约束条件，所以需要三个布尔数组，假设竖行的用b1(i)，左下到右上对角线的用b2(i)表示，右下到左上对角线的用b3(i)表示，
b1(i)好设置，第i列有皇后了，那么b1(i)=0；以后不能放在第i列
前面分析过左下到右上对角线的规律是i+a(i)相同，假设第i行在k位置了，以后符合i+k相等的都不能放，也就是b2(i+k)=0都不能放。
同样，右下到左上对角线的规律是i-a(i)，这里就有点麻烦了， i-a(i)可能是负数，于是我们加上一个8，变成8+i-a(i)，所以满足b3(i+k)=0都不能放

剩下的就和pmn没有太大的区别，只是这里有3个条件而已，注意不要忘记在主程序里面给3个bool数组附初值。
作者: admin    时间: 2020-3-28 19:55
  1. #include <iostream>
  2. using namespace std;
  3. int s=0,a[10];
  4. bool b1[20],b2[20],b3[20];

  6. void pr()
  7. {
  8.         cout<<endl<<++s<<':';
  9.         for (int i=1; i<=8; i++) cout<<a[i]<<' ';
  10. }
  11. void dfs(int i)
  12. {
  13.         if (i>8) pr();
  14.         else
  15.                 for (int k=1; k<=8; k++)
  16.                         if (b1[k] && b2[k-i+8] && b3[k+i])
  17.                                 {
  18.                                         a[i]=k;
  19.                                         b1[k]=b2[k-i+8]=b3[k+i]=0;/// 后面不能用
  20.                                         dfs(i+1);
  21.                                         b1[k]=b2[k-i+8]=b3[k+i]=1;/// 后面又可以用
  22.                                 }
  23. }
  24. int main()
  25. {
  26.   for (int i=1;i<=19;i++) b1[i]=b2[i]=b3[i]=1;
  27.           dfs(1);
  28.         return 0;
  29. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2