N皇后

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

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

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

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

示例 1：

img

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

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9

使用DFS搜索每一种情况。

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
class Solution {
    private List<List<String>> res = new ArrayList<>();
    //path[i] = j表示第i行放在第j列
    private int[] path;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        path = new int[n];
        this.n = n;
        //从第0行开始
        dfs(0);
        return res;
    }
	//
    private void dfs(int i) {
        if (i == n) {
            res.add(convert());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (check(i, j)) {
                path[i] = j;
                dfs(i + 1);
                //不需要回溯，因为会被覆盖
            }
        }
    }

    // 判断i行j列能否放置
    private boolean check(int i, int j) {
        for (int k = 0; k < i; k++) {
            //先判断之前的列是否有重复，判断对角线使用行之差的绝对值和列之差的绝对值是否相等
            if (path[k] == j || Math.abs(k - i) == Math.abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }
	//将path数组zhuan
    private List<String> convert() {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[path[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}