这个题解使用了回溯法和位运算来解决 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