n皇后非递归求解
#include
#include
using namespace std;
#define N 4
int x[N];
int Place(int k)
{
for(int i=0;iif(x[i]==x[k]||abs(i-k)==abs(x[i]-x[k])) //约束条件不在同一行(那是必然)不在同一列也不再同对角线上
return 1;
else
return 0;
}
}
void queen()
{
for(int i=0;i-1;
}
int k=0,count=0;
while(k>=0)
{
x[k]=x[k]+1;//第一个皇后放了哈,就先给你放在第一个
while(x[k]Place(k)==1)
{
x[k]=x[k]+1;
}//看看违反约束条件没
if(x[k]if(k==N-1)
{
cout<<"plan "<<++count<//到了最后一个皇后了,可以出第一个方案啦
for(int i=0;i1<<" ";
}
cout<else//皇后们别急一个个来
k=k+1;
}
else//倒霉的皇后没找到位置,跟上一个皇后商量一下
{
x[k]=-1;
k=k-1;
}
}
}
int main()
{
queen();
return 0;
}
你要搞n皇后就必然要递归,否则每一个分支你没地方保存啊
要不然你就要自己想办法让皇后能够遍历整个二维数组
//倒霉的皇后没找到位置,跟上一个皇后商量一下
这里出问题了,皇后没找到位置,那么整个分支都要减掉,而不能仅仅退回上一步
比如1,2,3,4,5,6的位置已经决定了不可能有解,但是无论如何7都能放下去,到了8就没地方放了
你老是退回到7,来回改7的位置有什么用呢