> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/backtracking/52-n-queens-ii.md).

# 52     N-Queens II

## 52. [N-Queens II](https://leetcode.com/problems/n-queens-ii/description/)

## 1. Question

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 the number of distinct solutions to the *n*-queens puzzle.

## 2. Implementation

**(1) Backtracking**

```java
class Solution {
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }

        int[] res = new int[n];
        boolean[] cols = new boolean[n];
        boolean[] diagnol1 = new boolean[2 * n];
        boolean[] diagnol2 = new boolean[2 * n];
        getTotalNQueens(0, n, cols, diagnol1, diagnol2, res);
        return res[0];
    }

    public void getTotalNQueens(int row, int n, boolean[] cols, boolean[] diagnol1, boolean[] diagnol2, int[] res) {
        if (row == n) {
            ++res[0];
            return;
        }

        for (int col = 0; col < n; col++) {
            int index1 = row - col + n;
            int index2 = row + col;

            if (cols[col] || diagnol1[index1] || diagnol2[index2]) {
                continue;
            }

            cols[col] = true;
            diagnol1[index1] = true;
            diagnol2[index2] = true;
            getTotalNQueens(row + 1, n, cols, diagnol1, diagnol2, res);
            cols[col] = false;
            diagnol1[index1] = false;
            diagnol2[index2] = false;
        }
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n \* 2 ^ n), 每一行里只能放一个queen, 每一列只有放和不放两种可能，所以n \* 2 ^ n，空间复杂度O(n)