實(shí)驗(yàn)報(bào)告：回溯法求解N皇后問(wèn)題(Java實(shí)現(xiàn))

1、實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)名稱：回溯法求解N皇后問(wèn)題（Java實(shí)現(xiàn)）二、學(xué)習(xí)知識(shí)：回溯法：也稱為試探法，它并不考慮問(wèn)題規(guī)模的大小，而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案，并以此慢慢地?cái)U(kuò)大問(wèn)題規(guī)模，迭代地逼近最終問(wèn)題的解。這種迭代類似于窮舉并且是試探性的，因?yàn)楫?dāng)目前的可能答案被測(cè)試出不可能可以獲得最終解時(shí)，則撤銷當(dāng)前的這一步求解過(guò)程，回溯到上一步尋找其他求解路徑。為了能夠撤銷當(dāng)前的求解過(guò)程，必須保存上一步以來(lái)的求解路徑，這一點(diǎn)相當(dāng)重要。三、問(wèn)題描述N皇后問(wèn)題：在一個(gè) N * N 的國(guó)際象棋棋盤中，怎樣放置 N 個(gè)皇后才能使 N 個(gè)皇后之間不會(huì)互相有威脅而共同存在于棋局中，即在 N * N 個(gè)

2、格子的棋盤中沒(méi)有任何兩個(gè)皇后是在同一行、同一列、同一斜線上。深度優(yōu)先遍歷的典型案例。四、求解思路1、求解思路：最容易想到的方法就是有序地從第 1 列的第 1 行開(kāi)始，嘗試放上一個(gè)皇后，然后再嘗試第 2 列的第幾行能夠放上一個(gè)皇后，如果第 2 列也放置成功，那么就繼續(xù)放置第 3 列，如果此時(shí)第3 列沒(méi)有一行可以放置一個(gè)皇后，說(shuō)明目前為止的嘗試是無(wú)效的（即不可能得到最終解），那么此時(shí)就應(yīng)該回溯到上一步（即第 2 步），將上一步（第 2 步）所放置的皇后的位置再重新取走放在另一個(gè)符合要求的地方如此嘗試性地遍歷加上回溯，就可以慢慢地逼近最終解了。2、需要解決的問(wèn)題：如何表示一個(gè) N * N 方格棋盤能

3、夠更有效？怎樣測(cè)試當(dāng)前所走的試探路徑是否符合要求？這兩個(gè)問(wèn)題都需要考慮到使用怎樣的數(shù)據(jù)結(jié)構(gòu)，使用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)有利于簡(jiǎn)化編程求解問(wèn)題的難度。3、我們使用以下的數(shù)據(jù)結(jié)構(gòu)：int columncol =row 表示第 col列的第row 行放置一個(gè)皇后boolean rowExistsi = true 表示第 i 行有皇后boolean ai = true 表示右高左低的第 i 條斜線有皇后（按 順序從1 2*N -1 依次編號(hào)）boolean bi = true 表示左高右低的第 i 條斜線有皇后（按 順序從1 2*N -1 依次編號(hào)）五、算法實(shí)現(xiàn)對(duì)應(yīng)這個(gè)數(shù)據(jù)結(jié)構(gòu)的算法實(shí)現(xiàn)如下：1. * 2.

4、*回溯法求解N皇后問(wèn)題 3. *authorhaolloyin 4. */5. publicclassN_Queens 6. 7. /皇后的個(gè)數(shù) 8. privateintqueensNum=4; 9. 10. /columni=j表示第i列的第j行放置一個(gè)皇后 11. privateintqueens=newintqueensNum+1; 12. 13. /rowExistsi=true表示第i行有皇后 14. privatebooleanrowExists=newbooleanqueensNum+1; 15. 16. /ai=true表示右高左低的第i條斜線有皇后 17. privateb

5、ooleana=newbooleanqueensNum*2; 18. 19. /bi=true表示左高右低的第i條斜線有皇后 20. privatebooleanb=newbooleanqueensNum*2; 21. 22. /初始化變量 23. privatevoidinit() 24. for(inti=0;iqueensNum+1;i+) 25. rowExistsi=false; 26. 27. 28. for(inti=0;iqueensNum*2;i+) 29. ai=bi=false; 30. 31. 32. 33. /判斷該位置是否已經(jīng)存在一個(gè)皇后,存在則返回true 34.

6、 privatebooleanisExists(introw,intcol) 35. return(rowExistsrow|arow+col-1|bqueensNum+col-row); 36. 37. 38. /主方法：測(cè)試放置皇后 39. publicvoidtesting(intcolumn) 40. 41. /遍歷每一行 42. for(introw=1;rowqueensNum+1;row+) 43. /如果第row行第column列可以放置皇后 44. if(!isExists(row,column) 45. /設(shè)置第row行第column列有皇后 46. queenscolum

7、n=row; 47. /設(shè)置以第row行第column列為交叉點(diǎn)的斜線不可放置皇后 48. rowExistsrow=arow+column-1=bqueensNum+column-row=true; 49. 50. /全部嘗試過(guò)，打印 51. if(column=queensNum) 52. for(intcol=1;col=queensNum;col+) 53. System.out.print(+col+,+queenscol+); 54. 55. System.out.println(); 56. else 57. /放置下一列的皇后 58. testing(column+1); 59

8、. 60. /撤銷上一步所放置的皇后，即回溯 61. rowExistsrow=arow+column-1=bqueensNum+column-row=false; 62. 63. 64. 65. 66. /測(cè)試 67. publicstaticvoidmain(Stringargs) 68. N_Queensqueen=newN_Queens(); 69. queen.init(); 70. /從第1列開(kāi)始求解 71. queen.testing(1); 72. 73. 六、運(yùn)行結(jié)果當(dāng) N = 8 時(shí)，求解結(jié)果如下（注：橫坐標(biāo)為 列數(shù)， 縱坐標(biāo)為 行數(shù)）：(1,1)(2,5)(3,8)(4,

9、6)(5,3)(6,7)(7,2)(8,4) 1. (1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5) 2. (1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3) 3. . 4. . 5. (1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6) 6. (1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6) 7. (1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4) 8. (1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)當(dāng) N = 4 時(shí)，求解結(jié)果如下：1. (1,2)(2,4)(3,1)(4,3) 2. (1,3)(2,1)(3,4)(4,2)七、實(shí)驗(yàn)小結(jié)：1、根據(jù)問(wèn)題選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)非常重要，就像上面 a 、b 標(biāo)志數(shù)組來(lái)表示每一條斜線的編號(hào)順序以及方向都相當(dāng)重要?？磿?shū)的時(shí)候也是費(fèi)了些時(shí)間來(lái)理解的，呼另外，queens col = row數(shù)組只是用了一維而不是二維來(lái)表示縱橫交錯(cuò)的方格棋盤上特定位置是否有皇后也是比較經(jīng)濟(jì)而有意思的。2、正確運(yùn)用、組織所確定的數(shù)據(jù)結(jié)構(gòu)到算法的實(shí)現(xiàn)邏輯中也是很重要的，就像代碼中的 isExi