难度: Hard
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:
输入：4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
运行时间: 34 ms
内存: 16.4 MB
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def generate():
board=[]
for r in range(n):
c=pos[r]
row[c]='Q'
board.append( "".join(row) )
row[c]='.'
ret.append(board)
def solve(row, column, diag1, diag2):
if row==n:
generate()
else:
avail = ((1<<n)-1) & (~(column|diag1|diag2))
while avail:
colPos = avail&(-avail)
avail = avail&(avail-1)
col = bin(colPos-1).count("1")
pos[row]=col
solve(row+1, column|colPos, (diag1|colPos)<<1, (diag2|colPos)>>1)
ret = []
row=['.']*n
pos=[0]*n
solve(0, 0, 0, 0)
return ret
这个题解使用了回溯法和位运算来解决 N 皇后问题。算法的核心是通过递归尝试在每一行放置一个皇后，并使用位运算来高效地检查是否满足不同行、不同列和不同对角线的约束。其中，column、diag1 和 diag2 分别用来表示已占用的列、主对角线和副对角线。avail 变量用来表示当前行中可放置皇后的位置。通过位运算，算法高效地找到可放置皇后的位置，并递归地在下一行继续放置皇后。
时间复杂度: O(N! * N)
空间复杂度: O(N)
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def generate():
board=[]
for r in range(n):
c=pos[r]
row[c]='Q'
board.append( \".\".join(row) )
row[c]='.'
ret.append(board)
def solve(row, column, diag1, diag2):
if row==n:
generate()
else:
avail = ((1<<n)-1) & (~(column|diag1|diag2))
while avail:
colPos = avail&(-avail)
avail = avail&(avail-1)
col = bin(colPos-1).count(\"1\")
pos[row]=col
solve(row+1, column|colPos, (diag1|colPos)<<1, (diag2|colPos)>>1)
ret = []
row=['.'] * n
pos=[0] * n
solve(0, 0, 0, 0)
return ret
在算法中，位运算通过维护三个位掩码：`column`、`diag1` 和 `diag2`来检查约束。`column`位掩码用于标记已放置皇后的列；`diag1`位掩码用于标记主对角线（从左上到右下），每次向左移位（<<1）来更新当前行的主对角线约束；`diag2`位掩码用于标记副对角线（从右上到左下），每次向右移位（>>1）来更新当前行的副对角线约束。每行递归尝试放置皇后时，会计算`avail`变量，这个变量通过位运算`(~(column | diag1 | diag2)) & ((1 << n) - 1)`得出当前行哪些位置是可用的（即不在先前皇后的攻击范围内）。
使用位运算提高效率的主要原因是位运算可以在硬件级别上直接处理整数的位模式，这比在高级语言中处理数组或其他数据结构要快得多。位运算允许我们在常数时间内进行检查和更新操作，例如检查冲突、设置和清除位。与使用二维数组相比，位运算减少了存储空间的需求，因为它仅使用几个整数来表示所有的列和对角线状态，而不需要为棋盘的每个单元格分别存储状态。这样不仅提高了空间效率，还由于减少了内存访问，提高了时间效率。
在递归函数`solve`中，`avail`变量代表当前行中可放置皇后的位置。它的计算方式为`((1 << n) - 1) & (~(column | diag1 | diag2))`。这里，`(1 << n) - 1`生成一个长度为n的位掩码，所有位均为1，表示所有列理论上都是可放置的位置。`~(column | diag1 | diag2)`通过对已占用的列和对角线的位掩码取反，得到一个新的位掩码，其中1表示未被占用的列和对角线。最后通过这两个掩码的与操作，确保只考虑棋盘大小内的位置。这样，`avail`中的每个1都代表对应的列可以安全放置一个皇后。