[已解决]八皇后问题中有一句我不明白作用

Hermione

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int count;
   
5. 
   
6. bool IsDanger(int r, int c, bool (*chess)[8])
   
7. {
   
8.     bool flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
   
9.     int i, j;
   
10.     for(i = 0; i < 8; i++)
    
11.         if(chess[i][c])
    
12.         {
    
13.             flag1 = 1;
    
14.             break;
    
15.         }
    
16.     for(i = r, j = c; i >= 0 && j >= 0; i--, j--)
    
17.         if(chess[i][j])
    
18.         {
    
19.             flag2 = 1;
    
20.             break;
    
21.         }
    
22.     for(i = r, j = c; i >= 0 && j < 8; i--, j++)
    
23.         if(chess[i][j])
    
24.         {
    
25.             flag3 = 1;
    
26.             break;
    
27.         }
    
28.     for(i = r, j = c; i < 8 && j >= 0; i++, j--)
    
29.         if(chess[i][j])
    
30.         {
    
31.             flag4 = 1;
    
32.             break;
    
33.         }
    
34.     for(i = r, j = c; i < 8 && j < 8; i++, j++)
    
35.         if(chess[i][j])
    
36.         {
    
37.             flag5 = 1;
    
38.             break;
    
39.         }
    
40.     if(flag1 + flag2 + flag3 + flag4 + flag5 == 0)
    
41.         return 0;
    
42.     else
    
43.         return 1;
    
44. }
    
45. 
    
46. void EightQueen(int r, bool (*chess)[8])
    
47. {
    
48.     bool chess2[8][8];
    
49.     for(int i = 0; i < 8; i++)
    
50.         for(int j = 0; j < 8; j++)
    
51.             chess2[i][j] = chess[i][j];
    
52.     if (r == 8)
    
53.     {
    
54.         cout << "case" << ++count << ":\n";
    
55.         for(int i = 0; i < 8; i++)
    
56.         {
    
57.             for(int j = 0; j < 8; j++)
    
58.             cout << chess2[i][j] << ' ';
    
59.             cout << endl;
    
60.         }
    
61.     }
    
62.     else
    
63.     {
    
64.         for(int j = 0; j < 8; j++)
    
65.         {
    
66.             if(!IsDanger(r, j, chess2))
    
67.             {
    
68.                 for(int k = 0; k < 8; k++)
    
69.                     chess2[r][k] = 0;
    
70.                 chess2[r][j] = 1;
    
71.                 EightQueen(r + 1, chess2);
    
72.             }
    
73.         }
    
74.     }
    
75. }
    
76. 
    
77. int main()
    
78. {
    
79.     bool chess[8][8] = {0};
    
80.     EightQueen(0, chess);
    
81. 
    
82.     return 0;
    
83. }

复制代码

很奇怪，第68,69行的for语句为什么不能删去。我想的是，本来棋盘就被初始化为0了，没把那行初始化为0，也可以，因为反正一开始就已经初始化为0了。我一开始没加，然后程序正常执行，但是什么都不输出，找了一个小时才发现是这错了。还是不能理解。
谢谢大家的帮助。

最佳答案

月排行榜 / 总排行榜

tailor_long

2017-12-6 11:41:59

首先，咱们来测试一下如果将68， 69 行的for语句删除，会出现什么问题；
见图一
很明显，出现了不满足8皇后的条件的情况，也就是一行里面出现了多个1，所以到最后没有输出，因为按照你程序的判断方法，没有符合的8皇后
但是为什么会出现这种情况呢？
看你的程序的第48到51行，chess2 = chess1；也就是将当前的棋盘赋值给chess2
然后请看你的程序的66到71行，如果r != 8, 也就是当前棋盘没有判断到最后一行，那么判断当前行是否是dange的也就是
if(!IsDanger(r, j, chess2))
然后咱们再来看看你的IsDanger(r, j, chess2)函数，你分别对行、列、对角进行判断，都没问题，但是有一个地方有一个潜在的问题，那就是在您的IsDanger(r, j, chess2)函数中的每一判断，随便举个例子

1.     for(i = r, j = c; i < 8 && j >= 0; i++, j--)
   
2.         if(chess[i][j])
   
3.         {//判断斜对角有没有重复
   
4.             flag4 = 1;
   
5.             break;
   
6.         }

复制代码

这里的

1. chess[i][j]

复制代码

