0052. N-Queens II.md

52. N-Queens II

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

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, ld, rd, col):
            nonlocal count
            # If all rows are filled, increment count and return
            if row == n:
                count += 1
                return
    
            # Calculate available positions for the current row
            bits = ~(ld | rd | col) & ((1 << n) - 1)
    
            # Iterate through available positions
            while bits:
                # Choose the rightmost available position
                p = bits & -bits
                # Clear the rightmost set bit in bits
                bits &= bits - 1
                # Recursively call backtrack for the next row with updated positions
                backtrack(row + 1, (ld | p) << 1, (rd | p) >> 1, col | p)
    
        count = 0
        # Start the backtracking process from the first row
        backtrack(0, 0, 0, 0)
        return count

每个二进制位对应棋盘的一列，而不是一行


bits - 1 表示对二进制数 bits 进行减法操作，即将 bits 的所有位都减去 1。

### 示例：N = 4
---------- Row 0 ----------
ld (左对角线): 0000
rd (右对角线): 0000
col (列): 0000
ld | rd | col: 0000
~(ld | rd | col): 1111
(1 << n) - 1: 1111
bits: 1111

Placing queen at (row: 0, p: 0001)
p = bits & -bits = 1111 & 0001 = 0001
After placing queen: 
ld = (ld | p) << 1 = (0000 | 0001) << 1: 0010 # 
rd = (rd | p) >> 1 = (0000 | 0001) >> 1: 0000
col = col | p = 0000 | 0001: 0001

---------- Row 1 ----------
ld (左对角线): 0010
rd (右对角线): 0000
col (列): 0001
ld | rd | col: 0011
~(ld | rd | col): 1100
(1 << n) - 1: 1111
bits: 1100

Placing queen at (row: 1, p: 0100)
After placing queen:
ld = (0010 | 0100) << 1: 1100
rd = (0000 | 0100) >> 1: 0010
col = 0001 | 0100: 0101