Description:

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。

Examples:

示例 1:

img

1
2
3
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

1
2
输入:n = 1
输出:1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func totalNQueens(n int) int {
res := 0
board := make([][]int, n)
for i:=0; i<n; i++{
board[i] = make([]int, n)
}
dfs(0, &board, &res, n)
return res

}

func dfs(row int, board *[][]int, res *int, n int){
if row > n-1{
*res += 1
return
}

for index:=0; index<n; index++{
if isValid(*board, row, index, n) {
(*board)[row][index] = 1
dfs(row+1, board, res, n)
(*board)[row][index] = 0
}else{
continue
}
}
}

func isValid(board [][]int, row, col, n int) bool{
if row == 0{
return true
}

for x:=0; x<row; x++{
// 判断列是否冲突
if board[x][col] == 1{
return false
}
// 判断对角线是否冲突
if x+n > row+col && x< row+col && board[x][row+col-x] == 1{
return false
}

if x+col-row <= n-1 && x+col >= row && board[x][x+col-row] == 1{
return false
}
}

return true
}