八皇后问题

问题：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

 代码：

 1 import org.junit.Test;
 2 import java.util.Arrays;
 3 
 4 public class EightQueensTest {
 5     @Test
 6     public void test() {
 7         EightQueens eightQueens = new EightQueens();
 8         //从第0个皇后开始摆放
 9         eightQueens.putQueen(0);
10     }
11 }
12 
13 class EightQueens {
14 
15     /**
16      * 八皇后的一种解法
17      * 下标代表第几个皇后，在第几行
18      * 值代表在第几列
19      */
20     private int[] answer = new int[QUEEN_NUM];
21 
22     /**
23      * 第count种解法
24      */
25     private int count;
26 
27     /**
28      * 皇后的数量
29      */
30     public static final int QUEEN_NUM = 8;
31 
32     /**
33      * 是否不与其它皇后冲突
34      * @param n 摆第n个皇后
35      * @return
36      */
37     private boolean isPeace(int n) {
38         //皇后之间不冲突，则它们互相之间不在同一行、同一列、同一斜线
39         //第n个皇后摆在第n行，所以所有皇后不在同一行
40         for (int i = 0; i < n; i++) {
41             //answer[n] == answer[i]:第n个皇后与第i个皇后在同一列
42             //Math.abs(n - i) == Math.abs(answer[n] - answer[i]):第n个皇后与第i个皇后在同一斜线
43             //当第n个皇后与第i个皇后在同一斜线，那么它们的行数差==列数差
44             if (answer[n] == answer[i] || Math.abs(n - i) == Math.abs(answer[n] - answer[i])) {
45                 return false;
46             }
47         }
48         return true;
49     }
50 
51     /**
52      * 摆放第n个皇后
53      * @param n
54      */
55     public void putQueen(int n) {
56         if (n == QUEEN_NUM) {
57             //摆放第8个皇后，皇后从0开始算，也就说这是第九个皇后，则已经放好了八个皇后
58             count++;
59             printAnswer();
60             return;
61         }
62 
63         //第n个皇后有八种摆法
64         for (int i = 0; i < QUEEN_NUM; i++) {
65             //将第n个皇后摆在第i列
66             answer[n] = i;
67             if (isPeace(n)) {
68                 //第n个皇后摆放可行，则摆放第n + 1个皇后
69                 putQueen(n + 1);
70             }
71             //如果冲突，那继续循环将第n个皇后摆在后一列
72         }
73     }
74 
75     /**
76      * 打印解法
77      */
78     private void printAnswer() {
79         System.out.println("第" + count + "种解法：answer=" + Arrays.toString(answer));
80     }
81 }