[LeetCode]52 N皇后II

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

img

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: 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 = (~(col | pie | 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)