八皇后问题详细的解法

1八皇后问题21八皇后问题背景2盲目的枚举算法3加约束的枚举算法4回溯法及基本思想5回溯法应用6八皇后问题的递归回溯算法7八皇后问题的非递归回溯算法3【背景】八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。4八皇后问题要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。八皇后的两组解5【问题分析】设八个皇后为xi，分别在第i行(i=1，2，3，4……，8)；问题的解状态：可以用(1,x1)，(2,x2)，……，(8,x8)表示8个皇后的位置；由于行号固定，可简单记为：(x1,x2,x3,x4,x5,x6,x7,x8)；问题的解空间：(x1,x2,x3,x4,x5,x6,x7,x8)，1≤xi≤8(i=1，2，3，4……，8)，共88个状态；约束条件：八个(1,x1),(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一行、同一列和同一对角线上。原问题即：在解空间中寻找符合约束条件的解状态。按什么顺序去搜？目标是没有漏网之鱼，尽量速度快。6枚举得有个顺序，否则轻则有漏的、重复的；重则无法循环表示。2【问题设计】盲目的枚举算法a盲目的枚举算法通过8重循环模拟搜索空间中的88个状态；按枚举思想，以DFS的方式，从第1个皇后在第1列开始搜索，枚举出所有的“解状态”：从中找出满足约束条件的“答案状态”。约束条件？1.按什么顺序去查找所有的解a.盲目的枚举算法voidmain(){intx[100];for(x[1]=1;x[1]=10;x[1]++)for(x[2]=1;x[2]=10;x[2]++)for(x[3]=1;x[3]=10;x[3]++)for(x[4]=1;x[4]=10;x[4]++)for(x[5]=1;x[5]=10;x[5]++)for(x[6]=1;x[6]=10;x[6]++)for(x[7]=1;x[7]=10;x[7]++)for(x[8]=1;x[8]=10;x[8]++)if(check(x)==0){printf(x);}}该如何解决冲突的问题呢？1.行；我们是按照行枚举的，保证了一行一个皇后；2.列：判断是否存在x[i]=x[j]3.对角线：主对角线的i-j与从对角线的i+j存在特殊关系，如图：9盲目的枚举算法约束条件？不在同一列：xi≠xj；不在同一主对角线上：xi-i≠xj-j；不在同一负对角线上：xi+i≠xj+j。违规的情况可以整合改写为：abs(xi-xj)=abs(i-j))or(xi=xj)10盲目的枚举算法queen1(){inta[9];for(a[1]=1;a[1]=8;a[1]++)for(a[2]=1;a[2]=8;a[2]++)for(a[3]=1;a[3]=8;a[3]++)for(a[4]=1;a[4]=8;a[4]++)for(a[5]=1;a[5]=8;a[5]++)for(a[6]=1;a[6]=8;a[6]++)for(a[7]=1;a[7]=8;a[7]++)for(a[8]=1;a[8]=8;a[8]++){if(check(a,8)=0)continue;elsefor(i=1;i=8;i++)print(a[i]);}}check1(a[],n){inti,j;for(i=2;i=n;i++)for(j=1;j=i-1;j++)if(a[i]==a[j])or(abs(a[i]-a[j])==abs(i-j))return(0);return(1);}双重循环，任意两个皇后之间都必须检查。用a[1]~a[8]存储x1~x811有“通用的解题法”之称。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。1回溯法回溯法指导思想——走不通，就掉头。12求问题所有解：要回溯到根，且根结点的所有子树都已被搜索遍才结束。求任一解：只要搜索到问题的一个解就可结束。1回溯法131回溯算法设计过程step1确定问题的解空间；step2确定结点的扩展规则；step3搜索解空间。142回溯法应用-加约束的枚举算法如果能够排除那些没有前途的状态，会节约时间；如何提前发现？回溯法指导思想——走不通，就掉头如(1,1,x3,x4,x5,x6,x7,x8)没有必要再扩展；这种状态扩展后会产生86个结点；同样的(1,2,x3,x4,x5,x6,x7,x8)，…也应被排除。在每一次扩展E结点后，都进行检查；对检查结果如何处理？检查合格的才继续向下扩展；遇到不合格的“掉头就走”。只要当前枚举到的状态可行，就继续枚举下去。当找到一种方案或者无法继续枚举下去时，就退回到上一状态。退回到上一状态的过程叫做回溯，枚举下一个状态的过程叫做递归。回溯就是像人走迷宫一样，先选择一个前进方向尝试，一步步试探，在遇到死胡同不能再往前的时候就会退到上一个分支点，另选一个方向尝试，而在前进和回撤的路上都设置一些标记，以便能够正确返回，直到达到目标或者所有的可行方案都已经尝试完为止。162回溯法应用-例1b加约束的枚举算法●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●我们可以依次确定每一行皇后的位置如果在某一列可以放下一个皇后，我们就在这里放下，并搜索下一行若无法放下皇后则回到上一行，即回溯当n行的皇后都已确定后，我们就找到了一种方案182例1b加约束的枚举算法queen1(){inta[9];for(a[1]=1;a[1]=8;a[1]++)for(a[2]=1;a[2]=8;a[2]++){if(check(a,2)==0)continue;for(a[3]=1;a[3]=8;a[3]++)……{if(check(a,7)==0)continue;for(a[8]=1;a[8]=8;a[8]++){if(check(a,8)==0)continue;elsefor(i=1;i=8;i++)print(a[i]);}}}}}}}}此算法可读性很好，体现了“回溯”。但它只能解决八皇后问题，而不能解决任意的n皇后问题。check2(inta[],intn){//多次被调用，只是一重循环inti;for(i=1;i=n-1;i++)if(abs(a[i]-a[n])==abs(i-n))or(a[i]==a[n])return(0);return(1);}192回溯法应用-算法说明八皇后问题中的核心代码：遍历过程函数；check函数。解决此类问题的核心内容：解空间树的搜索算法；估值/判断函数：判断哪些状态适合继续扩展，或者作为答案状态。202回溯法应用-n皇后问题介绍过的方法：c递归回溯算法；d非递归回溯算法；策略：能进则进，不能进则换，不能换则退。212回溯法应用-算法框架-递归算法框架inta[n];Queens(intk){if(kn)即表示最后一个皇后摆放完毕，输出结果;elsefor(i=下界;i=上界;i++)//枚举K个皇后所有可能的路径{依次从列顶端开始搜索，一直到列底端，直到找到合适位置,如果未找到，自动返回上层递归a[k]=i;if(check(a,k))//满足限界函数和约束条件，不冲突//递归摆放下一个皇后Queens(k+1);}}}22232回溯法应用-算法框架-非递归回溯框架inta[n],i;初始化数组a[]；i=1;While(i0(有路可走))and(未达到目标)//还未回溯到头{if(i=n)搜索到一个解，输出;//搜索到叶结点else//正在处理第i个元素{a[i]第一个可能的值；while(a[i]不满足约束条件且在搜索空间内)a[i]下一个可能的值；if(a[i]在搜索空间内){标识占用的资源;i=i+1;}//扩展下一个结点else{清理所占的状态空间；i=i-1;}//回溯}}