Description:
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
Examples:
示例 1：
1
2
3
| 输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
|
示例 2：
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
}
|
