# 52. N-Queens II (H)

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

 

**Example 1:**

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

```
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
```

**Example 2:**

```
Input: n = 1
Output: 1
```

 

**Constraints:**

* `1 <= n <= 9`

### Solution:

**Version 1:**

不使用 boolean 数组来记录访问情况，直接暴力使用 for 循环来判断是否可以摆放在某个位置的写法。

java

```
class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        
        return search(new ArrayList<Integer>(), n);
    }
   
    private boolean isValid(List<Integer> cols, int colIndex) {
        int rowIndex = cols.size();
        for (int row = 0; row < cols.size(); row++) {
            int col = cols.get(row);
            if (col == colIndex || row + col == rowIndex + colIndex || 
                    row - col == rowIndex - colIndex) {
                return false;
            }
        }
        return true;
    }
    
    // search函数为搜索函数，n表示已经放置了n个皇后，cols 表示每个皇后所在的列
    private int search(List<Integer> cols, int n) {
        int rowIndex = cols.size();

        // 若已经放置了n个皇后表示出现了一种解法
        if (rowIndex == n) {
            return 1;
        }

        int sum = 0;
        // 枚举当前皇后放置的列，若不合法则跳过
        for (int colIndex = 0; colIndex < n; colIndex++) {
            if (!isValid(cols, colIndex)) {
                continue;
            }
            // 若合法则递归枚举下一行的皇后
            cols.add(colIndex);
            sum += search(cols, n);
            cols.remove(cols.size() - 1);
        }
        
        return sum;
    }
}
```

**Version 2:**

usedColumns\[row]每次循环是直接改数值,不是累加,所以不需要回溯,加了usedColumns\[row] = 0也不影响结果

```
public class Solution {
    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[] usedColumns = new int[n];
        placeQueen(usedColumns, 0);
        return sum;
    }
    public void placeQueen(int[] usedColumns, int row) {
        int n = usedColumns.length;
        
        if (row == n) {
            sum ++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(usedColumns, row, i)) {
                usedColumns[row] = i;
                placeQueen(usedColumns, row + 1);
            }
        }
    }
    public boolean isValid(int[] usedColumns, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (usedColumns[i] == col) {
                return false;
            }
            // 这里是判断对角线， 包含两种情况
            //row + col == i + usedColumns[i] 移项后就是row - i == usedColumns[i] - col 
            以及row - col == i - usedColumns[i] 移项后就是 row - i == col - usedColomns[i]
            if ((row - i) == Math.abs(col-usedColumns[i])) {
                return false;
            }
        }
        return true;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/4.depth-first-search/52.-n-queens-ii-h.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.