[LeetCode] Problem 51 - N-Queens

Posted on | In ,

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

ZfWYmq.png

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.

Example

Input: 4

Output: 

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

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Code

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
private boolean[] column;
private boolean[] diagonal1;
private boolean[] diagonal2;

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    column = new boolean[n];
    diagonal1 = new boolean[2 * n - 1];
    diagonal2 = new boolean[2 * n - 1];
    char[][] board = new char[n][n];

    for (int i = 0; i < n; i++)
        Arrays.fill(board[i], '.');

    helper(result, board, n, 0);
    return result;
}

private void helper(List<List<String>> result, char[][] board, int n, int x) {
    if (x == n) {
        List<String> list = new ArrayList<>();

        for (char[] row : board)
            list.add(new String(row));

        result.add(list);
        return;
    }

    for (int y = 0; y < n; y++) {
        if (!isValid(n, x, y))
            continue;

        update(board, n, x, y, true);
        helper(result, board, n, x + 1);
        update(board, n, x, y, false);
    }
}

private boolean isValid(int n, int x, int y) {
    return !column[y] && !diagonal1[x + y] && !diagonal2[y - x + n - 1];
}

private void update(char[][] board, int n, int x, int y, boolean put) {
    column[y] = put;
    diagonal1[x + y] = put;
    diagonal2[y - x + n - 1] = put;
    board[x][y] = put ? 'Q' : '.';
}