P1219 八皇后

admin

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

吴语林

采用类似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

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

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

上面用函数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

1. #include <iostream>
   
2. using namespace std;
   
3. int s=0,a[10];
   
4. bool b1[20],b2[20],b3[20];
   
5. 
   
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. }

复制代码