是什么？是0 还是 1？这里就要看你的递归过程了，也就是第71行
EightQueen(r + 1, chess2);
你递归的是下一行，也就是r+1行，我们都知道初始棋盘全0，所以你的

1. chess[i][j]

复制代码

必然为0，所以你的IsDanger(r, j, chess2)函数判断的是当这个位置是0的时候，这一行有没有危险
如果没有危险的话，如果你将这一行的这个位置直接赋值为1，也就是没有68，69行，就可能会出现危险！所以你要将这一行全部清成0，然后对当前位置给1，这样才能保证当前棋盘没有危险
综上：
不知楼主大人懂了没？

跳转到最佳答案楼层

Hermione

待解决的疑问

tailor_long

首先，咱们来测试一下如果将68， 69 行的for语句删除，会出现什么问题；
见图一
很明显，出现了不满足8皇后的条件的情况，也就是一行里面出现了多个1，所以到最后没有输出，因为按照你程序的判断方法，没有符合的8皇后
但是为什么会出现这种情况呢？
看你的程序的第48到51行，chess2 = chess1；也就是将当前的棋盘赋值给chess2
然后请看你的程序的66到71行，如果r != 8, 也就是当前棋盘没有判断到最后一行，那么判断当前行是否是dange的也就是
if(!IsDanger(r, j, chess2))
然后咱们再来看看你的IsDanger(r, j, chess2)函数，你分别对行、列、对角进行判断，都没问题，但是有一个地方有一个潜在的问题，那就是在您的IsDanger(r, j, chess2)函数中的每一判断，随便举个例子

1.     for(i = r, j = c; i < 8 && j >= 0; i++, j--)
   
2.         if(chess[i][j])
   
3.         {//判断斜对角有没有重复
   
4.             flag4 = 1;
   
5.             break;
   
6.         }

复制代码

这里的

1. chess[i][j]

复制代码

是什么？是0 还是 1？这里就要看你的递归过程了，也就是第71行
EightQueen(r + 1, chess2);
你递归的是下一行，也就是r+1行，我们都知道初始棋盘全0，所以你的

1. chess[i][j]

复制代码

必然为0，所以你的IsDanger(r, j, chess2)函数判断的是当这个位置是0的时候，这一行有没有危险
如果没有危险的话，如果你将这一行的这个位置直接赋值为1，也就是没有68，69行，就可能会出现危险！所以你要将这一行全部清成0，然后对当前位置给1，这样才能保证当前棋盘没有危险
综上：
不知楼主大人懂了没？

Hermione

为加深印象，同时，万一（真的是万一的概率），提醒后来者：
我觉得，这跟数学关系有一点，我来证明一下为什么两句话是必须的，哈哈，居然还用了反证法：

如果没有那两句话，那么chess1[0][0]必然会变成1，而且之后都不会再变，会一直是1,
先证明chess[0][0]是1，不可能有答案，
很简单，chess[1][2]=1,chess[2][4]=1,chess[3][6]=1,然后陷入死路吧。（其实严格来说，这个证明需要用到下一个证明，这算不算递归？）
然后证明，chess1[0][其他]如果还是1，是不会有结果的，哈哈，其实，这个问题概括来说：
就是，如果一行摆放了两个棋子，那么一定不会有满足的答案，证明很简单，因为，8个列必须摆满，但是根据IsDanger的判断，同列不能有同棋子，这样有一行必定为空。
其实，楼上大神说得非常正确，只是再探讨下，补充下。谢谢啦。

Hermione

tailor_long 发表于 2017-12-6 11:41
首先，咱们来测试一下如果将68， 69 行的for语句删除，会出现什么问题；
见图一
很明显，出现了不满足8皇 ...

非常感谢您，两次都耐心回答我的问题，这问题也让我纠结好久了，谢谢您，orz。

tailor_long

Hermione 发表于 2017-12-6 16:35
非常感谢您，两次都耐心回答我的问题，这问题也让我纠结好久了，谢谢您，orz。

不客气啦，交流学习，共同进步！

博伊314

tailor_long 发表于 2017-12-6 11:41
首先，咱们来测试一下如果将68， 69 行的for语句删除，会出现什么问题；
见图一
很明显，出现了不满足8皇 ...

真大神，佩服

吃甲鱼的小乌龟

Hermione 发表于 2017-12-6 16:31
为加深印象，同时，万一（真的是万一的概率），提醒后来者：
我觉得，这跟数学关系有一点，我来证明一下为 ...

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
chess[0][0]为1不可能成功？