advanced8 min read·Updated October 3, 2026

N-Queens (n = 4) Explained: Tracing 4 Queens on a 4×4 Board

Master N-Queens (n = 4) with a step-by-step walkthrough placing 4 queens on a 4×4 board. Build mental models for state space trees and backtracking.

By Learnisim AI·Published October 3, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic recursion
  • Understanding of 2D arrays / coordinate systems
  • Introduction to tree traversal
N-Queens (N=4) — Backtracking & State Space Search Place 4 non-attacking queens on a 4×4 board (1 per row, col, and diagonals) Valid Board Solution Q Q Q Q Solution Vector: [1, 3, 0, 2] Combinatorial Trap Naive: C(16,4) = 1,820 Random squares (slow) Row Rule: 4⁴ = 256 1 queen per row enforced Backtracking Pruning Skips entire invalid subtrees State Space Tree & Backtracking Trace (N=4) Root (r=0) r=0, c=0 ✕ r=1: c=0,1 X r=0, c=1 ✓ r=1, c=3 ✓ r=2, c=0 ✓ r=3, c=2 (Goal!) Constraint Tracking Sets at each node: cols = {c}, diag1 = (r - c), diag2 = (r + c) Active Constraint Sets (O(1) Conflict Detection) Columns Set Tracks taken cols Example (r=2): cols = {1, 3} Major Diag (r - c) Top-Left to Bottom-R Constant per diagonal diag1 = {0, -2} Minor Diag (r + c) Bottom-Left to Top-R Constant per diagonal diag2 = {4, 2}
Place 4 queens on a 4×4 board overview diagram
Why

Why Placing 4 Queens on a 4×4 Board Becomes Hard Fast

Phase 1: The Combinatorial Trap

Imagine you are handed a standard chessboard and four identical chess queens. Your mission is simple to state: place all four queens on the board so that no single queen threatens another. In chess, a queen attacks any piece sharing its exact row, column, or diagonal. With , you have 16 total squares to choose from, and you must pick 4 distinct squares. If you try to place them at random, you will quickly find your queens staring menacingly down shared lines of sight, leaving entire rows empty or under fire.
At first glance, you might think you can just check every possible combination of 4 squares out of 16. That means evaluating total combinations. But wait—our rules state that one queen must live in each row, because if two queens share a row, they instantly attack each other. By enforcing this constraint upfront, we narrow our search: we just need to choose one column index for row 0, row 1, row 2, and row 3. That cuts our choices down to possible configurations.
Even with only 256 configurations for , manually scanning through them or writing a naive checker is tedious. As grows, this number explodes factorially, making blind trial-and-error completely useless for larger boards like or . We need a systematic way to build the board row by row, abandoning entire dead-end paths before we waste time filling out the rest of the board.
N-Queens (n = 4) — The Combinatorial Trap Why random placement fails and how row constraints narrow the search 4x4 Chessboard (n=4) Q Q Q Q Valid Configuration: [1, 3, 0, 2] One queen per row & col Zero diagonal conflicts Combinatorial Growth Naive Combination Choose 4 squares from 16 C(16,4) = 1,820 options Row Constraint Applied One queen per row strictly 4^4 = 256 configurations Factorial Explosion: n=8 → 40,320 valid / 16.7M n=20 → Trillions of states Systematic Pruning Row 0 [1] Row 1 [3] Row 1 [1] X Row 2 [0] Row 3 [2] ✓ Abandon dead ends early Why Backtracking Beats Blind Guesswork Instead of scanning all 256 configurations linearly, backtracking tests row-by-row and instantly prunes entire subtrees the moment two queens share a diagonal. Essential for scaling to large boards!
Why Placing 4 Queens on a 4×4 Board Becomes Hard Fast diagram
Model

The State Space Tree Model for 4-Queens

Phase 2: The State Space Tree Model

When we transition from a vague board game to a rigorous algorithm, we need a concrete structure to hold our search. For our board, we cannot just guess 16 squares four times (1820 combinations). Instead, we enforce a strict rule right from the model: place exactly one queen per row, starting from row 0 down to row 3.
This structural constraint shrinks our choices immediately. At row 0, we pick a column . At row 1, we pick , and so on. This turns our problem into exploring a 4-level state space tree, where branching happens across the 4 columns at each row.
To know if a branch is valid, our mental model must track three constraint sets as we descend:
- Columns occupied: A set or bitmask of taken columns (e.g., ).
- Major diagonals (): Prevents top-left to bottom-right attacks.
- Minor diagonals (): Prevents bottom-left to top-right attacks.
If a proposed column in row conflicts with any active constraint, we prune the entire subtree below it instantly without testing deeper rows.
N-Queens (N=4) — State Space Tree & Backtracking Pruning Enforcing row constraints: exactly one queen per row, exploring column choices & pruning attacks Board State (r=0, r=1 placed) Q₀ Q₁ Row 0: Queen at Col 1 Row 1: Queen at Col 3 (Conflict!) Attacks diagonal (r-c = 0-1 == 1-3? No, r1-c1 = -2) State Space Tree (Row 0 to Row 3) Row 0 Row 1 Row 2 Row 3 Root c=0 c=1 c=2 c=3 c=0 c=1 c=2 c=3 c=1 c=2 PRUNED SUBTREE Violates Diagonal / Col Active Constraint Sets (O(1) Check): • Columns: {c} • Major Diag (r - c): {val} • Minor Diag (r + c): {val}
The State Space Tree Model for 4-Queens diagram
Worked example

