n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
思想:
采用回溯的思想。用flag二位数组来存储各个位置是否被放置了皇后的信息。ans用来存放结果。
按行进行试验,当在(i,j)位置放置时,我们要先进行检测,(即检测之前的放置过的行中,相同列是否放置过皇后,以及对角线是否放置过皇后。)结果为true进行放置,进行下一行。如果该行所有位置都为false,则进行回溯,回溯到上一行。当row==n时,说明已经成功。则将结果添加到ans中。
代码:
class Solution {
List<List<String>> ans=new ArrayList<>();//存储结果
public List<List<String>> solveNQueens(int n) {
char [][]flag=new char[n][n];//N*N数组表征各个位置状态,是否存放了Q
for(char[] chars : flag){//flag数组初始化
Arrays.fill(chars,'.');
}
backTrack(flag,0,n);
return ans;
}
//回溯算法
public void backTrack(char[][]flag,int row,int n){
if(row==n){//此时说明成功,将结果存储到ans
ans.add(charToString(flag));
return;
}
for(int i=0;i<n;i++){//共n列,选择Q放在哪列
if(check(flag,row,i,n)){
flag[row][i]='Q';
backTrack(flag,row+1,n);
flag[row][i]='.';
}
}
}
//判断在(i,j)位置放置Q是否可行,即放置后是否违背规则约束
public boolean check(char [][]flag,int row,int col,int n){
for(int i=0;i<row;i++){
if(flag[i][col]=='Q'){//列判断
return false;
}
int l1=row-i;
for(int j=0;j<n;j++){//对角线判断
int l2=Math.abs(col-j);
if(l1==l2&&flag[i][j]=='Q'){
return false;
}
}
}
return true;
}
//将字符数组转化为字符串
public List<String> charToString(char[][] flag){
List<String> ans=new ArrayList<>();
for(char[] ch:flag){
ans.add(String.valueOf(ch));
}
return ans;
}
}