八皇后问题中有一句我不明白作用
本帖最后由 Hermione 于 2017-12-5 12:20 编辑#include <iostream>
using namespace std;
int count;
bool IsDanger(int r, int c, bool (*chess))
{
bool flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
int i, j;
for(i = 0; i < 8; i++)
if(chess)
{
flag1 = 1;
break;
}
for(i = r, j = c; i >= 0 && j >= 0; i--, j--)
if(chess)
{
flag2 = 1;
break;
}
for(i = r, j = c; i >= 0 && j < 8; i--, j++)
if(chess)
{
flag3 = 1;
break;
}
for(i = r, j = c; i < 8 && j >= 0; i++, j--)
if(chess)
{
flag4 = 1;
break;
}
for(i = r, j = c; i < 8 && j < 8; i++, j++)
if(chess)
{
flag5 = 1;
break;
}
if(flag1 + flag2 + flag3 + flag4 + flag5 == 0)
return 0;
else
return 1;
}
void EightQueen(int r, bool (*chess))
{
bool chess2;
for(int i = 0; i < 8; i++)
for(int j = 0; j < 8; j++)
chess2 = chess;
if (r == 8)
{
cout << "case" << ++count << ":\n";
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
cout << chess2 << ' ';
cout << endl;
}
}
else
{
for(int j = 0; j < 8; j++)
{
if(!IsDanger(r, j, chess2))
{
for(int k = 0; k < 8; k++)
chess2 = 0;
chess2 = 1;
EightQueen(r + 1, chess2);
}
}
}
}
int main()
{
bool chess = {0};
EightQueen(0, chess);
return 0;
}
很奇怪，第68,69行的for语句为什么不能删去。我想的是，本来棋盘就被初始化为0了，没把那行初始化为0，也可以，因为反正一开始就已经初始化为0了。我一开始没加，然后程序正常执行，但是什么都不输出，找了一个小时才发现是这错了。还是不能理解。
谢谢大家的帮助。 本帖最后由 Hermione 于 2017-12-5 12:21 编辑
待解决的疑问 本帖最后由 tailor_long 于 2017-12-6 11:45 编辑
首先，咱们来测试一下如果将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)
{//判断斜对角有没有重复
flag4 = 1;
break;
}
这里的chess是什么？是0 还是 1？这里就要看你的递归过程了，也就是第71行
EightQueen(r + 1, chess2);
你递归的是下一行，也就是r+1行，我们都知道初始棋盘全0，所以你的chess必然为0，所以你的IsDanger(r, j, chess2)函数判断的是当这个位置是0的时候，这一行有没有危险
如果没有危险的话，如果你将这一行的这个位置直接赋值为1，也就是没有68，69行，就可能会出现危险！所以你要将这一行全部清成0，然后对当前位置给1，这样才能保证当前棋盘没有危险
综上：
不知楼主大人懂了没？{:10_297:}
为加深印象，同时，万一（真的是万一的概率），提醒后来者：
我觉得，这跟数学关系有一点，我来证明一下为什么两句话是必须的，哈哈，居然还用了反证法：
如果没有那两句话，那么chess1必然会变成1，而且之后都不会再变，会一直是1,
先证明chess是1，不可能有答案，
很简单，chess=1,chess=1,chess=1,然后陷入死路吧。（其实严格来说，这个证明需要用到下一个证明，这算不算递归{:10_256:}？）
然后证明，chess1[其他]如果还是1，是不会有结果的，哈哈，其实，这个问题概括来说：
就是，如果一行摆放了两个棋子，那么一定不会有满足的答案，证明很简单，因为，8个列必须摆满，但是根据IsDanger的判断，同列不能有同棋子，这样有一行必定为空。
其实，楼上大神说得非常正确，只是再探讨下，补充下。谢谢啦{:10_297:}。 tailor_long 发表于 2017-12-6 11:41
首先，咱们来测试一下如果将68， 69 行的for语句删除，会出现什么问题；
见图一
很明显，出现了不满足8皇 ...
非常感谢您，两次都耐心回答我的问题，这问题也让我纠结好久了，谢谢您，orz。 Hermione 发表于 2017-12-6 16:35
非常感谢您，两次都耐心回答我的问题，这问题也让我纠结好久了，谢谢您，orz。
{:10_297:}
不客气啦，交流学习，共同进步！{:10_256:} 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为1不可能成功？
页:
[1]