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:
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:
Test Cases
1
2
| class Solution:
def totalNQueens(self, n: int) -> int:
|
solution_test.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def totalNQueens(self, n: int) -> int:
cols = [False] * n
slashes = [False] * ((n<<1) - 1)
backslashes = list(slashes)
def backtrace(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 += backtrace(i + 1)
cols[j] = slashes[i+j] = backslashes[i-j] = False
return cnt
return backtrace(0)
|
Iteratively
solution2.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution:
def totalNQueens(self, n: int) -> int:
q: list[int] = [0] * n
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
|
递归版本可以去掉记录每行的皇后摆放的位置，因为每一层递归的局部变量里已经记录了该信息。而非递归版还是需要的。
