LeetCode in Net
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) {
int count = 0;
Solve(0, n, new bool[n], new bool[2 * n], new bool[2 * n], ref count);
return count;
}
private void Solve(int row, int n, bool[] cols, bool[] d1, bool[] d2, ref int count) {
if (row == n) {
count++;
return;
}
for (int col = 0; col < n; col++) {
int id1 = col - row + n;
int id2 = col + row;
if (cols[col] || d1[id1] || d2[id2]) continue;
cols[col] = d1[id1] = d2[id2] = true;
Solve(row + 1, n, cols, d1, d2, ref count);
cols[col] = d1[id1] = d2[id2] = false;
}
}
}