LeetCode-in-Java
52. N-Queens II
Hard
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 9
Solution
public class Solution {
public int totalNQueens(int n) {
boolean[] row = new boolean[n];
boolean[] col = new boolean[n];
boolean[] diagonal = new boolean[n + n - 1];
boolean[] antiDiagonal = new boolean[n + n - 1];
return totalNQueens(n, 0, row, col, diagonal, antiDiagonal);
}
private int totalNQueens(
int n,
int r,
boolean[] row,
boolean[] col,
boolean[] diagonal,
boolean[] antiDiagonal) {
if (r == n) {
return 1;
}
int count = 0;
for (int c = 0; c < n; c++) {
if (!row[r] && !col[c] && !diagonal[r + c] && !antiDiagonal[r - c + n - 1]) {
row[r] = col[c] = diagonal[r + c] = antiDiagonal[r - c + n - 1] = true;
count += totalNQueens(n, r + 1, row, col, diagonal, antiDiagonal);
row[r] = col[c] = diagonal[r + c] = antiDiagonal[r - c + n - 1] = false;
}
}
return count;
}
}