> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0051-n-queens.md).

# 0051. N-Queens

<https://leetcode.com/problems/n-queens>

## Description

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

![](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)

```
**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"]]
```

**Constraints:**

* `1 <= n <= 9`

## ac

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

        List<char[]> board = new ArrayList<char[]>();
        char[] chars = new char[n];
        for (int i = 0; i < n; i++) chars[i] = '.';
        for (int i = 0; i < n; i++) board.add(chars.clone());

        Set<Integer> cSet = new HashSet<Integer>();

        backtrack(n, 0, cSet, board, res);

        return res;
    }
    private void backtrack(int n, int r, Set<Integer> cSet, List<char[]> board, List<List<String>> res) {
        if (r == n) {
            res.add(copyBoard(board));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!cSet.contains(i) && canPut(board, r, i)) {
                cSet.add(i);
                board.get(r)[i] = 'Q';
                backtrack(n, r+1, cSet, board, res);
                cSet.remove(i);
                board.get(r)[i] = '.';
            }
        }
    }
    private boolean canPut(List<char[]> board, int row, int col) {
        int r = row, c = col;
        while (r >= 0 && c >= 0) {
            if(board.get(r)[c] == 'Q') return false;
            r--;
            c--;
        }
        r = row;c = col;
        while (r >= 0 && c < board.get(0).length) {
            if(board.get(r)[c] == 'Q') return false;
            r--;
            c++;
        }
        return true;
    }
    private List<String> copyBoard(List<char[]> board) {
        List<String> r = new ArrayList<String>();
        for (int i = 0; i < board.size(); i++) {
            r.add(String.valueOf(board.get(i)));
        }
        return r;
    }
}
```