05 August 2008
给一个n代表棋盘，返回所有可能的queens的solutions
Backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
int count = 0;
public int totalNQueens(int n) {
boolean[] cols = new boolean[n]; // columns |
boolean[] d1 = new boolean[2 * n]; // diagonals \
boolean[] d2 = new boolean[2 * n]; // diagonals /
backtracking(0, cols, d1, d2, n);
return count;
}
public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
if(row == n) count++;
for(int col = 0; col < n; col++) {
int id1 = col - row + n;
int id2 = col + row;
if(cols[col] || d1[id1] || d2[id2]) continue;
cols[col] = true; d1[id1] = true; d2[id2] = true;
backtracking(row + 1, cols, d1, d2, n);
cols[col] = false; d1[id1] = false; d2[id2] = false;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
int result = 0;
public int totalNQueens(int n) {
boolean[] column = new boolean[n];
boolean[] dia45 = new boolean[2 * n - 1];
boolean[] dia135 = new boolean[2 * n - 1];
helper(0, n, column, dia45, dia135);
return result;
}
private void helper(int row, int n, boolean[] column, boolean[] dia45, boolean[] dia135) {
if (row == n) {
result++;
return;
}
for (int col = 0; col < n; col++) {
if (!column[col] && !dia45[col + row] && !dia135[n - 1- row + col]) {
column[col] = dia45[col + row] = dia135[n - 1- row + col] = true;
helper(row + 1, n, column, dia45, dia135);
column[col] = dia45[col + row] = dia135[n - 1- row + col] = false;
}
}
}
}