暴力嘛，大概还有一个说法就是枚举，穷举的意思了。穷举， 顾名思义为遍历一个集合。这个集合的意义很广， 在解决不同的问题过程中， 这个需要穷举的集合也不尽相同。 比如，我们可以穷举一遍一个给定的整数数组，寻找其中最大的一个； 我们可以穷举问题域，找出满足特定条件的项；等等。
那么，下面我想写一下如何利用穷举去解决比较弱的n（n<8）的皇后问题。
在N X N格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
我们先考虑N = 4的情况，也就是在4*4的棋盘上布局。 由于任意两个皇后不能在同一行出现， 所以每行一定有且仅有一个皇后。我们假设r0, r1, r2, r3分别表示第一，二，三，四行的皇后所在的位置。r0, r1, r2, r3都有可能在第一，二，三，四列，也就是取值可能为0,1,2,3。
主要穷举的代码如下：O（n^4）.....我醉了。。。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33int ValidCount = 0; for(int r0 = 0; r0 < 4; r0++) { for(int r1 = 0; r1 < 4; r1++) { for(int r2 = 0; r2 < 4; r2++) { for(int r3 = 0; r3 < 4; r3++) { bool isValid = true; // 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后 // 2. 验证 任意两个皇后没有处于同一列。 if (r0 == r1 || r0 == r2 || r0 == r3 || r1 == r2 || r1 == r3 || r2 == r3) isValid = false; // 3. 验证 任意两个皇后没有处于同一条斜线上 if ((r0 + 0 == r1 + 1) || (r0 + 0 == r2 + 2) || (r0 + 0 == r3 + 3) || (r1 + 1 == r2 + 2) || (r1 + 1 == r3 + 3) || (r2 + 2 == r3 + 3)) isValid = false; if ((r0 - 0 == r1 - 1) || (r0 - 0 == r2 - 2) || (r0 - 0 == r3 - 3) || (r1 - 1 == r2 - 2) || (r1 - 1 == r3 - 3) || (r2 - 2 == r3 - 3)) isValid = false; // 4. 找到合法的布局 if (isValid) { // 更新合法布局总数 ValidCount++; // 输出布局 for(int i = 0; i < 4; i++) if(r0 == i) printf("Q"); else printf("."); printf("n"); for(int i = 0; i < 4; i++) if(r1 == i) printf("Q"); else printf("."); printf("n"); for(int i = 0; i < 4; i++) if(r2 == i) printf("Q"); else printf("."); printf("n"); for(int i = 0; i < 4; i++) if(r3 == i) printf("Q"); else printf("."); printf("nn"); } } } } } printf("TotalValidCount=%d", ValidCount);
如果N = 8呢？r1, r2, r3, r4, r5, r6, r7, r8？ 写起来有点累了。申请一个数组r[8]吧， 用r[i]表示原来的ri。类似地， 我们很容易写出新穷举的代码：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45int ValidCount = 0; const int N = 8; int r[N]; for(r[0] = 0; r[0] < N; r[0]++) { for(r[1] = 0; r[1] < N; r[1]++) { for(r[2] = 0; r[2] < N; r[2]++) { for(r[3] = 0; r[3] < N; r[3]++) { for(r[4] = 0; r[4] < N; r[4]++) { for(r[5] = 0; r[5] < N; r[5]++) { for(r[6] = 0; r[6] < N; r[6]++) { for(r[7] = 0; r[7] < N; r[7]++) { bool isValid = true; // 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后 // 2. 验证 任意两个皇后没有处于同一列。 for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] == r[j]) isValid = false; // 3. 验证 任意两个皇后没有处于同一条斜线上 for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] + i == r[j] + j) isValid = false; for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] - i == r[j] - j) isValid = false; // 4. 找到合法的布局 if (isValid) { // 更新合法布局总数 ValidCount++; // 输出布局 for (int i = 0; i < N; i++) { for(int j = 0; j < N; j++) if(r[i] == j) printf("Q"); else printf("."); printf("n"); } printf("n"); } } } } } } } } } printf("TotalValidCount=%d", ValidCount);
复制代码
1
2
复制代码
1众所周知，8皇后问题有92个解！！！
复制代码
1
2
复制代码
1再用递归来小优化一下：
复制代码
1
2
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36void search(int* r, int N, int step) { if (step == N) { bool isValid = true; // 1. 验证 任意两个皇后没有处于同一行。 由于我们穷举的时候已经把ri表示为第i行的皇后位置， 保证了每行有且仅有一个皇后 // 2. 验证 任意两个皇后没有处于同一列。 for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] == r[j]) isValid = false; // 3. 验证 任意两个皇后没有处于同一条斜线上 for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] + i == r[j] + j) isValid = false; for (int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if (r[i] - i == r[j] - j) isValid = false; // 4. 找到合法的布局 if (isValid) { // 输出布局 for (int i = 0; i < N; i++) { for(int j = 0; j < N; j++) if(r[i] == j) printf("Q"); else printf("."); printf("n"); } printf("n"); } return; } for(r[step] = 0; r[step] < N; r[step]++) { search(r, N, step + 1); } } int main() { const int N = 8; int r[N]; search(r, N, 0); }
复制代码
1
最后
以上就是醉熏冰淇淋最近收集整理的关于如何暴力解决弱N皇后问题（比较sb的做法）的全部内容，更多相关如何暴力解决弱N皇后问题（比较sb内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复