问题背景
n n n 皇后问题 研究的是如何将 n n n 个皇后放置在 n × n n \times n n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n n n,返回 n n n 皇后问题 不同的解决方案的数量。
数据约束
- 1 ≤ n ≤ 9 1 \le n \le 9 1≤n≤9
解题过程
只需要统计可能的结果数量,参考修改 昨天的题解 就可以。
在不需要输出路径的前提下,位运算实现的优势就非常明显了。直接标记需要路径数组来记录之前访问过的节点信息,用布尔型数组虽然不需要记录路径,也避免不了定义几个标记数组。
具体实现
直接判断
class Solution {public int totalNQueens(int n) {int[] path = new int[n];return dfs(0, n, path);}private int dfs(int i, int n, int[] path) {if(i == n) {return 1;}int res = 0;for(int j = 0; j < n; j++) {if(check(i, j, path)) {path[i] = j;res += dfs(i + 1, n, path);path[i] = 0;}}return res;}private boolean check(int i, int j, int[] path) {for(int k = 0; k < i; k++) {if(j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {return false;}}return true;}
}
位运算限制
class Solution {public int totalNQueens(int n) {return dfs(n, (1 << n) - 1, 0, 0, 0);}private int dfs(int n, int mask, int col, int mainDiag, int subDiag) {if(col == mask) {return 1;}int limit = col | mainDiag | subDiag;int candidate = mask & (~limit);int cur;int res = 0;while(candidate != 0) {cur = candidate & (-candidate);candidate ^= cur;res += dfs(n, mask, col | cur, (mainDiag | cur) << 1, (subDiag | cur) >>> 1);}return res;}
}
数组标记
class Solution {public int totalNQueens(int n) {boolean[] col = new boolean[n];boolean[] mainDiag = new boolean[2 * n - 1];boolean[] subDiag = new boolean[2 * n - 1];return dfs(0, n, col, mainDiag, subDiag);}private int dfs(int i, int n, boolean[] col, boolean[] mainDiag, boolean[] subDiag) {if(i == n) {return 1;}int res = 0;for(int j = 0; j < n; j++) {if(!col[j] && !mainDiag[i + j] && !subDiag[i - j + n - 1]) {col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = true;res += dfs(i + 1, n, col, mainDiag, subDiag);col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = false;}}return res;}
}