import java.util.*;

public class SolveNQueens_51 {

// 设置成员变量减少递归调用参数传递

int n;

List<List<String>> res;

// 判断列上是否有皇后

boolean[] col;

// 判断主对角线上是否有皇后

boolean[] main;

// 判断副对角线上是否有皇后

boolean[] sub;

public List<List<String>> solveNQueens(int n) {

res = new ArrayList<>();

if (n == 0) {

return res;

}

this.n = n;

col = new boolean[n];

main = new boolean[n * 2 - 1];

sub = new boolean[n * 2 - 1];

Deque<Integer> path = new ArrayDeque<>();

dfs(0, path);

return res;

}

public void dfs(int row, Deque<Integer> path) {

// row 从第0行开始，如果 row=n 表示已经得到了一个结果

if (row == n) {

res.add(convertToBoard(path));

}

for (int i = 0; i < n; i++) {

// 主对角线行数减列数值固定，副对角线行数加列数值固定

// 这里不能用 row - i 直接判断主对角线，可能会出现负值，使用 row-i+n-1

if (!col[i] && !main[row - i + n - 1] && !sub[row + i]) {

col[i] = true;

main[row - i + n - 1] = true;

sub[row + i] = true;

path.addLast(i);

dfs(row + 1, path);

col[i] = false;

main[row - i + n - 1] = false;

sub[row + i] = false;

path.removeLast();

}

}

}

public List<String> convertToBoard(Deque<Integer> path) {

List<String> res = new ArrayList<>();

Iterator<Integer> iterator = path.iterator();

while(iterator.hasNext()) {

int i = iterator.next();

StringBuilder sb = new StringBuilder();

for (int j = 0; j < n; j++) {

if (j != i) {

sb.append(".");

} else {

sb.append("Q");

}

}

res.add(sb.toString());

}

// // 简化以上写法

// // repeat 为 jdk11 新增方法

// for (Integer num : path) {

// StringBuilder row = new StringBuilder();

// row.append(".".repeat(Math.max(0, n)));

// row.replace(num, num + 1, "Q");

// res.add(row.toString());

// }

return res;

}

}