Skip to main content

51. N-Queens

hard

Place n non-attacking queens on an n x n chessboard and return every distinct arrangement. The canonical hard backtracking problem — the one that finally rewards constant-time conflict checks via column and diagonal sets.

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 all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Constraints

  • 1 <= n <= 9

Examples

Example 1

Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Example 2

Input
n = 1
Output
[["Q"]]

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

Place one queen per row. Row index is your recursion depth.

Hint 2

Track three sets: occupied columns, occupied positive diagonals (row - col), occupied negative diagonals (row + col).

Hint 3

At row r, try every column c that isn't in any of the three sets. Place, recurse to r + 1, unplace.

Hint 4

When r == n, build the string representation and append to result.

Solution approach

Reveal approach

Place one queen per row to avoid same-row conflicts by construction. Maintain three sets: cols (occupied columns), diag1 (occupied r - c), diag2 (occupied r + c). dfs(row): if row == n, build the n strings ('.'*c + 'Q' + '.'*(n-c-1)) for each placement and append to result. Otherwise, for c in [0, n): if c in cols or row - c in diag1 or row + c in diag2, skip. Otherwise mark all three sets, recurse(row + 1), unmark. Constant-time conflict checks are what make this tractable. Time is O(n!) (worst-case branching shrinks fast as constraints accumulate); space O(n).

Complexity

Time
O(n!)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • constraint-satisfaction

Related problems

Asked at

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

  • Amazon
  • Apple
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →