N 皇后 II - 位图
var (
N int
ans int
)
func totalNQueens(n int) int {
N = n
ans = 0
backtracking(0, 0, 0 ,0)
return ans
}
// curN 当前列
// columns 位图（列）
// diagonals1 int 位图（对角线：左上到右下）
// diagonals2 int 位图（对角线：右上到左下）
func backtracking(curN, columns, diagonals1, diagonals2 int) {
if curN == N {
ans++
return
}
availablePositions := (1 << N - 1) &^ (columns | diagonals1 | diagonals2)
// ((1 << N) - 1) & (^(columns | diagonals1 | diagonals2))
for availablePositions > 0 {
// Brian Kernighan 算法：提取出二进制状态中最右侧的 1
pos := availablePositions & -availablePositions
backtracking(curN + 1, columns | pos, (diagonals1 | pos) << 1, (diagonals2 | pos) >> 1)
availablePositions &^= pos // 移除比特位
}
}curN 也不必要，可以用位运算代替：
var (
ans int
limit int // 需要放置皇后的位置
)
func totalNQueens(n int) int {
ans = 0
// 最小 n 位是 1，其他位是 0
limit = 1 << n - 1
backtracking(0, 0 ,0)
return ans
}
// columns 位图（列）
// diagonals1 int 位图（对角线：左上到右下）
// diagonals2 int 位图（对角线：右上到左下）
func backtracking(columns, diagonals1, diagonals2 int) {
if columns == limit { // 需要放置皇后的位置都放好了皇后
ans++
return
}
availablePositions := limit &^ (columns | diagonals1 | diagonals2)
// ((1 << N) - 1) & (^(columns | diagonals1 | diagonals2))
for availablePositions > 0 {
// Brian Kernighan 算法：提取出二进制状态中最右侧的 1
pos := availablePositions & -availablePositions
backtracking(columns | pos, (diagonals1 | pos) << 1, (diagonals2 | pos) >> 1)
availablePositions &^= pos // 移除比特位
}
}