### 问题描述

https://leetcode.com/problems/n-queens/#/description

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

Given an integer n, return all distinct solutions to the n-queens puzzle.

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

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]


N-皇后问题

### 代码

       public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
solve(res, new int[n], n, 0, new String[n]);
return res;
}

public void solve(List<List<String>> list, int[] c, int n, int index, String[] cur) {
if(index == n) {
return;
}
// 从第一列开始遍历
for(int j=0;j<n;j++) {
c[index] = j; // 将第index行的皇后放在第j列
boolean has = false; // 是否有冲突标志位
// 遍历当前已放置好的皇后，看是否有冲突
for(int i=0;i<index;i++) {
if(c[i] == c[index] || Math.abs(i-index)==Math.abs(c[i]-c[index])) {
has = true;
}
}
if(!has) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[j] = 'Q';
cur[index] = new String(row);
// 如果没有冲突，当前解法可行，增加一位皇后
solve(list, c, n, index+1, cur);
}
}
}