Question

八皇后问题递归算法不理解，求解

#include<iostream>
using namespace std;
const static N=8;
int layout[N];//布局
int cs=0;
int isSafa(int row, int col)//判断能否在（row，col）放下
{
int i;
for(i=0;i<row;i++)
{
if(layout[i]==col)
return 0;//同一列
if(i-layout[i]==row-col)
return 0;//同一条主对角线
if(i+layout[i]==row+col)
return 0;//同一条副对角线
}
return 1;
}
void lay(int row)//在row行上放Queen
{
int i;
if (row==N)//放完N个Queen输出布局
{
// printf("\n");
printf("\n%02d ", ++cs);//cs代表结果数
for(i=0;i<N;i++)
printf("%c%d ",layout[i]+'a',i+1);
}
else
{
for(i=0;i<N;i++)//在i列上放Queen
{
layout[row]=i;
if(isSafa(row,i))
lay(row+1);
}
}
}
void main()
{
lay(0);
printf("\n");
}

代码如上，是正确的，我不能理解
if(isSafa(row,i))
lay(row+1);
这段，八皇后不是存在即使上一个行可以放皇后，下一行就不能发皇后的情况么？谢谢

Answer 1

layout[row] = i; //尝试在此位置上放上八皇后
放上去之后才开始检查是不是合符八皇后的规则，
if(isSafe(row, i)) // 结果为true 意思是在此位置上放八皇后是符合规则的
lay(row+1) //那么OK，我们可以继续放下一层

八皇后是典型的循环里面加递归， 和全排列很类似。在之后你可以看看DFS，深搜就是用这个原理

追问

我想问在lay(row+1)后，在继续放下一层的时候，不是有可能在放row+1行的时候，可能每个位置都放不了情况（那一行都不满足八皇后规则），而需要修改上一行皇后的情况么？还想问一下，怎样才能学好递归，感觉好晕. 。可不可以留下一个方式，方便交流 谢~

追答

刚开始学递归都这样，最好的办法就你亲自跟着程序一步一步去实际模拟一次，你就明白了，单步调试将来会是你最常用的解决疑惑的方式。
你要明白递归嵌套在循环里面的奇妙之处，它是一个树结构， 你可以画个图看看，很快就能理解了。

追问

不是有可能在放row+1行的时候，可能每个位置都放不了情况（那一行都不满足八皇后规则），而需要修改上一行皇后的情况么？

追答

循环已经帮你修改了。举个例子：

for(int i = 1; i < 9; i++)// 这层循环会遍历row行1-8列，

｛
lawyer(i, row);//此时假设i=3时

if(safe(````)) 每个位置放不了， 那么不用管，它上层递归里面的for循环会继续遍历
{
……

}

｝
你自己画个图，或者单步走一遍，问题很简单解决， 递归必须自己去悟，最后给你画个简单的图，在不理解没办法了。我需要找3皇后 ，规则 ：2 ， 3， 1

1 i = 1时， 开始判定递归
1 2 3 这下面仅仅只是i = 1时的递归
1 2 3 1 2 3 1 2 3

2 i = 2时
1 2 3
1 2 3 1 2 3 1 2 3

3
1 2 3
1 2 3 1 2 3 1 2 3