N 皇后
leetcode第51题 (困难)
原链接: https://leetcode-cn.com/problems/n-queens/
题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例 1:
输入:n = 4,输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1,输出:[["Q"]]
解题思路
该题采用经典的回溯算法,因为根据题目在每行或每列都不能出现多个皇后,所以每行每列有且只能有一个皇后。
采用回溯算法,先把第一个皇后放在第一列的第一个位置[0][0],此时是满足条件的。
然后把第二个皇后放在第二列的第一个位置[0][1],这时和第一个皇后发送冲突,第一行有两个皇后,不满足条件,移动位置,把第二个皇后放在第二列的第二个位置[1][1],发现还冲突,对角线上有两个皇后,然后再放到第三个位置[2][1],满足条件。
然后放第三个皇后,先将第三个皇后放第三列的第一个位置[0][2],发现不满足条件第一行有两个皇后,放在第二个位置发现还不满足条件,对角线有两个皇后,最终第三个第四个位置都不满足条件。那么此时将先放弃第三个皇后的摆放回溯到第二个皇后,遍历第二个皇后的下一个位置[3][1],满足条件后再放第三个皇后。当所有皇后都摆放完毕,且都满足条件后,那么这就是一种完整的解法。
依次类推,当每一个皇后所在列的所有行都遍历完后,那么算法就结束了。
通常这种算法采用递归函数来实现,当然我们用定义的栈的数据结构也可以解决,只不过复杂度更高一些。
在判断放置每个皇后是否满足条件的时候可以采用状态压缩的方式,例如在表示二维数组的每一行上是否有皇后时,我们可以定义一个一维数组去表示比如:hang[n]={1,0,1,0},意思就是第一行和第三行有一个皇后,第二行和第四行没有皇后,采用这个方法就可以很快速的知道某一行是否有皇后,那么列和斜线都可以采用这种方案。只需要在放置皇后以后去改变该位置上数组的值就可以。
代码(java)
class Solution {
public List<List<String>> solveNQueens(int n) {
return begin(n);
}
int w,hh;
int [] hang,lie,s,x;
char area[][];
List<List<String>> list=new ArrayList<>();
public List<List<String>> begin(int n) {
hang=new int[n];
lie=new int[n];
s=new int[2*n-1];
x=new int[2*n-1];
w=(hh=n)-1;
area=new char[n][n];
for(int i=0;i<hh;i++){
for(int j=0;j<hh;j++){
area[i][j]='.';
}
}
dfs(0);
return list;
}
//第n个
public void dfs(int n){
if(n>=hh){
ArrayList arrayList=new ArrayList(hh);
for(int i=0;i<hh;i++){
StringBuilder stringBuilder=new StringBuilder();
for(int j=0;j<hh;j++){
stringBuilder.append(area[i][j]);
}
arrayList.add(stringBuilder.toString());
}
list.add(arrayList);
return;
}
for (int i=0;i<hh;i++){
int ni=n+i;
int wi=n+(w-i);
if(hang[i]==1||lie[n]==1||s[ni]==1||x[wi]==1){
continue;
}else{
hang[i]=1;lie[n]=1;s[ni]=1;x[wi]=1;
area[i][n]='Q';
dfs(n+1);
area[i][n]='.';
hang[i]=0;lie[n]=0;s[ni]=0;x[wi]=0;
}
}
}
}