51. N-Queens

发表于 | 分类于

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

解法1： DFS, O(N^N )

每一行有Ｎ个位置可以尝试，一共有Ｎ个行，不同的摆放方法是N^N
要注意的是在存储一个特定的摆放时，一个list就能解决问题。每一个元素对应的是每一行的列的位置。
比较直接的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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> board = new ArrayList<>();
        dfs(res, board, n);
        return res;
    }
    /*
        Create a board from the configuration
    */
    private List<String> draw(List<Integer> board) {
        List<String> res = new ArrayList<>();
        int n = board.size();
        for (int i = 0; i < board.size(); i++) {
            char[] chs = new char[n];
            Arrays.fill(chs, '.');
            chs[board.get(i)] = 'Q';
            res.add(new String(chs));
        }
        return res;
    }
    /*
        Check if a board is valid
    */
    private boolean isValid(List<Integer> board) {
        if (board.size() == 0) {
            return true;
        }
        for (int i = 0; i < board.size() - 1; i++) {
            for (int j = i + 1; j < board.size(); j++) {
                if (board.get(i) == board.get(j)) return false;
                if (i + board.get(i) == j + board.get(j)) return false;
                if (j - i == board.get(j) - board.get(i)) return false;
            }
        }
       return true;
    }
    private void dfs(List<List<String>> res, List<Integer> board, int n) {
        if (!isValid(board)) {
            return;
        }
        if (board.size() == n) {
            List<String> solution = draw(board);
            res.add(solution);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (board.contains(i)) {
                continue;
            }
            board.add(i);
            dfs(res, board, n);
            board.remove(board.size() - 1);
        }
    }
}