黑马程序员技术交流社区
标题: java经典算法之八个皇后（Queen） [打印本页]
作者: 王海彬 时间: 2015-9-16 23:03
标题: java经典算法之八个皇后（Queen）
问题说明：
西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上？
希望对各位有点帮助
算法代码：
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）
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |