How do you solve the N-Queens problem? | Interview Question

Q: How do you solve the N-Queens problem?

**Target Audience:** Developers preparing for coding interviews who know recursion in Python and want to master backtracking. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Imagine seating eight very touchy guests at a square banquet table laid out like a chessboard. Each guest refuses to sit in the same row as another guest, in the same column, or anywhere along the same diagonal line. You want to find every seating plan that keeps everyone calm. You could write down every possible way to put 8 guests on 64 seats and check each one. There are more than

The problem

Question presented to candidate: "Place n queens on an n by n chessboard so that no two attack each other. Write a Python function that returns every solution, and then tell me how you would only count them for n up to 12."

What a strong answer should cover:

Place one queen per row, so a solution is a list queens[row] = col; this turns n² cells into n decisions.
Backtracking with choose / explore / un-choose, pruning a column as soon as it is attacked.
O(1) safety checks using three sets: columns, r - c and r + c.
Complexity: O(n!) upper bound on the search, O(n) extra space plus the output; 92 solutions for n = 8.
Python details: append queens[:] (a copy), use set or list[bool] for the taken markers, recursion depth is only n so the default limit of 1000 is not a problem, and the bitmask version needs & full because Python ints never overflow.

Clarifying questions expected:

Do you want every board (as strings) or only the number of solutions?
What range of n should I expect? (It decides whether a bitmask counter is worth it.)

Code / implementation expected: Yes — a recursive solve_n_queens(n) with three sets in Python 3, and optionally a bitmask counter.

dsa
backtracking

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for coding interviews who know recursion in Python and want to master backtracking.
Difficulty: Hard
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Imagine seating eight very touchy guests at a square banquet table laid out like a chessboard. Each guest refuses to sit in the same row as another guest, in the same column, or anywhere along the same diagonal line. You want to find every seating plan that keeps everyone calm.

You coul

The solution is hidden so you can try first

11 min read · 14 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonAll solutions as boards for n = 4, solution counts for n = 0..8

Practice

PythonBrute force over permutations vs backtracking: work counted for n = 4..8

Practice

PythonN-Queens II: counting solutions for n = 1..12 with bitmasks

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.