资源描述:
《八皇后问题详细的解法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1八皇后问题21八皇后问题背景2盲目的枚举算法3加约束的枚举算法4回溯法及基本思想5回溯法应用6八皇后问题的递归回溯算法7八皇后问题的非递归回溯算法3【背景】八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。4八皇后问题要在8*8的国际象棋棋盘中放8个皇后,使任意两个皇后都不能互相吃掉。规则:皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。八皇后的两组解5【问题分析】设八个皇后为xi,分别在第i行(i=1,2,3,4…
2、…,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枚举得有个顺序,否则轻
3、则有漏的、重复的;重则无法循环表示。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(
4、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≠x
5、j+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(che
6、ck(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有“通用的解题法”之称。回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回
7、溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。1回溯法回溯法指导思想——走不通,就掉头。12求问题所有解:要回溯到根,且根结点的所有子树都已被搜索遍才结束。求任一解:只要搜索到问题的一个解就可结束。1回溯法131回溯算法设计过程step1确定问题的解空间;step2确定结点的扩展规则;step3搜索解空间。142回溯法应用-加约束的枚举算法如果能够排除那些没有