[LeetCode] 52. N-Queens II

Posted on | In

Problem

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

52. N-Queens II

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

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

Explanation

  1. Similar to 51. N-Queens, but this time we only need to print out the number of result, so we can change the base case to be if all the elements of corArr are filled, then we increase res and return.

Solution

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
class Solution {
    int res = 0;
    void helper(int[] colArr, int row) {
        if (row == colArr.length) {
            res++;
            return;
        }
        for (int i = 0; i < colArr.length; i++) {
            if (isValid(colArr, row, i)) {
                colArr[row] = i;
                helper(colArr, row+1);
                colArr[row] = -1;
            }
        }
    }
    boolean isValid(int[] colArr, int row, int colInd) {
        for (int i = 0; i < row; i++) {
            if (colArr[i] == colInd || Math.abs(row-i) == Math.abs(colInd - colArr[i])) {
                return false;
            }
        }
        return true;
    }
    public int totalNQueens(int n) {
        int[] colArr = new int[n];
        Arrays.fill(colArr, -1);
        helper(colArr, 0);
        return res;
    }
}