八皇后问题详细的解法课件.pptVIP

八皇后问题1

1八皇后问题背景nnnnnnn2盲目的枚举算法3加约束的枚举算法4回溯法及基本思想5回溯法应用6八皇后问题的递归回溯算法7八皇后问题的非递归回溯算法2

【背景】八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。3

八皇后问题要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇q后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。八皇后的两组解q4

【问题分析】设八个皇后为x，分别在第i行(i=1，2，3，4……，8)；ni问题的解状态：可以用(1,x)，(2,x)，……，(8,x)表示8个n128皇后的位置；由于行号固定，可简单记为：(x,x,x,x,x,x,x,x)；q12345678问题的解空间：(x,x,x,x,x,x,x,x)，1≤x≤8(i=1，2，3，nn12345678个状态；i4……，8)，共88约束条件：八个(1,x),(2,x),(3,x),(4,x),(5,x),(6,x),123456(7,x),(8,x)不在同一行、同一列和同一对角线上。78原问题即：在解空间中寻找符合约束条件的解状态。按什么顺序去搜？nn目标是没有漏网之鱼，尽量速度快。q5

2【问题设计】盲目的枚举算法a盲目的枚举算法n通过8重循环模拟有哪些信誉好的足球投注网站空间中的88个状态；qq按枚举思想，以DFS的方式，从第1个皇后在第1列开始有哪些信誉好的足球投注网站，枚举出所有的“解状态”：从中找出满足约束条件的“答案状态”。n约束条件？n枚举得有个顺序，否则轻则有漏的、重复的；重则无法循环表示。6

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存在特殊关系，如图：

盲目的枚举算法约束条件？n不在同一列：x≠x；qij不在同一主对角线上：x-i≠x-j；qqij不在同一负对角线上：x+i≠x+j。ij违规的情况可以整合改写为：qnabs(x-x)=abs(i-j))or(x=x)ijij9

双重循环，任意两个皇后之间都必须检查。queen1()盲目的枚举算法check1(a[],n){inti,j;for(i=2;i=n;i++)for(j=1;j=i-1;j++)if(a[i]==a[j])or{用a[1]~a[8]存储x~x18inta[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]++)(abs(a[i]-a[j])==abs(i-j)return(0);return(1);}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]);}10}

1回溯法有“通用的解题法”之称。n回溯法的基本做法是有哪些信誉好的足球投注网站，或是一种组织得井井有条的，能避免不必要有哪些信誉好的足球投注网站的穷举式有哪些信誉好的足球投注网站法。这种方法适用于解一些组合数相当大的问题。n回溯法在问题的解空间树中，按深度优先策略，从根n结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。回溯法指导思想——走不通，就掉头。11

1回溯法求问题所有解：要回溯