分类: C/C++
2012-09-21 21:08:21
显然,每一行可以而且必须放一个皇后,所以n皇后问题的解可以用一个n元向量X=(x1,x2,.....xn)表示,其中,1≤ i≤ n且1≤ xi≤ n,即第n个皇后放在第i行第xi列上。
由于两个皇后不能放在同一列上,所以,解向量X必须满足的约束条件为:
xi≠ xj;
若两个皇后的摆放位置分别是(i,xi)和(j,xj),在棋盘上斜率为-1的斜线上,满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上,满足条件i+j=xi+xj;
综合两种情况,由于两个皇后不能位于同一斜线上,所以,
解向量X必须满足的约束条件为:|i-xi|≠ |j-xj|
故实现代码如下
#include
#include
int x[100];
bool place(int k)//考察皇后k放置在x[k]列是否发生冲突
{
int i;
for(i=1;i
if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))
return false;
return true;
}
void queue(int n)
{
int i,k;
for(i=1;i<=n;i++)
x[i]=0;
k=1;
//这里用到了回溯的方法
while(k>=1)
{
x[k]=x[k]+1; //在下一列放置第k个皇后
while(x[k]<=n&&!place(k))
x[k]=x[k]+1;//搜索下一列
if(x[k]<=n&&k==n)//得到一个输出
{
for(i=1;i<=n;i++)
printf("%d ",x[i]);
printf("\n");
//return;//若return则只求出其中一种解,若不return则可以继续回溯,求出全部的可能的解
}
else if(x[k]<=n&&k
k=k+1;//放置下一个皇后
else
{
x[k]=0;//重置x[k],回溯
k=k-1;
}
}
}