In this post, you will know how to solve the N-Queens II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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
N-Queens II Leetcode Solutions in Python
class Solution:
def totalNQueens(self, n: int) -> int:
ans = 0
cols = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)
def dfs(i: int) -> None:
nonlocal ans
if i == n:
ans += 1
return
for j in range(n):
if cols[j] or diag1[i + j] or diag2[j - i + n - 1]:
continue
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = True
dfs(i + 1)
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = False
dfs(0)
return ans
N-Queens II Leetcode Solutions in CPP
class Solution {
public:
int totalNQueens(int n) {
int ans = 0;
dfs(n, 0, vector<bool>(n), vector<bool>(2 * n - 1), vector<bool>(2 * n - 1),
ans);
return ans;
}
private:
void dfs(int n, int i, vector<bool>&& cols, vector<bool>&& diag1,
vector<bool>&& diag2, int& ans) {
if (i == n) {
++ans;
return;
}
for (int j = 0; j < n; ++j) {
if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
continue;
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
dfs(n, i + 1, move(cols), move(diag1), move(diag2), ans);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
}
}
};
N-Queens II Leetcode Solutions in Java
class Solution {
public int totalNQueens(int n) {
dfs(n, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
return ans;
}
private int ans = 0;
private void dfs(int n, int i, boolean[] cols, boolean[] diag1, boolean[] diag2) {
if (i == n) {
++ans;
return;
}
for (int j = 0; j < cols.length; ++j) {
if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
continue;
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
dfs(n, i + 1, cols, diag1, diag2);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
}
}
}
Note: This problem N-Queens II is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
NEXT: Median of Two Sorted Arrays Leetcode Solution
