题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
样例
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
输入:n = 1
输出:1
算法1
(基于集合的DFS + 回溯) $O(n!)$
回溯算法的特点就是按照题目的要求尽可能的返回全面的答案,那么这就很难避免对这个矩阵(数组) 来进行各种枚举,所以从这个角度看回溯算法其实也算是一种暴力搜索算法,时间复杂度还是很高的。
来说下题目思路:
1.递归终止条件:当皇后来到martix.length - 1的位置的时候,就已经是摆放皇后的最后一个位置了,然后用一个变量来记录当前皇后的递归深度:level,所以递归终止条件: level == martix.length 时退出递归。
2.利用for 循环来遍历二维矩阵的所有列,使得皇后在每个列上作为开头找到对应的组合方案(递归)
3.题目中说到,在摆放的当前皇后的位置的同一行,同一列,同一斜率的方向都不能摆放其他皇后,这就是剪枝条件了。
关于同一斜率的条件如何定义:
如何不让皇后在同一列上:定义一个存放col 位置的容器,只要成功摆放一个皇后的位置,就把当前的col 位置计入容器中,后面的皇后只要从这个容器中能获取到这个值,说明后面的皇后与前面的皇后处于同一列,则当前列位置不能进行摆放。
如何不让皇后在同一行上:只要我们成功摆放了一个皇后,就进入递归,去到下一行摆放新皇后的位置。
时间复杂度
由于每个皇后必须位于不同列,因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择,第二个皇后最多有 N−1 列可以选择,第三个皇后最多有 N−2 列可以选择(如果考虑到不能在同一条斜线上,可能的选择数量更少),因此所有可能的情况不会超过 N! 种,遍历这些情况的时间复杂度是 O(N!)。
参考文献
Java 代码
public class N皇后II {
int result ;
public int totalNQueens(int n) {
if(n <= 0) return n;
//记录路径
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
Set<Integer> col = new HashSet<>();
dfs(n,pie,na,col,0);
return result;
}
void dfs(int n,Set<Integer> pie,Set<Integer> na,Set<Integer> col,int level){
if(level == n){
result = result + 1;
return;
}
for(int i = 0; i < n; i++){
if(pie.contains(i - level) || na.contains(i + level) || col.contains(i)){ //剪枝
continue;
}
pie.add(i-level);
na.add(i+level);
col.add(i);
dfs(n,pie,na,col,level+1);
//回溯
pie.remove(i - level);
na.remove(i + level);
col.remove(i);
}
}
}