N 皇后问题
毫无疑问这是道经典题。
一个比较常规的做法可能是每次向棋盘上新加第i个queen时，检查它是否跟前i-1个有冲突。这样的话其实要产生每个solution就要检查0+1+2+...+n-1 = O(n^2)倍，不是特别efficient。
另一种比较6的做法时，维护三个boolean数组ocp90, ocp45, ocp135，分别记录哪些列，45度对角线和135度对角线已经被占。其中ocp45和ocp135的下标规律是：
| | | / / / \ \ \ O O O O O O O O O | | | / / / / \ \ \ \ O O O O O O O O O | | | / / / / \ \ \ \ O O O O O O O O O | | | / / / \ \ \ 3列 5条45度对角线 5条135度对角线 (n等于3时)
- 同一条45度对角线上i+j值是一样的，在[0, 1, 2n-2]区间内，所以可以用i+j作为index
- 同一条135度对角线上i-j的值时一样的，在[-(n-1), -(n-2), ..., -2, -1, 0, 1, 2, ..., n-1]范围内，因此可以用i-j+n-1作为index
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
if (n == 0)
return res;
boolean[] ocp90 = new boolean[n], ocp45 = new boolean[2*n-1], ocp135 = new boolean[2*n-1];
char[][] board = new char[n][n];
for (char[] row : board)
Arrays.fill(row, '.');
backtrack(res, board, 0, n, ocp90, ocp45, ocp135);
return res;
}
public void backtrack(List<List<String>> res, char[][] board, int i, int n, boolean[] ocp90, boolean[] ocp45, boolean[] ocp135){
if (i == n){
List<String> l = new ArrayList<>();
for (char[] row : board)
l.add(new String(row));
res.add(l);
return;
}
for (int j = 0; j < n; j++){
if (!ocp90[j] && !ocp45[i+j] && !ocp135[i-j+n-1]){
ocp90[j] = true;
ocp45[i+j] = true;
ocp135[i-j+n-1] = true;
board[i][j] = 'Q';
backtrack(res, board, i+1, n, ocp90, ocp45, ocp135);
board[i][j] = '.';
ocp135[i-j+n-1] = false;
ocp45[i+j] = false;
ocp90[j] = false;
}
}
}
}
和上一道题不同的地方是，这道题要求返回解的个数。
所以做法上的区别就是：找到一个解时，不需要再把board configuration加到一个list里，而是想办法累计解的个数就行了。
那么问题来了：怎么累计解的个数呢？常用的方法有两种：
- 直接用一个全局int变量。但是这样感觉看起来比较不好看。。。
- dfs返回搜索树中以当前节点为根的子树的解的个数（比较拗口。。。其实就是当前节点的返回值是它几个child节点的返回值的累加和。。。）
这里采用了第二种方法：
class Solution {
public int totalNQueens(int n) {
if (n <= 0)
return 0;
boolean[] ocp90 = new boolean[n], ocp45 = new boolean[2*n-1], ocp135 = new boolean[2*n-1];
return dfs(n, 0, ocp90, ocp45, ocp135);
}
public int dfs(int n, int i, boolean[] ocp90, boolean[] ocp45, boolean[] ocp135){
if (i == n)
return 1;
int sum = 0;
for (int j = 0; j < n; j++){
if (!ocp90[j] && !ocp45[i+j] && !ocp135[i-j+n-1]){
ocp90[j] = true;
ocp45[i+j] = true;
ocp135[i-j+n-1] = true;
sum += dfs(n, i+1, ocp90, ocp45, ocp135);
ocp90[j] = false;
ocp45[i+j] = false;
ocp135[i-j+n-1] = false;
}
}
return sum;
}
}