# 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.

![](https://assets.leetcode.com/uploads/2018/10/12/8-queens.png)

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.

**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

```java
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) {
            ans.add(drawBoard(cols));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(col, cols)) {
                continue;
            }
            cols.add(col);
            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(".");
            }
            board.add(sb.toString());
        }
        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](https://mnmunknown.gitbooks.io/algorithm-notes/518_search_&_recursion_3.html)
>
> 更取巧的方式是，利用一个皇后会占用这个格子的所有行，列以及对角线的特点，维护所有“行，列，45度对角线，135度对角线” 的 boolean array，这样在每次考虑一个新位置的时候，只需要 $$O(1)$$ 的时间进行一次操作就可以了。

```java
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) {
            addSolution(ans, map);
            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));
        ans.add(cur);
    }
}
```