Is N-Queens II easy or hard?

N-Queens II is classified as a Hard problem because it requires designing a backtracking search with efficient pruning. Understanding how diagonals are represented and optimized using sets or bitmasks is the key difficulty.

N-Queens II Python/Java solution

Python and Java implementations usually use recursive backtracking. Python solutions often rely on sets or bitmasks for column and diagonal tracking, while Java solutions commonly use boolean arrays or bit operations for better performance.

How to solve N-Queens II in O(n)?

N-Queens II cannot be solved in O(n) time because the problem requires exploring combinations of queen placements. The best known approaches use backtracking with pruning, which runs in roughly O(n!) time. Bitmasking reduces constant overhead but does not change the theoretical complexity.

What is the best approach for N-Queens II?

Backtracking with pruning is the standard solution. Track used columns, main diagonals, and anti-diagonals while placing queens row by row. This reduces the search space dramatically compared to brute force. An optimized variant uses bitmasking for faster conflict checks.

Is N-Queens II asked at Google/Amazon/Meta?

N-Queens style problems frequently appear in technical interviews at companies like Google, Amazon, and Meta because they test backtracking, recursion, and constraint pruning. Variants may ask for the number of solutions or the actual board configurations.

What data structure is used in N-Queens II?

Typical implementations use sets or boolean arrays to track occupied columns and diagonals. Optimized solutions replace these structures with integer bitmasks so column and diagonal conflicts can be checked using fast bit operations.

What is the time complexity of N-Queens II?

The time complexity is approximately O(n!) because each row tries multiple column placements and recursively explores valid configurations. Pruning with column and diagonal checks prevents exploring invalid branches, which significantly reduces the practical search space.

Description Solution Video 13:58

52. N-Queens II

Hard79.5% acceptance10 companies

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

Asked at 10 companies

Zenefits Liftoff Deutsche Bank Walmart Labs Snowflake

Google Amazon Microsoft Meta Bloomberg

Topics

Backtracking

13:58

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

52. N-Queens II

Asked at 10 companies

Topics

Similar problems