forked from luox78/go-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
totalq_test.go
52 lines (43 loc) · 962 Bytes
/
totalq_test.go
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
51
52
package bit_test
import "testing"
func TestTotalNQueens(t *testing.T) {
// 给定一个整数 n,返回 n 皇后不同的解决方案的数量。
// 示例:
// 输入: 4
// 输出: 2
// 解释: 4 皇后问题存在如下两个不同的解法。
// [
// [".Q..", // 解法 1
// "...Q",
// "Q...",
// "..Q."],
// ["..Q.", // 解法 2
// "Q...",
// "...Q",
// ".Q.."]
// ]
t.Log(totalNQueens(4))
t.Log(totalNQueens(8))
t.Log(totalNQueens(1))
}
func totalNQueens(n int) int {
var count int
bitDFS(n, 0, 0, 0, 0, &count)
return count
}
func bitDFS(n, row, col, left, right int, count *int) {
// 递归终止条件
if row >= n {
*count++
return
}
// 获取所有可以放的位
bits := (^(col | left | right)) & ((1 << uint(n)) - 1)
for bits > 0 {
// 得到1个空位
p := bits & -bits
bitDFS(n, row+1, col|p, (left|p)<<1, (right|p)>>1, count)
// 去掉放置的空位
bits &= bits - 1
}
}