N-Queens II LeetCode Solution

Last updated on October 9th, 2024 at 10:30 pm

Here, We see N-Queens II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Backtracking

Companies

Zenefits

Level of Question

Hard

N-Queens II LeetCode Solution

N-Queens II LeetCode Solution

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

1. N-Queens II Leetcode Solution 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);
        }        
    }
};

2. N-Queens II Leetcode Solution 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. N-Queens II Leetcode Solution 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    
};

4. N-Queens II Leetcode Solution 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
        
Scroll to Top