搜索
实用文档文案大全N后问题算法一、实验目的及要求所要涉及或掌握的知识：1.了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2.运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解3.在运用迭代的方法实现编程时，要注意回溯点二、问题描述及实验内容对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。最后程序运行的结果是c[1…6]={1,5,8,6,3,7}三、问题分析和算法描述6-QUEENS的算法表示：输入：空。输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7}1.fork=1to62.c[k]=0//没有放皇后3.endfor4.flag=false5.k=16.whilek=17.whilec[k]=58.c[k]=c[k]+1实用文档文案大全9.ifc为合法着色thensetflag=ture且从两个while循环退出10.elseifc是部分解thenk=k+111.endwhile12.c[k]=0//回溯并c[k]=013.k=k-114.endwhile15.ifflagthenoutputc16.elseoutput“nosolution”四、具体实现#includemath.h#includetime.h#includestdlib.h#includestdio.h#includeiostreamusingnamespacestd;inttotal=0;//方案计数voidbacktrace(intqueen[],intN){inti,j,k;cout★为皇后放置位置\n;for(i=1;;){//首先安放第1行if(queen[i]N){//皇后还可调整k=0;//检查与第k个皇后是否互相攻击while(ki&&abs(queen[k]-queen[i])&&(abs(queen[k]-queen[i])-abs(k-i)))k++;if(k=i-1){//与第k个皇后互相攻击queen[i]++;//第i个皇后右移一列，重测continue;}i++;//无冲突，安置下一行皇后if(iN)continue;cout第total+1种为：\n;实用文档文案大全for(inti=0;iN;i++){for(intj=0;jqueen[i];j++)cout□;cout★;for(intk=queen[i]+1;kN;k++)cout□;coutendl;}total++;//方案数加1if(total%5==0)coutendl;queen[N-1]++;//将第8个皇后右移一列，前8个不动i=N-1;//此处是制造机会，如不成功则回溯，关键一步}else//当前行皇后无法安置，回溯{queen[i]=0;//当前行皇后回归1列i--;//回溯到前一行皇后if(i0){//回溯到数组1行之前，结束cout\n针对N皇后问题，一共找到total种放置方法。endl;coutendl;return;}elsequeen[i]++;//前一行皇后右移一列}}}voidmain(){while(1){clock_tstart,finish;doubleduration;intN;cout请输入皇后个数：endl;cinN;实用文档文案大全int*queen=newint[N];for(inti=0;iN;i++)queen[i]=0;//八皇后全放在第0列intn=N;/*定义数组p[N]用来存放结果序列，n为行号*/start=clock();total=0;backtrace(queen,N);finish=clock();duration=(double)(finish-start);cout为找出放置方法系统共耗时duration/1000秒！\nendl;delete[]queen;}}运行结果：实用文档文案大全回溯法求解八皇后问题2010-10-2918:28:56|分类：算法分析|标签：皇后回溯数组位置八皇后问题|举报|字号订阅问题描述：八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。问题历史：八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。转化规则：其实八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。令一个一位数组a[n]保存所得解，其中a[i]表示把第i个皇后放在第i行的列数（注意i的值都是从0开始计算的），下面就八皇后问题做一个简单的从规则到问题提取过程。（1）因为所有的皇后都不能放在同一列，因此数组的不能存在相同的两个值。实用文档文案大全（2）所有的皇后都不能在对角线上，那么该如何检测两个皇后是否在同一个对角线上？我们将棋盘的方格成一个二维数组，如下：假设有两个皇后被放置在（i，j）和（k，l）的位置上，明显，当且仅当|i-k|=|j-l|时，两个皇后才在同一条对角线上。算法原型：上面我们搞清楚了在解决八皇后问题之前需要处理的两个规则，并将规则转化到了我们数学模型上的问题，那么这段我们开始着手讨论如何设计八皇后的解决算法问题，最常用的就是回溯法，什么是回溯法？回溯法（英语：backtracking）是穷尽搜索算法（英语：Brute-forcesearch）中的一种。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：*找到一个可能存在的正确的答案*在尝试了所有可能的分步方法后宣告该问题没有答案在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。明显，回溯的思想是：假设某一行为当前状态，不断检查该行所有的位置是否能放一个皇后，检索的状态有两种：（1）先从首位开始检查，如果不能放置，接着检查该行第二个位置，依次检查下去，直到在该行找到一个可以放置一个皇后的地方，然后保存当前状态，转到下一行重复上述方法的检索。实用文档文案大全（2）如果检查了该行所有的位置均不能放置一个皇后，说明上一行皇后放置的位置无法让所有的皇后找到自己合适的位置，因此就要回溯到上一行，重新检查该皇后位置后面的位置。是否注意到？如果我们用一个数组来保存当前的状态，上面的检索过程是否有点像堆栈的操作？如果找到可行位置，压栈，如果当前行所有位置不行，将出栈。好了，问题模型逐渐清晰开来了，我们可以定义一个过程，这个过程负责检索的过程，如果检索到当前行某个位置可行，压栈，如果当前行所有位置不行，将执行出栈操作。8皇后问题，我们假定栈的大小为8，如果栈满了，表示找到了可行方法，将执行所有出栈操作。也许有同学会问：如果我找到了一个方法，在进入找下一个可行方法时，该如何做到找出的方法不重复？我们是否需要为每行设定一个状态变量？其实这个问题的处理方法很简单：其实我们在回溯的时候，每个皇后所在位置就是该行的状态变量，回溯转到下一个位置的时候，只需后移1位即可，也就是i++。OK，其实我们可以使用一个数组来模拟栈的结构就可以了，上面解说的时候不用数组而使用栈是因为栈的结构比数组更形象而已。根据上述想法，我们必须定义一个过程，这个过程用来检查当前行的某个位置是否可行，为了方便大家阅读，我采用了常用的算法描述语言SPARKS。SPARKS有个最大的特点就是非常注重算法的思想而不是代码，这样可以更加清晰明了地帮助读者了解作者的算法思想。（1）过程PLACE，检索当前行是否可以放置一个皇后。procedurePLACE(k)//如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。X是一个全程数组，进入此过程时已设置了k个值。ABS(r)过程返回r的绝对值//globalX(1:k);integeri,ki←1whileikdoifX(i)=X(k)orABS(X(i)-X(k))=ABS(i-k)thenreturn(false)endifi←i+1实用文档文案大全repeatreturn(true)endPLACE（2）利用上述的检索过程，通过递归的方式，来确定每个皇后的位置———回溯的思想procedureNQUEENS(n)//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integerk,n,X(1:n)X(1)←0;k←1//k是当前行，X(k)是当前行的位置whilek0doX(k)←X(k)+1//移到下一个位置whileX(k)=nandnotPLACE(k)do//此处能放这个皇后吗？X(k)←X(k)+1repeatifX(k)=n//找到一个位置//thenifk=n//是一个完整的解吗？//thenprint(X)//是，打印数组//elsek←k+1;X(k)←0//转向下一行//endifelsek←k-1//否则，回溯上一行//endifrepeatendNQUEENS实用文档文案大全C语言八皇后问题的实现：#includestdio.h#includestdlib.h#definemax8intqueen[max],sum=0;/*max为棋盘最大坐标*/voidshow()/*输出所有皇后的坐标*/{inti;printf(();for(i=0;imax;i++){printf(%d,queen[i]);}printf()\n);sum++;}intPLACE(intn)/*检查当前列能否放置皇后*/{inti;for(i=0;in;i++)/*检查横排和对角线上是否可以放置皇后*/{if(queen[i]==queen[n]||abs(queen[i]-queen[n])==(n-i)){return1;}}return0;}实用文档文案大全voidNQUEENS(intn)/*回溯尝试皇后位置,n为横坐标*/{inti;for(i=0;imax;i++){queen[n]=i;/*将皇后摆到当前循环到的位置*/if(!PLACE(n)){if(n==max-1){show();/*如果全部摆好，则输出所有皇后的坐标*/}else{NQUEENS(n+1);/*否则继续摆放下一个皇后*/}}}}intmain(){NQUEENS(0);/*从横坐标为0开始依次尝试*/printf(%d,sum);system(pause);return0;}