八皇后问题的解决方案

物电学院刘东八皇后问题最优解八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。回溯法概述1

内容提要八皇后问题2解决八皇后问题常用算法3算法分析与总结4回溯法概述1在8*8的国际象棋棋盘中放八个皇后，使随意两个皇后都不能相互吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的随意棋子。八皇后问题2枚举法解决八皇后问题非递归回溯法解决八皇后问题递归回溯法解决八皇后问题解决八皇后问题常用算法3八皇后问题约束条件3.01234567812345678a()a()a()a()a()a()a()a()a(i)=j第i行j列放置皇后推断不同列推断不同对角线a（i）≠a（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-176543210i-a（i）≠j-a（j）推断不同反对角线i+a（i）≠j+a（j）23456789345678910456789101156789101112678910111213789101112131489101112131415910111213141516a(i)=j第i行j列放置皇后推断不同列推断不同对角线a（i）≠a（j）i-a（i）≠j-a（j）推断不同反对角线i+a（i）≠j+a（j）八皇后问题约束条件3.0i-a（i）≠j-a（j）i+a（i）≠j+a（j）abs（i-j）≠abs（a（i）-a（j））枚举法解决八皇后问题3.1思想：利用8重循环，分别描述8个皇后处在各行的8个状态，再各个状态中依次找出符合约束条件的皇后状态。第一行q(1)所在列分别依次1~8列第二行q(2)所在列分别依次1~8列第三行q(3)所在列分别依次1~8列第四行q(4)所在列分别依次1~8列第五行q(5)所在列分别依次1~8列第六行q(6)所在列分别依次1~8列第七行q(7)所在列分别依次1~8列第八行q(8)所在列分别依次1~8列判断q是否符合约束条件，满足就打印取下一个q(8)取下一个q(7)取下一个q(1)取下一个………………Forq1=1To8

Forq2=1To8

Forq3=1To8

Forq4=1To8

Forq5=1To8

Forq6=1To8

Forq7=1To8

Forq8=1To8

q(q1)=q1:q(q2)=q2:q(q3)=q3:q(q4)=q4

q(q5)=q5:q(q6)=q6:q(q7)=q7:q(q8)=q8

Ifputdown(q)=1Thenprintstr(q)

Nextq8

Nextq7

Nextq6

Nextq5

Nextq4Nextq3Nextq2Nextq1用语言编程非递归回溯法解决八皇后问题3.2皇后放置行号r=1行号r>0列q(r)<8q(r)列符合放置条件r≥8输出解r=r+1q(r)=q(r)+1是是是否否否r=r-1q(r)=0否退出是

Dimr=1Whiler>0Whileq(r)<8

q(r)=qq(r)+1DimOK%=1Forj=1Tor-1Ifq(r)=q(j)Ormath.abs(r–j)=math.abs(q(r)-q(j))ThenOK=0ExitForEndIfNextIfOK=1Then

If(r<8)Thenr=r+1Else

printstr(q)‘调用打印输出放置解

EndIfEndIfEndWhileqq(r)=0r=r-1EndWhile递归回溯法解决八皇后问题3.3调用search(1)行号r=形参i<8q(r)列符合放置条件r>8输出解q(r)=i是是是否否返回0调用search(r+1)i=i+1否

PrivateFunctionsearch(ByValrAsInteger)If(r>8)Then

printstr(q)

Return0EndIfFori=1To8q(r)=iDimOK%=1Forj=1Tor-1Ifq(r)=q(j)OrMath.Acos(r-j)=Math.Abs(q(r)-q(j))Then