51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[[“Q”]]

提示：

1 <= n <= 9

解法一：回溯

 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


func solveNQueens(n int) [][]string {
    var ans [][]string
    tmp := make([][]byte, n)
    for i := 0; i < n; i++ {
        tmp[i] = make([]byte, n)
        for j := 0; j < n; j++ {
            tmp[i][j] = '.'
        }
    }
    columns := make([]bool, n)
    leftToR := make(map[int]bool)
    rightToL := make(map[int]bool)
    var backtracking func(row int)
    backtracking = func(row int) {
        if row == n {
            t := make([]string, n)
            for i := 0; i < n; i++ {
                t[i] = string(tmp[i])
            }
            ans = append(ans, t)
            return
        }

        for col := 0; col < n; col++ {
            if !columns[col] && !leftToR[col-row] && !rightToL[col+row] {
                columns[col] = true
                leftToR[col-row] = true
                rightToL[col+row] = true

                tmp[row][col] = 'Q'
                backtracking(row + 1)
                tmp[row][col] = '.'

                columns[col] = false
                leftToR[col-row] = false
                rightToL[col+row] = false
            }
        }
    }
    backtracking(0)
    return ans
}