The N-Queens Problem, Explained

If you've spent any time on coding platforms or preparing for technical interviews, you've probably run into the N-Queens problem. It looks like a puzzle, it feels like a puzzle, but underneath it's one of the best ways to actually understand backtracking instead of just memorizing it.

The Problem, In Plain Terms

Place N queens on an N×N chessboard so that no two queens attack each other.

In chess, a queen attacks any square along its row, its column, and both diagonals. So the rule becomes: no two queens can share a row, a column, or a diagonal.

For N = 4, that means fitting 4 queens onto a 4×4 board with zero conflicts. It sounds simple until you actually try it by hand — most placements you'll attempt in the first minute fail.

Why Brute Force Falls Apart Fast

The naive idea is: try every possible way to place N queens on N² squares, and check each arrangement for conflicts.

The problem is scale. For an 8×8 board, the number of ways to place 8 queens on 64 squares runs into the billions. Checking every single one for validity is technically possible but painfully wasteful — you'd be generating and discarding huge numbers of arrangements that were obviously doomed from the second queen you placed.

This is exactly the situation backtracking was built for.

The Key Insight: One Queen Per Row

Since no two queens can share a row anyway, you don't need to think about placing "8 queens on 64 squares." You only need to decide one thing per row: which column does this row's queen go in?

That single reframing shrinks the problem enormously. Instead of choosing from 64 squares, you're placing one queen per row, column by column, and checking as you go.

How Backtracking Solves It

Backtracking is essentially: try something, and if it stops working, undo it and try the next option — rather than working out the entire solution in advance.

Here's the loop for N-Queens:

Start at row 0.
Try placing a queen in each column of that row, one at a time.
For each attempt, check: does this column, or either diagonal, already have a queen from a previous row?
If it's safe, place the queen and move to the next row.
If none of the columns in a row are safe, go back to the previous row, remove that queen, and try its next option.
Repeat until every row has a queen (a solution) — or until every possibility has been exhausted. That "go back and remove the queen" step is the backtrack. It's what separates this from brute force: the algorithm abandons a bad path the moment it becomes invalid, instead of building the whole thing out first.

Walking Through N = 4

Row 0: place a queen in column 0.
Row 1: column 0 and column 1 both conflict (column 0 is taken, column 1 is diagonally attacked). Column 2 works — place it there.
Row 2: every column conflicts with the two queens already placed. Dead end.
Backtrack to Row 1: try column 3 instead of column 2.
Row 2: column 1 is now safe. Place it.
Row 3: every column conflicts. Dead end again.
Backtrack all the way to Row 0: try column 1 instead of column 0. Keep following this pattern and you eventually land on a valid arrangement — for N = 4, the two solutions place queens at columns (1, 3, 0, 2) and (2, 0, 3, 1) across rows 0–3.

A Working Implementation (Python)


python
def solve_n_queens(n):
    solutions = []
    columns = set()
    diagonals = set()      # row - col is constant along a "/" diagonal
    anti_diagonals = set()  # row + col is constant along a "\" diagonal
    board = [-1] * n        # board[row] = column of the queen in that row
 
    def backtrack(row):
        if row == n:
            solutions.append(board.copy())
            return
        for col in range(n):
            if col in columns or (row - col) in diagonals or (row + col) in anti_diagonals:
                continue
            # Place the queen
            board[row] = col
            columns.add(col)
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
 
            backtrack(row + 1)
 
            # Remove the queen (this is the "backtrack")
            columns.remove(col)
            diagonals.remove(row - col)
            anti_diagonals.remove(row + col)
 
    backtrack(0)
    return solutions
 
print(f"Total solutions for 8-Queens: {len(solve_n_queens(8))}")

Two details make this version efficient:

Sets instead of a 2D board scan. Checking col in columns is instant, instead of scanning an entire board for conflicts on every placement.
Diagonal math. Every square on the same "/" diagonal shares the same row - col value, and every square on the same "" diagonal shares the same row + col value. That turns diagonal-conflict checking into two more set lookups.

How Fast Is This, Really?

Backtracking doesn't change the worst-case complexity in theory — it's still exponential, roughly O(N!) in the loosest bound, since each row has fewer safe options than the last. But in practice, it prunes enormous portions of the search space early, which is why it solves N = 8 almost instantly and N = 15 in a reasonable amount of time, where brute force would never finish.

Space complexity is O(N) — you only need to track one queen's position per row plus the conflict sets, not the full board of every attempt.

Why This Problem Shows Up So Often

N-Queens isn't really about chess. It's a clean template for an entire category of problems: constraint satisfaction, where you're placing things one at a time under rules, and need to backtrack whenever a rule gets broken. Once you understand this pattern, you start recognizing it everywhere:

Sudoku solvers
Maze and pathfinding puzzles
Map coloring problems
Scheduling and resource-allocation problems
Generating valid combinations under constraints (parentheses, permutations, subsets) That's the real reason it's a favorite in interviews and DSA courses — it's not testing whether you know chess, it's testing whether you can think in terms of "choose, check, recurse, undo."

The Takeaway

The N-Queens problem is a small puzzle with a big lesson: most hard problems don't need every possibility explored — they need bad paths abandoned early. Master that idea here, on an 8×8 board, and you'll start spotting the same pattern in problems that look nothing like chess at all.