forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0051-n-queens.go
32 lines (31 loc) · 734 Bytes
/
0051-n-queens.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
package main
func solveNQueens(n int) [][]string {
ans, curr := make([][]string, 0), make([]string, 0)
column, diag1, diag2 := make(map[int]int), make(map[int]int), make(map[int]int)
var backtrack func(y int)
backtrack = func(y int) {
if y == n {
ans = append(ans, append([]string{}, curr...))
}
for x := 0; x < n; x++ {
if column[x] > 0 || diag1[x+y] > 0 || diag2[n+x-y-1] > 0 {
continue
}
column[x], diag1[x+y], diag2[n+x-y-1] = 1, 1, 1
s := ""
for i := 0; i < n; i++ {
if i == x {
s += "Q"
} else {
s += "."
}
}
curr = append(curr, s)
backtrack(y + 1)
column[x], diag1[x+y], diag2[n+x-y-1] = 0, 0, 0
curr = curr[:len(curr)-1]
}
}
backtrack(0)
return ans
}