[LeetCode 51] N皇后
题目描述
示例:
输入: 4
输出: [
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],
["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
解释: 4 皇后问题存在两个不同的解法。
题目分析
这个N皇后其实和数独有异曲同工的地方，皇后不能互相攻击的意思就在同一行同一列以及两条对角线上不能由其他的皇后，否则就将不符合题意。和数独同样的思路，设三个数组，默认为是fault，如果插入数组，那么就同行同列，以及对角线都为true。最后根据数组的索引插入"Q"或者"."。同样的，用回溯算法，既然不知道第几次能完全插入正确，那就一个一个的试了，直到正确为止。
源码
class Solution {
List<List<String>> result=new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
LinkedList<Integer> res=new LinkedList<>();
boolean[] col=new boolean[n];
boolean[] main_diag=new boolean[2*n];
boolean[] anti_diag=new boolean[2*n];
dfs(res,col,main_diag,anti_diag,0,n);
return result;
}
private void dfs(LinkedList<Integer> res,boolean[] col,boolean[] main_diag,boolean[] anti_diag,int row,int n){
if(row==n){
List<String> list=new LinkedList<>();
for(int i=0;i<n;i++){
StringBuilder sb=new StringBuilder();
for(int j=0;j<n;j++){
sb.append(res.get(i) == j ? "Q" : ".");
}
list.add(sb.toString());
}
result.add(list);
return;
}
for(int i=0;i<n;i++){
if(col[i]||main_diag[row+i]||anti_diag[row-i+n]){
continue;
}
res.add(i);
col[i]=true;
main_diag[i+row]=true;
anti_diag[row-i+n]=true;
dfs(res,col,main_diag,anti_diag,row+1,n);
res.removeLast();
col[i]=false;
main_diag[row+i]=false;
anti_diag[row-i+n]=false;
}
}
}
难点
这道题最首先的难点就是理解题意，没玩过象棋的还真不知道互相攻击是什么意思，仅仅误解为行列不能相同那就惨了。
其次，要比数独多一个索引的链表，当然了 如果用数独的二维数组也可以，这样可以少一个索引链表但是多一个参数row[n][n]。
小结
对于同行同列或者同对角线不能出现相同的数据的这类题目，思路就是设个boolean的数组，被索引了或者访问了就设为true，如果第二次被访问了那就直接报错就行啦。