In this post, we are going 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.
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
Now, let’s see the leetcode solution of N-Queens II Leetcode Solution.
N-Queens II Leetcode Solution 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 Solution 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 Solution 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 Chase2learn This tutorial is only for Educational and Learning purposes.
