按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：[["Q"]]提示：
- 1 <= n <= 9
解题：
每行一个，每行的位置不同，每个皇后的坐标y-x的差值的绝对值不同，代码没写出来官方解答：
1.基于集合的回溯
var solutions [][]string
func solveNQueens(n int) [][]string {
solutions = [][]string{}
queens := make([]int, n)
for i := 0; i < n; i++ {
queens[i] = -1
}
columns := map[int]bool{}
diagonals1, diagonals2 := map[int]bool{}, map[int]bool{}
backtrack(queens, n, 0, columns, diagonals1, diagonals2)
return solutions
}
func backtrack(queens []int, n, row int, columns, diagonals1, diagonals2 map[int]bool) {
if row == n {
board := generateBoard(queens, n)
solutions = append(solutions, board)
return
}
for i := 0; i < n; i++ {
if columns[i] {
continue
}
diagonal1 := row - i
if diagonals1[diagonal1] {
continue
}
diagonal2 := row + i
if diagonals2[diagonal2] {
continue
}
queens[row] = i
columns[i] = true
diagonals1[diagonal1], diagonals2[diagonal2] = true, true
backtrack(queens, n, row+1, columns, diagonals1, diagonals2)
queens[row] = -1
delete(columns, i)
delete(diagonals1, diagonal1)
delete(diagonals2, diagonal2)
}
}
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
}2.基于位运算的回溯
var solutions [][]string
func solveNQueens(n int) [][]string {
solutions = [][]string{}
queens := make([]int, n)
for i := 0; i < n; i++ {
queens[i] = -1
}
solve(queens, n, 0, 0, 0, 0)
return 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
}