传说中的问题。
传说中的算法：回溯法
Python实现：
def place\_queen(l):
if type(l)==list:
tq=l[-1]
k=len(l)
for i,iq in enumerate(l[0:-1],start=1):
if iq==tq or abs(iq-tq)==abs(i-k):
return False
return True
def output\_queens(number,l,n):
print "Solution:%d" % number
for i in range(1,n+1):
for j in range(1,n+1):
if j==l[i-1]:
print "1 ",
else:
print "0 ",
print ''
def n\_queens(l,n):
nCount=0
l.append(0)
while(len(l)):
l[-1]=l[-1]+1
while(l[-1]\<=n and not place\_queen(l)):
l[-1]+=1
if l[-1]\<=n:
if len(l)==n:
nCount+=1
output\_queens(nCount,l,n)
else:
l.append(0)
else:
l.pop()
return nCount
def main():
n=12
l=[]
nCount=n\_queens(l,n)
print "There are %d solutions!" % nCount
if \_\_name\_\_=='\_\_main\_\_':
import time
start=time.clock()
main()
end=time.clock()
print "Run time: %f seconds " % (end-start)
话说第一次感觉Python有点慢了。
当n=8时命令行下需要0.852626s，IDLE运行则需要16.468123s。而当n=12命令行下时需要266.441883s，就不在IDLE下运行了。
而C代码呢。n=8时，0.188s；n=12时，10.674s。
C真的快的如此彪悍。
附C代码：
出处：链接
\#include \
\#include \
\#include \
\#include \
\#define MAXNUMBER 20
//判断当前得到的解向量是否满足问题的解
bool place\_queen(int x[],int k)
{
int i;
for(i=1;i\
{
if((x[i]==x[k]) || (abs(x[i]-x[k])==abs(i-k)))
return false;
}
return true;
}
//将结果简单信息打印到屏幕
void output\_queens(int x[],int n)
{
for(int i=1;i\<=n;i++)
printf("%3d",x[i]);
printf("\\n");
}
//将结果详细信息写入文件
void output\_queens(FILE \*fp,int number,int x[],int n)
{
fprintf(fp,"solution %d: ",number);
for(int i=1;i\<=n;i++)
{
for(int j=1;j\<=n;j++)
{
if(j==x[i])
fprintf(fp,"1 ");
else
fprintf(fp,"0 ");
}
fprintf(fp,"\\n");
}
fprintf(fp,"\\n");
}
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*
\* n后问题求解
\* input : n, the number of queens
\* output : the vector of solution, X
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/
int n\_queens(FILE \*fp,int n,int x[])
{
int nCount=0; //解个数
int k=1; //先处理第1个皇后
x[1]=0;
while(k\>0)
{
x[k]=x[k]+1;//在当前列加1的位置开始搜索
while(x[k]\<=n && !place\_queen(x,k))
//当前列位置是否满足条件
x[k]=x[k]+1; //不满足,继续搜索下一列位置
if(x[k]\<=n) //若存在满足条件的列
{
if(k==n)//是最后一个皇后，则得到一个最终解
{
//break; //此处若break,则只能得到一个解
nCount++;
output\_queens(x,n); //输出
output\_queens(fp,nCount,x,n);
}
else //否则，处理下一个皇后,即第 k+1 个皇后
{
k++;
x[k]=0;
}
}
else //若不存在满足条件的列,则回溯
{
x[k]=0; //第k个皇后复位为0
k--; //回溯到前一个皇后
}
}
return nCount;
}
int main()
{
int n=8,x[MAXNUMBER]={0};
FILE \*fp=fopen("8皇后问题的解.txt","w");
if(fp==NULL)
{
printf("can not wirte file!");
exit(0);
}
printf("the queens are placed on the coloums : ");
//求解并写入文件
int nCount=n\_queens(fp,n,x);
printf("there are %d solutions! ",nCount);
fclose(fp);
return 0;
}
Comments