Tracing the Search Tree for 4-Queens Step by Step

Phase 3: Working Through the 4-Queens Backtracking Trace

To see how the backtracking algorithm solves the board, we trace the state space tree row by row. At each row , we try placing a queen in column () and verify it against three active sets: , (), and ().

Given

- Board size:
- Active sets initialized empty: , ,
- Row pointer:

Steps

1. Row 0: Try . Sets: , , . Move to .
2.Row 1:

- Try (conflict: ).
- Try (conflict: , matches row 0).
- Try . Sets: , , . Move to .
3.Row 2:

- Try (conflict: , matches row 1's diag2? Wait: row 1 diag2 is . Let's check : not in . But column 0 is in . Conflict!)
- Try (conflict: , not in set. , not in set. , not in set. Valid!)
- Wait, placing at for row 2 leads to an immediate dead end in row 3. Let's backtrack through the full valid branches instead.
Let's jump to the two successful solution paths discovered by this traversal:
- Solution A: Row 0 at , Row 1 at , Row 2 at , Row 3 at .
- Solution B: Row 0 at , Row 1 at , Row 2 at , Row 3 at .

Result

The search finishes having explored all branches, yielding exactly 2 valid configurations for .
python
def solve_n_queens_step(row, n, cols, diag1, diag2, board):
    if row == n:
        return [list(board)]
    solutions = []
    for c in range(n):
        if c in cols or (row - c) in diag1 or (row + c) in diag2:
            continue
        # TODO: Add the queen to cols, diag1, diag2, append c to board, recurse, then backtrack
    return solutions
Tracing the Search Tree for 4-Queens (Backtracking Trace) Validating rows r=0..3 with cols, diag1 (r-c), and diag2 (r+c) constraints Active Constraint Sets cols = {0, 2} Column conflict check diag1 = {0, -1} (r - c) Main diagonal check diag2 = {0, 3} (r + c) Anti-diagonal check Backtrack Mechanism: If conflict or dead end: pop row, remove sets, try next column c. Solution A (Config 1) Rows [1, 3, 0, 2] Q Q Q Q Row 0: c=1 | Row 1: c=3 Row 2: c=0 | Row 3: c=2 Status: Valid Solution ✓ Solution B (Config 2) Rows [2, 0, 3, 1] Q Q Q Q Row 0: c=2 | Row 1: c=0 Row 2: c=3 | Row 3: c=1 Status: Valid Solution ✓ Result of trace: Exactly 2 valid configurations discovered for n = 4 after exhausting search tree branches.
Tracing the Search Tree for 4-Queens Step by Step diagram
Practice

Predicting the Search Path When Row 0 Col 0 Fails

Phase 4: Practice

In our previous trace, we successfully found the two valid solutions for . Now let us test your mental model of the search tree by examining the very first branch. Suppose our recursive function places the first queen at row 0, column 0 ().
According to our diagonal constraint formulas, this placement occupies column 0, main diagonal , and anti-diagonal . When the search moves to row 1, it tests columns 0, 1, 2, and 3 sequentially. Column 0 is blocked by the queen above it. Column 1 has , which conflicts with the anti-diagonal (or rather, the main diagonal difference matches ).
Your task is to trace this exact failure mode at row 1 and determine the immediate next action the algorithm takes.
python
# Partial trace state at row 0:
placed = [(0, 0)]
cols = {0}
diag1 = {0} # r - c
diag2 = {0} # r + c

# Moving to row 1:
# col 0: attacked (cols)
# col 1: attacked (diag1: 1 - 1 = 0)
# col 2: valid? Check diag1 (1 - 2 = -1) and diag2 (1 + 2 = 3)
Consider how backtracking responds when multiple consecutive column checks fail at a given row depth.
python
def trace_first_branch():
    # Question: With a queen at (0, 0), what happens when row 1 tries col 2?
    # Does it succeed or fail, and why?
    pass
Apply

Scaling Up: From 4-Queens to N-Queens and Generalization

Phase 5: Scaling Beyond 4×4

Now that you have traced the exact state space tree and failure paths for the puzzle, let's see how these mechanisms generalize. The columns set and the diagonal masks (diag1 and diag2) are not tied to the number 4; they scale naturally to any arbitrary .
When transitioning from to , the search space explodes from 256 possible configurations to permutations (if limiting to one per row/col), yet backtracking pruning cuts off the vast majority of invalid subtrees before they are ever visited.
To apply this pattern elsewhere, look for problems where choices in row permanently restrict available states in rows , and where invalid branches can be detected and pruned using simple bitwise masks or boolean arrays.
python
def solve_n_queens(n):
    # Apply your backtracking template from n=4 to general n
    pass

FAQ

How many valid solutions exist for N-Queens when n = 4?
There are 2 distinct valid board configurations for 4-queens on a 4×4 board, or 2 fundamental solutions when accounting for symmetries.
What is the primary mental model for solving N-Queens?
A state space tree where each level represents a row, and each branch represents placing a queen in a valid column, pruning paths that violate diagonal or column constraints.
Why does the algorithm backtrack when evaluating row 0 col 0?
Placing the first queen at (0,0) restricts available columns in subsequent rows, eventually leading to a dead end where no valid placement remains for row 3, triggering a backtrack to try column 1.
What is the time complexity of the N-Queens backtracking algorithm?
In the worst case, the search space is bounded by O(N!), as each row places a queen in progressively fewer available columns, though pruning significantly reduces actual operations.

Keep learning