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
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n!) | O(n) |
Java | O(n!) | O(n) |
JavaScript | O(n!) | O(n) |
Python | O(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).