N-Queens II LeetCode Solution

Last updated on January 19th, 2025 at 06:06 pm

Here, we see a N-Queens II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking

Companies

Zenefits

Level of Question

Hard

N-Queens II LeetCode Solution

N-Queens II LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Backtracking with Bitmasking”. Backtracking is used to explore all possible configurations of placing queens on the chessboard, and bitmasking is used to efficiently track the state of columns, left diagonals, and right diagonals.

3. Code Implementation in Different Languages

3.1 N-Queens II C++

class Solution {
public:
    int totalNQueens(int n) {
        ans = 0;
        place(0,0,0,0,n);
        return ans;
    }
    
private:
    int ans;
    
    void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }        
    }
};

3.2 N-Queens II Java

class Solution {
    int ans;
    public int totalNQueens(int n) {
        ans = 0;
        place(0,0,0,0,n);
        return ans;
    }
    
    private void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if ((vert & vmask) + (ldiag & lmask) + (rdiag & rmask) > 0) continue;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }        
    }
}

3.3 N-Queens II JavaScript

var totalNQueens = function(n) {
    let ans = 0
    
    const place = (i, vert, ldiag, rdiag) => {
        if (i === n) ans++
        else for (let j = 0; j < n; j++) {
            let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (n-i-1+j)
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
        }
    }

    place(0,0,0,0)
    return ans    
};

3.4 N-Queens II Python

class Solution(object):
    def totalNQueens(self, n):
        self.res = 0
        self.dfs([-1]*n, 0)
        return self.res
    
    def dfs(self, nums, index):
        if index == len(nums):
            self.res += 1
            return #backtracking
        for i in range(len(nums)):
            nums[index] = i
            if self.valid(nums, index):
                self.dfs(nums, index+1)
    
    def valid(self, nums, n):
        for i in range(n):
            if nums[i] == nums[n] or abs(nums[n]-nums[i]) == n-i:
                return False
        return True
        

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n!)O(n)
JavaO(n!)O(n)
JavaScriptO(n!)O(n)
PythonO(n!)O(n)
  • The C++, Java, and JavaScript implementations use bitmasking to efficiently track column and diagonal conflicts, reducing the overhead of checking conflicts compared to the Python implementation.
  • The Python implementation uses a more traditional backtracking approach with an array (nums) to track queen placements and a helper function (valid) to check conflicts. This is less efficient than bitmasking but easier to understand.
  • All implementations use backtracking with pruning to avoid exploring invalid configurations, significantly reducing the number of recursive calls compared to a naive approach.
  • The time complexity is O(N!) due to the backtracking approach with pruning.
  • The recursion stack depth is N, and the bitmask variables use constant space. Thus, the space complexity is O(N).
Scroll to Top