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.
- code
def totalNQueens(self, n):
self.res = 0
self.dfs([-1]*n, 0)
return self.res
def dfs(self, nums, index):
if index == len(nums):
self.res += 1
return #backtracking
for i in range(len(nums)):
nums[index] = i
if self.valid(nums, index):
self.dfs(nums, index+1)
def valid(self, nums, n):
for i in range(n):
if nums[i] == nums[n] or abs(nums[n]-nums[i]) == n-i:
return False
return True
Python recursive dfs solution with comments. - LeetCode Discuss
- code
class Solution:
def totalNQueensHelp(self, n, i):
ct=0
for j in range (n):
if (j not in self.s1) and (i-j not in self.s2) and (i+j not in self.s3):
if (i==n-1):
return 1
self.s1.add(j)
self.s2.add(i-j)
self.s3.add(i+j)
ct+=self.totalNQueensHelp(n,i+1)
self.s1.discard(j)
self.s2.discard(i-j)
self.s3.discard(i+j)
return ct
def totalNQueens(self, n: int) -> int:
self.s1 = set()
self.s2 = set()
self.s3 = set()
return self.totalNQueensHelp(n,0)