leetcode--八皇后

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

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

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

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
题意很明白。就是四面八方不能有皇后
采用回溯方法
套路就是

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表
``

```java
class Solution {
    List<List<String>> res = new ArrayList();
    
    int n = 0;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        char[][] board = new char[n][n];
        for (int i = 0;i < n;i++) {
            Arrays.fill(board[i], '.');
        }
        dfs(0, board);
        return res;
    }
    private void dfs(int i, char[][] board) {
        if (i == n) {
            res.add(array2List(board));
        }
        for (int j = 0;j < n;j++) {
            // 如果会相撞
            if (!isValid(i, j, board)) {
                continue;
            }
            board[i][j] = 'Q';
            dfs(i + 1, board);
            board[i][j] = '.';
        }
    }

    private List<String> array2List(char[][] board) {
        List<String> list = new ArrayList();
        for (char[] c : board) {
            list.add(String.valueOf(c));
        }
        return list;
    }
    private boolean isValid(int row, int col, char[][] board) {
        
        // 列冲突
        for (int i = 0;i < row;i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 左上冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0;i--,j--) {
           if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 右上冲突
          for (int i = row - 1, j = col + 1; i >= 0 && j < n;i--,j++) {
           if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
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

数组填充 Arrays.fill(arr, ‘’);
char数组转字符串 String.valueOf(char[])