0052-n-queens-ii¶
Try it on leetcode
Description¶
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:
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(Python)¶
class Solution:
def __init__(self):
self.lookup = {}
for i in range(1, 10):
self.lookup[i] = self.__totalNQueens(i)
def totalNQueens(self, n: int) -> int:
return self.lookup[n]
def __totalNQueens(self, n: int) -> int:
board = [[0] * n for _ in range(n)]
res = 0
def is_valid(row, col):
# Check same column
for r in range(row):
if board[r][col] == 1:
return False
# Check upper-left diagonal
r, c = row - 1, col - 1
while r >= 0 and c >= 0:
if board[r][c] == 1:
return False
r -= 1
c -= 1
# Check upper-right diagonal
r, c = row - 1, col + 1
while r >= 0 and c < n:
if board[r][c] == 1:
return False
r -= 1
c += 1
return True
def backtrack(row):
if row == n:
return 1
count = 0
for col in range(n):
if is_valid(row, col):
board[row][col] = 1
count += backtrack(row + 1)
board[row][col] = 0
return count
return backtrack(0)