n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：1提示：
- 1 <= n <= 9
解答：
// 昨天的代码拿过来，对结果求一下长度就可以
var solutions [][]string
func totalNQueens(n int) int {
solutions = [][]string{}
queens := make([]int, n)
for i := 0; i < n; i++ {
queens[i] = -1
}
solve(queens, n, 0, 0, 0, 0)
return len(solutions)
}
func solve(queens []int, n, row, columns, diagonals1, diagonals2 int) {
if row == n {
board := generateBoard(queens, n)
solutions = append(solutions, board)
return
}
availablePositions := ((1 << n) - 1) & (^(columns | diagonals1 | diagonals2))
for availablePositions != 0 {
position := availablePositions & (-availablePositions)
availablePositions = availablePositions & (availablePositions - 1)
column := bits.OnesCount(uint(position - 1))
queens[row] = column
solve(queens, n, row+1, columns|position, (diagonals1|position)>>1, (diagonals2|position)<<1)
queens[row] = -1
}
}
func generateBoard(queens []int, n int) []string {
var board []string
for i := 0; i < n; i++ {
row := make([]byte, n)
for j := 0; j < n; j++ {
row[j] = '.'
}
row[queens[i]] = 'Q'
board = append(board, string(row))
}
return board
}官方解答：
1.基于集合的回溯
func totalNQueens(n int) (ans int) {
columns := make([]bool, n)
diagonals1 := make([]bool, 2*n-1)
diagonals2 := make([]bool, 2*n-1)
var backtrack func(int)
backtrack = func(row int) {
if row == n {
ans++
return
}
for col, hasQueen := range columns {
d1, d2 := row+n-1-col, row+col
if hasQueen || diagonals1[d1] || diagonals2[d2] {
continue
}
columns[col] = true
diagonals1[d1] = true
diagonals2[d2] = true
backtrack(row + 1)
columns[col] = false
diagonals1[d1] = false
diagonals2[d2] = false
}
}
backtrack(0)
return
}2.基于位运算的回溯
func totalNQueens(n int) (ans int) {
var solve func(row, columns, diagonals1, diagonals2 int)
solve = func(row, columns, diagonals1, diagonals2 int) {
if row == n {
ans++
return
}
availablePositions := (1<<n - 1) &^ (columns | diagonals1 | diagonals2)
for availablePositions > 0 {
position := availablePositions & -availablePositions
solve(row+1, columns|position, (diagonals1|position)<<1, (diagonals2|position)>>1)
availablePositions &^= position
}
}
solve(0, 0, 0, 0)
return
}