HardArrayBacktrackingAlgorithm XUpdated Sep 2026

51. N-Queens

Asked at Google

Difficulty

Hard

Time

O(n!)

Space

O(n^2)

Pattern

Array

Companies

1

Problem

You have an n x n chessboard and n queens. A queen attacks every square in the same row, the same column, and both diagonals. Your job is to place all n queens so that no queen attacks any other queen.

Return all distinct valid boards. Each board is a list of n strings of length n, where 'Q' marks a queen and '.' marks an empty square. You may return the boards in any order.

Because a queen attacks along its whole row, each row can hold exactly one queen. So we can decide the board one row at a time: pick a column for row 0, then a column for row 1, and so on. If a choice makes a later row impossible, we undo it and try the next column.

Queens must not share a line

board01230123.Q.....QQ.....Q.One queen per row, one per column, and no two on adiagonal
On a 4x4 board the queens at (0,1), (1,3), (2,0), (3,2) never share a row, column or diagonal.

Constraints

  • ●1 <= n <= 9

Examples

Example 1
Inputn = 4
Output[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
WhyWith 4 queens there are exactly two valid boards. In the first board the queens sit at (row 0, col 1), (1, 3), (2, 0), (3, 2). Check any pair: no two share a row, a column, or a diagonal. The second board is the mirror image of the first, so it is a different board and counts separately.
Example 2
Inputn = 1
Output[["Q"]]
WhyA single queen on a 1x1 board attacks nothing, so the one-square board is valid.

Asked At

1 companies
CompanyDifficulty
GoogleHardView all Google questions →

How to Think About It

1

Try placing queens row by row, checking each column for validity

2

Use three sets to track occupied columns, positive diagonals, and negative diagonals

3

Prune early by checking if current partial placement is still valid

4

Backtrack immediately when a conflict is detected rather than continuing

5

Use Algorithm X with dancing links for optimal performance on large N

Optimal Approach

Use backtracking with three sets to track attacked positions. Place queens row by row. For each row, try every column. If a position is not attacked (not in same column, positive diagonal, or negative diagonal), place the queen and recurse to the next row. If placing a queen leads to a valid complete board, record the solution. Backtrack by removing the queen and trying the next column. The diagonal invariant is that all cells on the same positive diagonal share row+col, and all cells on the same negative diagonal share row-col.

Backtrack row by row

row 001230123.Q..............Step 1 — put the first queen in column 1 of row 0row 101230123.Q.....Q........Step 2 — column 3 is free for row 1, so place thesecond queenfull board01230123.Q.....QQ.....Q.Step 3 — rows 2 and 3 also find a safe column, so theboard is completesame column: c in colssame diagonal: r+c in pos_diagsame diagonal: r-c in neg_diagskip if any of the three hits
Place a queen in the current row, recurse, and undo the choice when a conflict appears.
ComplexityTime O(n!)Space O(n^2)The search tree has roughly n! branches, and each stored board costs O(n^2) to build; the recursion stack and the three sets use O(n) extra space.

What Trips People Up in Real Interviews

1

Clarify if you need to return all solutions or just count them

2

Mention the diagonal math: positive diagonal is row+col, negative is row-col

3

Explain the time complexity is O(N!) but pruning makes it much faster in practice

4

Discuss how the problem extends to the N-Queens counting variant

5

Show how to represent the board compactly as a 1D array of column positions

Solution Code

O(n!) time
class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols = set()
        pos_diag = set()
        neg_diag = set()
        board = [['.'] * n for _ in range(n)]

        def backtrack(r):
            if r == n:
                result.append([''.join(row) for row in board])
                return
            for c in range(n):
                if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
                    continue
                cols.add(c)
                pos_diag.add(r + c)
                neg_diag.add(r - c)
                board[r][c] = 'Q'
                backtrack(r + 1)
                cols.remove(c)
                pos_diag.remove(r + c)
                neg_diag.remove(r - c)
                board[r][c] = '.'

        backtrack(0)
        return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the N-Queens problem?

Place N queens on an N×N chessboard so that no two queens attack each other. Return all distinct solutions where each solution contains a distinct board configuration. The classic backtracking problem that tests constraint satisfaction and pruning techniques.

How do you solve N-Queens?

The optimal approach runs in O(n!) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask N-Queens?

N-Queens is asked at Google. It is a hard difficulty problem.

What are common mistakes on N-Queens?
  • Clarify if you need to return all solutions or just count them
  • Mention the diagonal math: positive diagonal is row+col, negative is row-col
  • Explain the time complexity is O(N!) but pruning makes it much faster in practice
  • Discuss how the problem extends to the N-Queens counting variant
  • Show how to represent the board compactly as a 1D array of column positions