• ㊗️
• 大家
• offer
• 多多！

## Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:

Input: n = 1
Output: [["Q"]]


## Code

class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
if(n <= 0){
return res;
}

helper(res, new int[n], 0);
return res;
}
/*
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],
queens数组在这种情况下为[1,3,0,2]
queens是为了检查当前行放了Q的位置是否在列上会有冲突
因此在queens中不能有重复的数字
行不用管，因为每一行只能放一个

pos指的是行
*/
private void helper(List<List<String>> res, int[] queens, int pos){
// 到了最后一行
if(pos == queens.length){
return;
}

for(int i = 0; i < queens.length; i++){
// 在第pos行，把queen放在位置i上，看是不是可行
queens[pos] = i;
if(isValid(queens, pos)){
// 如果可行的话，就进入到下一行
helper(res, queens, pos + 1);
}
}
}

private boolean isValid(int[] queens, int pos){
for(int i = 0; i < pos; i++){
// 放到当前行的时候，如果出现重叠的列，那就是false
// 比如[1,1,.....]
if(queens[i] == queens[pos]){
return false;
}
// 判断斜线是不是相同
/*
["Q...",
".Q..",
"....",
"...."],
*/
// 此时pos = 1, i = 0, queens=[0,1,0,0]
// queens[1] - queens[0] = 1
// i - pos = 1
// 返回false
// 简单说就是： 如果两点的列之差(绝对值)等于行之差(绝对值) 那两点就在同一对角线上
if(Math.abs(queens[pos] - queens[i]) == Math.abs(i - pos)){
return false;
}
}
return true;
}

// 得到一个有效解, 加入到最终的结果中
private void addSolution(List<List<String>> res, int[] queens){
List<String> list = new ArrayList<>();
for(int i = 0; i < queens.length; i++){
StringBuilder sb = new StringBuilder();
for(int j = 0; j < queens.length; j++){
if(queens[i] == j){
sb.append('Q');
} else{
sb.append('.');
}
}
// 完成一行了，加入到list中