n皇后问题.doc

一、实验名称:n皇后问题二、实验目的及要求8皇后问题是一个广为人知的问题:将8个皇后放在8×8的棋盘上,皇后之间不能互相攻击,求各种放法。更一般的,把8换成n,其解法个数是随n成几何级增长的,因此程序运行时间也是几何级别的。现在我们关注这样一个问题,既然不能很快的把所有解都枚举出来,那么我们能不能很快的求出一个解来呢?这就是n皇后问题。有人说,我就用纯搜索来搜第一个解,会不会快呢?你可以试一试,当n增大的时候会变的非常非常慢。除了搜索,还能有什么更好的办法呢?下面介绍一个QS2算法,可以在当n大到500000的时候仍能在几分钟之内得到解。三、实验环境C++四、实验内容在一个N*N的棋盘上放置N个皇后,且使得每两个之间不能互相攻击,也就是使得每两个不在同一行,同一列和同一斜角线上。对于N=1,问题的解很简单,而且我们很容易看出对于N=2和N=3来说,这个问题是无解的。所让我们考虑4皇后问题并用回溯法对它求解。因为每个皇后都必须分别占据—行,我们需要做的不过是为图1棋盘上的每个皇后分配一列。我们从空棋盘开始,然后把皇后1放到它所在行的第一个可能位置上,也就是第一行第—列。对于皇后2,在经过第一列和第二列的失败尝试之后,我们把它放在第一个可能的位置,就是格子〔2,3),位于第二行第二列的格子。这被证明是一个死胡同,因为皇后:将没有位置可放。所以,该算法进行回溯,把皇后2放在下一个可能位置(2,4)上。然后皇后3就可以放在(3,2),这被证明是另一个死胡同。该算法然后就回溯到底,把皇后1移到(1,2)。接着皇后2到(2,4),皇后3到(3,1),而皇后4到(4,3),这就是该问题的一个解。图2给出了这个查找的状态空间树。五、算法描述及实验步骤voidQueen(intn);/*n皇后问题*/voidTrySolution(inti,intn,inta[],intb[],intc[],intx[]);/*回溯求解n皇后问题*/voidOutSolution(intn,intx[]);/*输出一组解*/intmain(void)/*主函数main(void)*/{intn=4;Queen(n);/*求解4皇后问题*/system("PAUSE");/*调用库函数system()*/return0;/*返回值0*/}/*n皇后问题*/voidQueen(intn){inta[N+1],b[2*N+1],c[2*N+1];/*a:某一列,b:副对角线,c:主对角线*/inti,x[N+1];/*x:皇后所放置的列*//*赋初值*/for(i=1;i<=n;i++)a[i]=FALSE;for(i=1;i<=2*n;i++)b[i]=FALSE;for(i=1;i<=2*n;i++)c[i]=FALSE;TrySolution(1,n,a,b,c,x);/*递归求解n皇后问题*/}/*前i-1个皇后已放置后,为第i个皇后选择合适的位置,a用于表示某列是否放置有皇后,b表示某条副对角线是否放置有皇后,c表示某条主对角线是否放置有皇后,x表示皇后所放置的列*/voidTrySolution(inti,intn,inta[],intb[],intc[],intx[]){intj;if(i>n){/*/i>n表示第1~n个皇后已放置好*/OutSolution(n,x);/*已得到解,输出解*/}else{for(j=1;j<=n;j++){/*第i个皇后所放置的列*/if(a[j]==FALSE&&b[i+j]==FALSE&&c[i-j+n]==FALSE){/*如果位置(i,j)所在的列,对角线没放置有皇后,则在位置(i,j)放置第i个皇后*/a[j]=TRUE;b[i+j]=TRUE;c[i-j+n]=TRUE;x[i]=j;/*表示第i个皇后所放置的位置*/TrySolution(i+1,n,a,b,c,x);/*再试探第i+1个皇后所放置的位置*///释放位置(i,j),进行回溯a[j]=FALSE;b[i+j]=FALSE;c[i-j+n]=FALSE;}}}}/*输出皇后问题的解*/voidOutSolution(intn,intx[]){um=0;/*num表示当前已求得解的个数*/inti;printf("第%d个解:",++num);for(i=1;i<=n;i++){/*输出解*/printf("(%d,%d)",i,x[i]);}printf("\n");}六、调试过程及实验结果七、总结通观这个算法,发现其实很简单,就是先随机产生了一种排列方案,然后找一个被攻击的皇后,随机选择另一个皇后,让她们交换位置,如果这个交换可以使总的碰撞次数减少,那么就进行交换。由于这个算法是随机的,不能保证从最开始随机产生的queen[i]状态一定