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

Hermione

#include <iostream>
using namespace std;

int count;

bool IsDanger(int r, int c, bool (*chess)[8])
{
    bool flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
    int i, j;
    for(i = 0; i < 8; i++)
        if(chess[i][c])
        {
            flag1 = 1;
            break;
        }
    for(i = r, j = c; i >= 0 && j >= 0; i--, j--)
        if(chess[i][j])
        {
            flag2 = 1;
            break;
        }
    for(i = r, j = c; i >= 0 && j < 8; i--, j++)
        if(chess[i][j])
        {
            flag3 = 1;
            break;
        }
    for(i = r, j = c; i < 8 && j >= 0; i++, j--)
        if(chess[i][j])
        {
            flag4 = 1;
            break;
        }
    for(i = r, j = c; i < 8 && j < 8; i++, j++)
        if(chess[i][j])
        {
            flag5 = 1;
            break;
        }
    if(flag1 + flag2 + flag3 + flag4 + flag5 == 0)
        return 0;
    else
        return 1;
}

void EightQueen(int r, bool (*chess)[8])
{
    bool chess2[8][8];
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++)
            chess2[i][j] = chess[i][j];
    if (r == 8)
    {
        cout << "case" << ++count << ":\n";
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            cout << chess2[i][j] << ' ';
            cout << endl;
        }
    }
    else
    {
        for(int j = 0; j < 8; j++)
        {
            if(!IsDanger(r, j, chess2))
            {
                for(int k = 0; k < 8; k++)
                    chess2[r][k] = 0;
                chess2[r][j] = 1;
                EightQueen(r + 1, chess2);
            }
        }
    }
}

int main()
{
    bool chess[8][8] = {0};
    EightQueen(0, chess);

    return 0;
}

很奇怪，第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)函数中的每一判断，随便举个例子

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

这里的

chess[i][j]

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

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)函数中的每一判断，随便举个例子

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

这里的

chess[i][j]

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

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不可能成功？