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.."] ]
My code:
class Solution:
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
self.count=0
self.n=n
self.DFS([],[],[])
return self.count
def DFS(self,quenes,xy_diff,xy_sum):
p=len(quenes)
#print('executing %d'%p)
if len(quenes)==self.n:
self.count+=1
return
for i in range(self.n):
if i not in quenes and (i-p) not in xy_diff and (i+p) not in xy_sum:
self.DFS(quenes+[i],xy_diff+[i-p],xy_sum+[i+p])