八皇后——穷举法.docx

利用穷举解法来解决八皇后问题。 由于棋盘的对称性，第一行只考虑前四列的情况，然后逐行查找可行点，计算出结果后，总的解法数即是计算结果的两倍，而后四列的情况也即是前四列结果关于垂直线的对称。源程序如下：1. publicclassEightQueens2. intanswer=0;/结果数 3. intchess=newint88;/棋盘 4. EightQueens()5. inti=0,j=0,k=0;6. /取半个棋盘计算结果，最后结果*2 7. for(k=0;k4;k+)8. /棋盘初始化为0 9. for(i=0;i8;i+)10. for(j=0;j8;j+)11. chessij=0;12. 13. /第一行 14. chess0k=1;15. row(1);16. 17. System.out.println(八皇后问题共有+answer+种解法);18. 19. publicvoidrow(intI)20. inti=0,j=0;21. for(j=0;j8;j+)22. /重新初始化行 23. for(i=I;i0)25. for(intk=0;k8;k+)26. chessik=0;27. 28. 29. 30. if(sum1(j)=0&sum2(I,j)=0)31. chessIj=1;32. if(I=7)33. answer+=2;34. /输出结果，棋盘以数组形式表示 35. /*for(inta=0;a8;a+)36. for(intb=0;b8;b+)37. System.out.println(解法+answer+:);38. System.out.print(chessab+);39. 40. System.out.println();41. 42. System.out.println();43. */44. /*for(inta=0;a8;a+)45. for(intb=0;b8;b+)46. System.out.println(解法+(answer+1)+:);47. System.out.print(chessa7-b+);48. 49. System.out.println();50. 51. System.out.println();52. */53. 54. elserow(I+1);55. 56. 57. 58. /计算行值 59. publicintsum(inti)60. intj=0,s=0;61. for(j=0;j8;j+)62. s+=chessij;63. 64. returns;65. 66. /计算列值 67. publicintsum1(intj)68. inti=0,s=0;69. for(i=0;i=0&j=0;i-,j-)78. s+=chessij;79. 80. for(i=I,j=J;i=0&j8;i-,j+)81. s+=chessij;82. 83. for(i=I,j=J;i=0;i+,j-)84. s+=chessij;85. 86. for(i=I,j=J;i8&j8;i+,j+)87. s+=chessij;88. 89. returns;90. 91. publicstatic