n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."], ["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
] 该题与LeetCode37题解数独类似：LeetCode-37.解数独
注释见代码
import java.util.ArrayList;
class Solution {
private List<List<String>> result;
public List<List<String>> solveNQueens(int n) {
char [][]array=new char [n][n];
result=new ArrayList<>();
//初始化数组
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
array[i][j]='.';
//先横再竖，全部规则符合时，切换到下一行
solveNQueens(array,0);
return result;
}
//参数n为数组行
public void solveNQueens(char [][]array,int n) {
int num=array.length;
//当n==num时，即为所有行数都已填入，此时处理array
if(n==num){
Deal(array);
return ;
}
for(int i=0;i<num;i++){
//每一位插入Q
array[n][i]='Q';
//因为从第一行开始填入，所以只需要进行从第一行到n行的检查
//分别为竖列的检查和斜的检查
if(checkj(array,n,i)&&checkij(array,n,i)){
//如果都符合规则的话就进入下一行
solveNQueens(array,n+1);
}
//当递归完成后或者不符合规则的时候更改回'.'
array[n][i]='.';
}
}
//处理array
private void Deal(char[][] array){
int num=array.length;
List<String> list=new ArrayList<>();
for(int i=0;i<num;i++){
String str="";
for(int j=0;j<num;j++){
str+=array[i][j];
}
list.add(str);
}
result.add(list);
}
//检查竖的
private boolean checkj(char [][]array,int i,int j){
for(int m=0;m<i;m++){
if(array[m][j]=='Q')
return false;
}
return true;
}
//检查斜的
private boolean checkij(char [][]array,int i,int j){
int num=array.length;
int tmpi=i,tmpj=j;
//从左上到该坐标
while(tmpi>0&&tmpj>0){
tmpi--;
tmpj--;
}
//寻找临界点
while(tmpi<i&&tmpj<j){
if(array[tmpi][tmpj]=='Q')
return false;
tmpi++;
tmpj++;
}
//从右上到该坐标
tmpi=i;
tmpj=j;
//寻找临界点
while(tmpi>0&&tmpj<num-1){
tmpi--;
tmpj++;
}
while(tmpi<i&&tmpj>j){
if(array[tmpi][tmpj]=='Q')
return false;
tmpi++;
tmpj--;
}
return true;
}
}