问题说明: 西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无事的放置在棋盘上? 希望对各位有点帮助
算法代码: 1. public class Queen { 2. // 同位置是否有皇后,1表示有 3. private int[] column; 4. // 右上至左下是否有皇后 5. private int[] rup; 6. // 左上至右下是否有皇后 7. private int[] lup; 8. // 解答 9. private int[] queen; 10. 11. // 解答编号 12. private int num; 13. 14. public Queen() { 15. column = new int[8+1]; 16. rup = new int[2*8+1]; 17. lup = new int[2*8+1]; 18. 19. for(int i = 1; i <= 8; i++) 20. column = 1; 21. 22. for(int i = 1; i <= 2*8; i++) 23. rup = lup = 1; 24. 25. queen = new int[8+1]; 26. } 27. 28. public void backtrack(int i) { 29. if(i > 8) { 30. showAnswer(); 31. } 32. else { 33. for(int j = 1; j <=8; j++) { 34. if(column[j] == 1 && 35. rup[i+j] == 1 && 36. lup[i-j+8] == 1) { 37. queen = j; 38. // 设定为占用 39. column[j] = rup[i+j] = lup[i-j+8] = 0; 40. backtrack(i+1); 41. column[j] = rup[i+j] = lup[i-j+8] = 1; 42. } 43. } 44. } 45. } 46. 47. protected void showAnswer() { 48. num++; 49. System.out.println("\n解答 " + num); 50. for(int y = 1; y <= 8; y++) { 51. for(int x = 1; x <=8; x++) { 52. if(queen[y] == x) { 53. System.out.print(" Q"); 54. } 55. else { 56. System.out.print(" ."); 57. } 58. } 59. System.out.println(); 60. } 61. } 62. 63. public static void main(String[] args) { 64. Queen queen = new Queen(); 65. queen.backtrack(1); 66. } 67. } 八枚银币(Coins)
|