52. N-Queens II LeetCode Solution

Last updated: February 14, 2025

In this guide, you will get 52. N-Queens II LeetCode Solution with the best time and space complexity. The solution to N-Queens II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
N-Queens II solution in C++
N-Queens II solution in Java
N-Queens II solution in Python
Additional Resources

Problem Statement of N-Queens II

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

Complexity Analysis

Time Complexity: O(n \cdot n!)
Space Complexity: O(n \cdot n!)

52. N-Queens II LeetCode Solution in C++

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, std::move(cols), std::move(diag1), std::move(diag2), ans);
      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
    }
  }
};
/* code provided by PROGIEZ */

52. 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;
    }
  }
}
// code provided by PROGIEZ

52. 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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents