n皇后问题及深度优先算法

《n皇后问题及深度优先算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、常规N皇后解决问题过程一.问题描述运用回溯法解题通常包含以下三个步骤:(1)针对所给问题，定义问题的解空间;(2)确定易于搜索的解空间结构;(3)以深度优先的力式搜索解空间，并且在搜索过程屮用剪枝函数避免无效搜索;通过上述的基本思路，我们可以将问题描述为：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约朿条件得到能放置一个皇后的约朿条件(l)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)o应用回溯法,当可以放置皇后时就继续到卞一行，不行的话就返回到第一行，重新检验耍放的列数，

2、如此反复，直到将所有解解出。也就是对于NxN的棋盘，选择出N个符合i!=rAj!=sA

3、i-r

4、!=

5、j-s

6、V(i+r)!=(j+s)的点的排列总数。二.伪代码:X[k]=X[k]+l判断点是否符合要求:IfX[k]<=nthenplace(k,X)Sum=Sum+l1=1ElseWhilei0doK=K+1zX[

7、k]=0ElseK=K-1Printsum三・代码实现#includeusingnamespacestd;#include/*检查可不可以放置一个新的皇后*/X[k]=X[k]+lboolplace(intk,int*X)WhileX[k]<=nand!(place(k,x))inti;i=l；while(i

8、

9、(abs(X[i]-X[k])==abs(i-k)))returnfalse;i++；}returntrue;}/*求解问题的所有解的总数，X存放列

10、数*/voidNqueens(intn,int*X){intkzsum=0;X[l]=0;k=l;while(k>0){X[k]=X[k]+l;while((X[k]<=n)&&(!place(k,X)))X[k]=X[k]+l;if(X[k]<=n)if(k==n){for(inti=l;i<=n;i++)cout<

11、<<”请输入皇后的个数:”；cin>>n;X=newint[n];coutvv”问题的解如下:"<

12、图列应该更好解释：程序2思路4、Z1//x/7/Row：00010101Ld:Rd:0011100000001001pos=up_perlim.it&-(rowIIdIrd)/用于判断是否有可放*皇后的位・Row==upperlimit，则总数加1如上图所示，假设一个8*8的棋盘，那么第一次我们在棋盘第一个位置放置一个皇后，则此吋，第二列最靠右可放棋子的位置是3。假设第二个放到第二列3的位置，则此吋，第三列最靠右能放棋子的位置是5…我们用蓝色线代表向右边斜的线，用橙色代表向左边斜的线，用红色代表向下边的线，而同一行，我们不需判断

13、，因为棋子不能放置同一行的位置。这样，我们画了上面的图，所有被红，橙，蓝穿过的格都不能放置皇后。那么从图上，我们很容易的推出第四行第儿个位置能放皇后（从右往左算是2,7,8）。我们用0代表没有被线穿过，用1代表被线穿过，用row代表竖方向，Id代表左斜线，rd代表右斜线。假设每次放皇后我们都先放最靠右边的。则放第一个皇后时:Row=00000001,放置第二个皇后吋：Row=00000101,放置第三个皇后时：Row=00010101,Ld=00000001,Ld=00000110,Ld=00011100,Rd=00001001R

14、d=00000100Rd=00010010按照图，我们可以标识出有没有被线穿过的格子，那么我们要在上面放皇后，当然要放置在没有被线穿过的位置：也就是说Row或者Ld或者Rd上有被线穿过的格子都是不符合要求的，用数学描述为：(row

15、ld

16、rd),因