八皇后问题的解决方案.pptx

物电学院物电学院 刘东刘东八皇后问题最优解 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。回溯法概述回溯法概述1 内容提要内容提要八皇后问题八皇后问题2解决八皇后问题常用算法解决八皇后问题常用算法3算法分析与总结算法分析与总结4回溯法概述回溯法概述1在在8*88*8的国际象棋棋盘中放八个皇后，使任意两个的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子同一列、同一对角线的任意棋子。八皇后问题八皇后问题2枚举法解决八皇后问题枚举法解决八皇后问题非递归回溯法解决八皇后问非递归回溯法解决八皇后问题题递归回溯法解决八皇后问题递归回溯法解决八皇后问题3.13.23.3解决八皇后问题常用算法解决八皇后问题常用算法3八皇后问题约束条件八皇后问题约束条件3.01 12 23 34 45 56 67 78 81 12 23 34 45 56 67 78 8a a()()a a()()a a()()a a()()a a()()a a()()a a()()a a()()a(i)a(i)=j =j 第第ii行行j j列放置皇后列放置皇后判断不同列判断不同列判断不同对角线判断不同对角线 a a（ii）a a（j j）0-1-2-3-4-5-6-710-1-2-3-4-5-6210-1-2-3-4-53210-1-2-3-443210-1-2-3543210-1-26543210-176543210 i-a i-a（ii）j-aj-a（j j）判断不同反对角线判断不同反对角线 i+a i+a（ii）j+aj+a（j j）234567893456789 10456789 10 1156789 10 11 126789 10 11 12 13789 10 11 12 13 1489 10 11 12 13 14 159 10 11 12 13 14 15 16a(i)a(i)=j =j 第第ii行行j j列放置皇后列放置皇后判断不同列判断不同列判断不同对角线判断不同对角线 a a（ii）a a（j j）i-a i-a（ii）j-aj-a（j j）判断不同反对角线判断不同反对角线 i+a i+a（ii）j+aj+a（j j）八皇后问题约束条件八皇后问题约束条件3.0 i-a i-a（ii）j-aj-a（j j）i+a i+a（ii）j+aj+a（j j）abs abs（i-ji-j）abs abs（a a（ii）-a-a（j j）枚举法解决八皇后问题枚举法解决八皇后问题3.1 思想：利用思想：利用8 8重循环，分别描述重循环，分别描述8 8个皇后处在各个皇后处在各行的行的8 8个状态，再各个状态中依次找出符合约束条个状态，再各个状态中依次找出符合约束条件的皇后状态件的皇后状态 第第一行一行q(1)q(1)所在列分别依次所在列分别依次1818列列第二行第二行q(2)q(2)所在列分别依次所在列分别依次1818列列第三行第三行q(3)q(3)所在列分别依次所在列分别依次1818列列第四行第四行q(4)q(4)所在列分别依次所在列分别依次1818列列第五行第五行q(5)q(5)所在列分别依次所在列分别依次1818列列第六行第六行q(6)q(6)所在列分别依次所在列分别依次1818列列第七行第七行q(7)q(7)所在列分别依次所在列分别依次1818列列第八行第八行q(8)q(8)所在列分别依次所在列分别依次1818列列判断判断q q是否符合约束条件，满足就打印是否符合约束条件，满足就打印取下一个取下一个q(8)q(8)取下一个取下一个q(7)q(7)取下一个取下一个q(1)q(1)取下一个取下一个 For q1=1 To 8 For q1=1 To 8 For For q2=1 To q2=1 To 8 8 For For q3=1 To 8q3=1 To 8 For For q4=1 To 8q4=1 To 8 For For q5=1 To 8q5=1 To 8 For For q6=1 To 8q6=1 To 8 For For q7=1 To 8q7=1 To 8 For For q8=1 To 8q8=1 To 8 q(q1 q(q1)=q1:q(q2)=q2:q(q3)=q3:q(q4)=q4)=q1:q(q2)=q2:q(q3)=q3:q(q4)=q4 q(q5)=q5:q(q6)=q6:q(q7)=q7:q(q8)=q8q(q5)=q5:q(q6)=q6:q(q7)=q7:q(q8)=q8 If If putdown(qputdown(q)=1)=1 Then Then printstr(q)printstr(q)Next Next q8 q8 Next Next q7 q7 Next Next q6 q6 Next Next q5 q5 Next q4Next q4 Next Next q3 q3 Next Next q2 q2Next Next q1 q1用用语言编程语言编程非递归回溯法解决八皇后问题非递归回溯法解决八皇后问题3.2皇后皇后放置放置行号行号r=1r=1行号行号r0r0列列q(r)8q(r)0 While r 0 While While q(rq(r)8)8 q(rq(r)=qq(r)+1)=qq(r)+1 Dim OK%=1 Dim OK%=1 For j=1 To r-1 For j=1 To r-1 If q(r)=q(j)Or If q(r)=q(j)Or math.abs(math.abs(r r j)=j)=math.abs(math.abs(q(r)-q(j)Thenq(r)-q(j)Then OK=0 OK=0 Exit For Exit For End If End If Next Next If OK=1 Then If OK=1 Then If(r 8)ThenIf(r 8)Then r=r+1 r=r+1 Else Else printstr(qprintstr(q)调用打印输出放置解调用打印输出放置解 End End If If End If End If End While End While qq(r)=0 qq(r)=0 r=r-1 r=r-1 End While End While递归回溯法解决八皇后问题递归回溯法解决八皇后问题3.3调用调用search(1)search(1)行号行号r=r=形参形参ii88r8输出解输出解q(rq(r)=i)=i是是是是是是否否否否返回返回0 0调用调用search(r+1)search(r+1)i=i+1i=i+1否否 Private Private Function Function search(ByVal search(ByVal r As Integer)r As Integer)If If(r 8)Then(r 8)Then printstr(qprintstr(q)Return 0Return 0 End If End If For i=1 To 8 For i=1 To 8 q(r)=i q(r)=i Dim OK%=1 Dim OK%=1 For j=1 To r-1 For j=1 To r-1 If q(r)=q(j)Or Math.Acos(r-j)=Math.Abs(q(r)-q(j)Then If q(r)=q(j)Or Math.Acos(r-j)=Math.Abs(q(r)-q(j)Then OK=0 OK=0 Exit For Exit For End If End If Next Next If OK=1 Then search(r+1)If OK=1 Then search(r+1)Next Next Return 0 Return 0 End Function End Function算法算法总结总结