Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
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.."] ]
class Solution: def totalNQueens(self, n: int) -> int: self.result=[] self.pie=set();self.na=set();self.cols=set() self._dfs(n,0,[]) return len(self.result) def _dfs(self,n,row,c): if n<1:return [] if row>=n: self.result.append(c) return for col in range(n): if col in self.cols or col-row in self.pie or col+row in self.na: continue self.cols.add(col) self.pie.add(col-row) self.na.add(col+row) self._dfs(n,row+1,c) self.cols.remove(col) self.pie.remove(col-row) self.na.remove(col+row)
class Solution: def totalNQueens(self, n: int) -> int: if n < 1:return [] self.count = 0 self._dfs(n,0,0,0,0) return self.count def _dfs(self,n,row,col,pie,na): if row>=n: self.count +=1 return bits = (~(pie|col|na)&(1<<n)-1) while bits: p = bits & (-bits) self._dfs(n,row+1,col|p,(pie|p)<<1,(na|p)>>1) bits = bits & (bits-1) row=0,col=0,pie=0,na=0 bits= 15 p= 1 row=1,col=1,pie=2,na=0 bits= 12 p= 4 row=2,col=5,pie=12,na=2 bits= 0 p= 8 row=2,col=9,pie=20,na=4 bits= 2 p= 2 row=3,col=11,pie=44,na=3 bits= 0 p= 2 row=1,col=2,pie=4,na=1 bits= 8 p= 8 row=2,col=10,pie=24,na=4 bits= 1 p= 1 row=3,col=11,pie=50,na=2 bits= 4 p= 4 p= 4 row=1,col=4,pie=8,na=2 bits= 1 p= 1 row=2,col=5,pie=18,na=1 bits= 8 p= 8 row=3,col=13,pie=52,na=4 bits= 2 p= 2 p= 8 row=1,col=8,pie=16,na=4 bits= 3 p= 1 row=2,col=9,pie=34,na=2 bits= 4 p= 4 row=3,col=13,pie=76,na=3 bits= 0 p= 2 row=2,col=10,pie=36,na=3 bits= 0
原文：https://www.cnblogs.com/ybxw/p/12940135.html
