The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
使用深度优先遍历，并剪枝
注意斜线上的规律，左斜线上的点 横纵坐标和相同，右斜线上的点 横纵坐标差相同
class Solution {
int total = 0;
public int totalNQueens(int n) {
dfs(n,0,new ArrayList<Integer>(),new ArrayList<Integer>(),new ArrayList<Integer>());
return total;
}
private void dfs( int n, int level, List<Integer> cols, List<Integer> sum, List<Integer> dif) {
if (level == n) {
total++;
return;
}
for (int i = 0; i < n; i++) {
if (cols.contains(i) || sum.contains(i + level) || dif.contains(i - level))
continue;
cols.add(i);
sum.add(i + level);
dif.add(i - level);
dfs(n, level + 1, cols, sum, dif);
cols.remove(cols.size() - 1);
sum.remove(sum.size() - 1);
dif.remove(dif.size() - 1);
}
}
}
使用位运算（最优解）
class Solution {//DFS 位运算 mytip
public int totalNQueens(int n) {
int total=0;
return dfs(total,n,0,0,0,0);
//return total;
}
private int dfs(int total, int n, int level, int cols, int pie, int na) {
if (level == n) {
total++;
return total;
}
int bits = (~(cols|pie|na))&((1<<n)-1);//得到可能放的空位
while(0!=bits){//遍历可能放的空位
int cur = bits&(-bits);//得到最后一个1
total= dfs(total,n,level+1,cols|cur,(pie|cur)<<1,(na|cur)>>1);
bits= bits&(bits-1);//清楚最后一个1
}
return total;
}
}
相关题
n皇后 LeetCode51 https://www.cnblogs.com/zhacai/p/10621300.html