# N-Queens

Hard

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 integern, return all distinct solutions to then-queens puzzle.

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

Example:

Input:
4

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

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

Explanation:
There exist two distinct solutions to the 4-queens puzzle as shown above.

## Solution

Backtracking

class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();

if (n <= 0) {
return ans;
}
searchHelper(n, new ArrayList<Integer>(), ans);

return ans;
}

// Backtracking recursively find the valid solutions
private void searchHelper(int n, List<Integer> cols, List<List<String>> ans) {
if (cols.size() == n) {
return;
}

for (int col = 0; col < n; col++) {
if (!isValid(col, cols)) {
continue;
}
searchHelper(n, cols, ans);
cols.remove(cols.size() - 1);
}
}

// Output the one solution of the board in desired format
private List<String> drawBoard(List<Integer> cols) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < cols.size(); i++) {
StringBuilder sb = new StringBuilder();
// draw the row
for (int j = 0; j < cols.size(); j++) {
if (cols.get(i) == j) {
sb.append("Q");
continue;
}
sb.append(".");
}
}
return board;
}

// Check if the new position to be placed is invalid
private boolean isValid(int col, List<Integer> cols) {
if (cols.size() == 0) {
return true;
}

for (int row = 0; row < cols.size(); row++) {
if (col == cols.get(row)) {
return false;
}
if (cols.get(row) - row == col - cols.size()) {
return false;
}
if (cols.get(row) + row == col + cols.size()) {
return false;
}
}
return true;
}
}

@mnmunknown

public class Solution {
public List<List<String>> solveNQueens(int n) {
boolean[]
//ocp0 = new boolean[n],
ocp90 = new boolean[n],
// 总共 2n - 1 种可能性，(0,0) 的 index 是 n - 1
ocp45 = new boolean[2 * n - 1],
ocp135 = new boolean[2 * n - 1];
List<List<String>> ans = new ArrayList<List<String>>();
char[][] map = new char[n][n];
for (char[] tmp : map) Arrays.fill(tmp, '.'); //init

solve(0, n, map, ans, ocp45, ocp90, ocp135);
return ans;
}

private void solve(int depth, int n, char[][] map, List<List<String>> ans,
boolean[] ocp45, boolean[] ocp90, boolean[] ocp135) {
if (depth == n) {
return;
}

for (int j = 0; j < n; j++)
// 每次都进行新的一行，所以行不用检查
// 90度代表棋盘的列
// 45度对角线（从左上到右下）同一条线上 row + col 是相等的，因此可用作 index
// 135度对角线（从左下到右上）可从 (0,0) 即 index (n - 1) 为起点
// 因为同一条对角线 row - col 值恒定，可用作 offset 表示对角线的 index.
if (!ocp90[j] && !ocp45[depth + j] && !ocp135[j - depth + n - 1]) {
ocp90[j] = true;
ocp45[depth + j] = true;
ocp135[j - depth + n - 1] = true;
map[depth][j] = 'Q';

solve(depth + 1, n, map, ans, ocp45, ocp90, ocp135);

ocp90[j] = false;
ocp45[depth + j] = false;
ocp135[j - depth + n - 1] = false;
map[depth][j] = '.';
}
}

private void addSolution(List<List<String>> ans, char[][] map) {
List<String> cur = new ArrayList<String>();
for (char[] i : map) cur.add(String.valueOf(i));
}