八皇后问题详细的解法解读.ppt

* 八皇后问题 * 1八皇后问题背景 2盲目的枚举算法 3加约束的枚举算法 4回溯法及基本思想 5 回溯法应用 6八皇后问题的递归回溯算法 7八皇后问题的非递归回溯算法 * 【背景】 八皇后问题是一个以国际象棋为背景的问题： 如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。 * 八皇后问题 要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。 八皇后的两组解 * 【问题分析】 设八个皇后为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)不在同一行、同一列和同一对角线上。 原问题即：在解空间中寻找符合约束条件的解状态。 按什么顺序去搜？ 目标是没有漏网之鱼，尽量速度快。 * 枚举得有个顺序，否则轻则有漏的、重复的；重则无法循环表示。 2 【问题设计】盲目的枚举算法 a 盲目的枚举算法 通过8重循环模拟有哪些信誉好的足球投注网站空间中的88个状态； 按枚举思想，以DFS的方式，从第1个皇后在第1列开始有哪些信誉好的足球投注网站，枚举出所有的“解状态”： 从中找出满足约束条件的“答案状态”。 约束条件？ 1.按什么顺序去查找所有的解 a.盲目的枚举算法 void main() { int x[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存在特殊关系，如图： * 盲目的枚举算法 约束条件？ 不在同一列：xi≠xj； 不在同一主对角线上：xi-i ≠ xj-j； 不在同一负对角线上：xi+i ≠ xj+j。 违规的情况可以整合改写为： abs(xi - xj)=abs( i-j )) or (xi = xj) * 盲目的枚举算法 queen1( ) { int a[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; else for(i=1;i=8;i++) print(a[i]); } } check1(a[],n) {int i,j; for(i=2;i=n;i++)　 for(j=1;j=i-1;j++