Description
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.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Solutions
1. Backtracking
# Time: O(n^2)
# Space: O(n)
class Solution:
def totalNQueens(self, n: int) -> int:
if n <= 0:
return []
res = [0]
self.dfs(n, [], [], [], res)
return res[0]
def dfs(self, n, xydiff_diag, xysum_diag, queens, res):
# q is the current row index, queen store every column position of a queen
r = len(queens)
if r == n:
res[0] += 1
return
# check every column position, c is the test column index
for c in range(n):
if c in queens or r - c in xydiff_diag or r + c in xysum_diag:
continue
self.dfs(n, xydiff_diag + [r - c], xysum_diag + [r + c], queens + [c], res)
# 9/9 cases passed (44 ms)
# Your runtime beats 94.04 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)