## DFS&BFS - 52. N-Queens II

Updated on with 0 views and 0 comments

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:

``````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.."]
]
``````

go：

``````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]
}
}
}
``````