该问题使用回溯法是毫无疑问的，大多数人都能够指出这一点。但是这个问题比较核心的一点，我认为是对数组的思维。
n皇后问题要求我们在遍历一个点时，获知这个点的同一列，正对角线，反对角线上是否存在元素，如果存在，则这个点不能够作为当前解。
其中的关键问题就是，如何判定同一列以及两个对角线上是否已经存在点。
最原始的办法，可以使用一个二维数组记录某个点的占用情况，在遍历到某个点时，从二维数组的（0，0）处开始依轮询每个点。
一个初级的改进是只遍历二维数组中对角线和同一列的点。
但是如果从另外一个角度来看，二维数组（假定长度为n）只有n个列，2n-1个正对角线和2n-1个反对角线（斜着看）。一个点只可能属于同一列，同一正对角线，同一反对角线。以以正对角线为例，如果我们给如每个对角线编上唯一的序号，那么实际上可以根据点的坐标（i,j）来获得起所在对角线的编号，即n-1+i-j
这样一来，我们只需要3个标记数组，分别标记某列，某正对角线，某反对角线，就能仅通过3次判断知道某个点是否有效。
代码
import java.util.ArrayList;
import java.util.List;
class Solution {
private int n;
// 同一列的标记（一共有n个列）
9
private boolean[] column;
10
// 正对角线的标记（一共有2n-1个正对角线）
11
private boolean[] diag1;
12
// 反对角线的标记（一共有2n-1个反对角线）
13
private boolean[] diag2;
14
private int solutions;
15
16
public int totalNQueens(int n) {
17
this.n = n;
18
column = new boolean[n];
19
diag1 = new boolean[2*n-1];
20
diag2 = new boolean[2*n-1];
21
solutions = 0;
22
// init
23
for (int i = 0; i < n; i++) {
24
column[i]=false;
25
}
26
for(int i=0;i<2*n-1;i++){
27
diag1[i]=diag2[i]=false;
28
}
29
// solve recursively
30
solve(0);
31
return solutions;
32
}
33
34
35
private void solve(int row) {
36
if (row == n) {
37
return;
38
}
39
for (int i = 0; i < n; i++) {
40
if (!(column[i]||diag1[n-1+i - row]||diag2[i+row])) {
41
column[i]=diag1[n-1+i - row]=diag2[i+row]=true;
42
if (row == n - 1) {
43
++solutions;
44
} else {
45
solve(row + 1);
46
}
47
column[i]=diag1[n-1+i - row]=diag2[i+row]=false;
48
}
49
}
50
}
51
52
53
54
55
}
网友评论