GoCalf Calf 的自留地 · 昙花一现

52. N-Queens II

Calf

Problem

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.

https://leetcode.cn/problems/n-queens-ii/description/

Example 1:

case1
case1

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

Test Cases

python 
class Solution:
    def totalNQueens(self, n: int) -> int:
solution_test.py下载完整源码
py 
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('n, expected', [
    (4, 2),
    (1, 1),

    (8, 92),
])
class Test:
    def test_solution(self, n, expected):
        sol = Solution()
        assert sol.totalNQueens(n) == expected

    def test_solution2(self, n, expected):
        sol = Solution2()
        assert sol.totalNQueens(n) == expected

Thoughts

跟 51. N-Queens 差不多，只是不用输出皇后的摆放结果，直接记录方案数量即可。

Code

Recursively

solution.py下载完整源码
py 
class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = [False] * n
        slashes = [False] * ((n<<1) - 1)
        backslashes = list(slashes)

        def backtrack(i: int) -> int:
            if i == n:
                return 1

            cnt = 0
            for j in range(n):
                if any((cols[j], slashes[i+j], backslashes[i-j])): continue
                cols[j] = slashes[i+j] = backslashes[i-j] = True
                cnt += backtrack(i + 1)
                cols[j] = slashes[i+j] = backslashes[i-j] = False

            return cnt

        return backtrack(0)

Iteratively

solution2.py下载完整源码
py 
class Solution:
    def totalNQueens(self, n: int) -> int:
        q: list[int] = [0] * n # q[i] = j, means there is a queue in (i, j).
        cols = [False] * n
        slashes = [False] * ((n<<1) - 1)
        backslashes = list(slashes)

        cnt = 0
        i = 0
        while q[0] < n:
            if q[i] == n:
                i -= 1
                cols[q[i]] = slashes[i+q[i]] = backslashes[i-q[i]] = False
                q[i] += 1
            elif any((cols[q[i]], slashes[i+q[i]], backslashes[i-q[i]])):
                q[i] += 1
            elif i < n - 1:
                cols[q[i]] = slashes[i+q[i]] = backslashes[i-q[i]] = True
                i += 1
                q[i] = 0
            else:
                cnt += 1
                i -= 1
                cols[q[i]] = slashes[i+q[i]] = backslashes[i-q[i]] = False
                q[i] += 1

        return cnt

递归版本可以去掉记录每行的皇后摆放的位置，因为每一层递归的局部变量里已经记录了该信息。而非递归版还是需要的。

评论需要 JavaScript。