Skip to main content

52. N-Queens II

hard

Count the distinct solutions to the n-queens puzzle. Same recursion as N-Queens but returns a count — letting the bit-set optimization show off without the string-building overhead.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= n <= 9

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Same backtracking as N-Queens — just increment a counter on success.

Hint 2

Track cols / diag1 / diag2 sets; constant-time conflict check at each cell.

Hint 3

For tight performance, represent the three sets as integer bitmasks. Available = ~(cols | diag1 | diag2) & ((1 << n) - 1).

Hint 4

Iterate over the set bits of 'available' with bit = available & -available; recurse with (cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1); strip the bit.

Solution approach

Reveal approach

Standard backtracking like N-Queens but only carry a count. dfs(row, cols, diag1, diag2): if row == n, increment count and return. Otherwise compute available = ~(cols | diag1 | diag2) & ((1 << n) - 1). While available is non-zero, isolate the lowest set bit via bit = available & -available, recurse(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1), then strip: available &= available - 1. Shifting the diagonals left/right captures how a diagonal threat 'slides' one column over each row. The bitmask version runs in true O(n!) time but with a small constant that beats the set-based version on n up to 9.

Complexity

Time
O(n!)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Google

Practice these live with InterviewChamp.AI

Drill N-Queens II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →