52. N-Queens II
The n-queens puzzle is the problem of placing n queens on an n_×_n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
代码语言：javascript复制Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]思路：
这一题n皇后与51题区别是只用求出组合种数，而51题要求输出所有结果，做法是一样，都是dfs递归回溯，使用列和对角线是否能摆放皇后来剪枝。
代码：
go：
代码语言：javascript复制var col, dia1, dia2 []bool
func totalNQueens(n int) int {
var res int
col = make([]bool, n)
dia1 = make([]bool, 2*n-1)
dia2 = make([]bool, 2*n-1)
putQueen(n, 0, []int{}, &res)
return res
}
// 尝试在一个n皇后问题中，摆放第index行的皇后位置
func putQueen(n int, index int, row []int, res *int) {
if index == n {
*res
return
}
for i := 0; i < n; i {
if !col[i] && !dia1[index i] && !dia2[index-i n-1] { // 对应列、对角线、反对角线没有皇后
row = append(row, i)
col[i] = true
dia1[index i] = true
dia2[index-i n-1] = true
// 尝试在index 1 摆放皇后
putQueen(n, index 1, row, res)
col[i] = false
dia1[index i] = false
dia2[index-i n-1] = false
row = row[:len(row)-1]
}
}
}
