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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// 是否冲突
//  0/0  0/1  0/2  0/3
//  1/0  1/1  1/2  1/3
//  2/0  2/1  2/2  2/3
//  3/0  3/1  3/2  3/3
// 1. 判断是否属于同一列
// 2. 判断左边斜线上是否有冲突
//    *
//      *
//        *
// 2. 判断右边斜线上是否有冲突
//           *
//          *
//        *
func totalNQueens(n int) int {
    // 结果
    res := make([][]string, 0)
    // 初始化path
    path := make([]string, 0)
    for i := 0; i< n ; i++ {
        path = append(path, strings.Repeat(".", n))
    }
    // 从第一行开始
    row := 0

    backtrack(row, path, &res)

    return len(res)
}

func backtrack(row int, path []string, res *[][]string) {
    if len(path) == row {
        temp := make([]string, len(path))
        copy(temp, path)
        *res = append(*res, temp)
        return
    }

    n := len(path)
    for col := 0; col<n; col++ {
        if !isConflict(path, row, col) {
            continue
        }

        rowBytes := []byte(path[row])
        rowBytes[col] = 'Q'
        path[row] = string(rowBytes)

        backtrack(row+1, path, res)

        rowBytes[col] = '.'
        path[row] = string(rowBytes)
    }
}

func isConflict(path []string, row, col int) bool {
    // 同一列
    n := len(path)
    for i := 0; i < n; i++ {
        if path[i][col] == 'Q' {
            return false
        }
    }

    // 左上方
    r := row-1
    c := col-1 
    for r >= 0 && c >= 0 {
        if path[r][c] == 'Q' {
            return false
        }
        c = c - 1
        r = r - 1
    }

    // 右上方
    r = row-1
    c = col+ 1
    for r >=0 && c < n {
        if path[r][c] == 'Q' {
            return false
        }
        c = c + 1
        r = r - 1
    }
    
    return true
}