[LeetCode] Problem 52 - N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

Example

Input: 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.

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

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

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

public int totalNQueens(int n) {
    column = new boolean[n];
    diagonal1 = new boolean[2 * n - 1];
    diagonal2 = new boolean[2 * n - 1];

    helper(n, 0);
    return result;
}


private void helper(int n, int x) {
    if (x == n) {
        result++;
        return;
    }

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

        update(n, x, y, true);
        helper(n, x + 1);
        update(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(int n, int x, int y, boolean put) {
    column[y] = put;
    diagonal1[x + y] = put;
    diagonal2[y - x + n - 1] = put;
}