The N-Queens puzzle looks simple: place N queens on an N×N board so none share a row, column, or diagonal. But that simplicity hides a great little laboratory for studying search. If you've played Queens Game, you've already done this by hand, using color regions and elimination to skip guesses. Under the hood, computer solvers face the same challenge on a bigger scale, and how they solve it reveals two fundamentally different philosophies of problem-solving.
This article is for anyone curious about how algorithms actually "think" through a constraint puzzle — puzzle fans, students learning computer science, or programmers who've heard the term "backtracking" and want real intuition, not just pseudocode. We'll compare plain backtracking, which tries a queen, checks for conflicts, and backs up when stuck, against constraint propagation, which actively narrows down future options before a single guess is made.
By the end, you'll see why these two approaches can solve the exact same board at wildly different speeds, and what that difference teaches about smart search more broadly — in puzzles, and in software.
Two Ways to Search the Same Board
The classic N-Queens puzzle asks you to place N queens on an N×N chessboard so that no two share a row, column, or diagonal. First published by Max Bezzel in 1848, it's one of the oldest test cases in computer science for search algorithms — and the logic behind it is the same logic behind Queens, the region-based puzzle where color-coded zones stand in for the diagonal rules.
Solving N-Queens by computer usually starts with backtracking: place a queen, check for conflicts, and if none exist, move to the next row. Hit a dead end, and you back up and try again. It's simple and guaranteed to work.
Constraint propagation changes the strategy. Instead of waiting to hit a wall, it actively trims impossible placements from every open row as soon as a queen goes down. This piece compares the two approaches head-to-head — how they behave, where they struggle, and why one scales so much better than the other as the board grows.
How Plain Backtracking Places Queens One Row at a Time
Plain backtracking solves the puzzle the way a careful player might, working row by row and trusting trial and error to sort out the rest.
The algorithm starts at row one and tries placing a queen in the first available column. Before committing, it checks three things:
- Is another queen already in this column?
- Is another queen already on this diagonal, corner to corner?
- In the Queens game specifically, does this square belong to a color region that already has a queen?
If the placement passes, the algorithm moves to the next row and repeats the process. If every column in a row fails these checks, there's no valid move — so the algorithm backtracks. It undoes the most recent placement, returns to the previous row, and tries the next untested column there.
This cycle of place, check, recurse, and undo continues until either a full board of valid placements is found or every option has been exhausted. There's no lookahead here — the algorithm doesn't anticipate future conflicts. It only reacts once a row runs out of legal moves, which is why plain backtracking can end up testing many dead-end branches before stumbling onto the solution.
What Constraint Propagation Does Differently
Plain backtracking places a queen, then checks for conflicts after the fact. Constraint propagation flips that order: before you commit to a placement, it updates what's still legal everywhere else on the board.
Forward checking is the clearest example. Every unplaced region has a domain — the set of columns still open to it. When you place a queen in row 3, column 4, forward checking immediately strips column 4, and both diagonals running through that square, from every other region's domain. If a region's domain drops to zero, you know that branch fails right now, not five moves later.
This matters on Queens because color regions often overlap in tight clusters near the board's edges or corners. A single placement can quietly eliminate several candidate squares from two or three neighboring regions at once. Forward checking surfaces that immediately instead of letting the search wander into a dead branch.
The practical payoff is fewer wasted placements. Instead of discovering a contradiction three or four queens deep, you catch it the moment a domain empties out. Research on constraint satisfaction shows forward checking roughly doubles the size of n-queens problems solvable in practical time compared to plain backtracking — a real efficiency gain, not just a theoretical one.
A Six-Queens Walkthrough: Watching the Search Trees Diverge
Picture a 6x6 Queens board with six colored regions. Row 1's region only touches columns 1 and 2, so both searches start by placing a queen at row 1, column 1.
Plain backtracking now moves to row 2, tries every open column in that row's region, and picks the first legal one — say column 3. It keeps going row by row, and only when it reaches row 5 or 6 does it discover the columns left are already blocked by earlier queens or fall outside that row's region. At that point it backtracks, undoes the row 5 queen, tries another column, fails again, undoes row 4, and so on. Several rows of placements get built and torn down before the conflict at row 1's choice is even reconsidered.
Constraint propagation checks further ahead. As soon as row 1's queen lands on column 1, it removes column 1 and its diagonal neighbors from every other row's options. If that step shrinks some row's region down to zero legal columns, propagation flags the problem immediately — before row 2, 3, or 4 ever gets a placement.
Side by side, backtracking's tree grows five or six levels deep before pruning a bad branch. Propagation's tree often gets pruned at depth one or two. Same board, same rules, dramatically different amounts of wasted work.
Why Fewer Branches Get Explored: The Numbers Behind the Speedup
The gap between plain backtracking and forward checking isn't cosmetic — it's compounding. Research on constraint satisfaction shows forward checking roughly doubles the size of n-queens problems you can practically solve compared to plain backtracking. That's not a small tuning gain; it's the difference between a solver that stalls around a modest board size and one that comfortably handles a board twice as large.
The reason comes down to how pruning interacts row by row. Plain backtracking discovers a conflict only after placing a queen and checking the board. Forward checking removes doomed columns from future rows' domains the moment a queen goes down.
That removal effect stacks:
- Row 1 shrinks row 2's options.
- Row 2's narrowed choices shrink row 3's options further.
- By row 6 or 7, entire branches that backtracking would have generated and rejected one-by-one simply never exist.
Each row doesn't just add its own savings — it multiplies the savings from every row before it. Fewer live branches at row 3 mean exponentially fewer dead ends by row 7, which is why the speedup accelerates on larger boards rather than staying flat.
How Real Solvers Like OR-Tools Put This to Work
Google's OR-Tools, a widely used constraint-programming toolkit, doesn't treat propagation and backtracking as rivals. It runs them together in a loop: at every node in the search tree, the solver first propagates constraints to shrink each variable's domain, then branches only if a choice is still needed.
For a Queens-style board, that means row, column, and region constraints all fire together. Placing a queen in one colored region immediately eliminates conflicting cells in its row, column, and diagonals. If any region's domain empties out, OR-Tools detects the dead end and backtracks right away, instead of discovering the failure several placements later.
This combination is why production solvers scale so well:
- Propagation does the cheap, deterministic work upfront.
- Backtracking handles only the genuinely ambiguous decisions.
- Search order and heuristics (like picking the most constrained region next) further cut wasted branches.
The result is a search tree that stays small even as board size grows.
What This Comparison Teaches About Search in General
N-Queens is a stand-in for a much larger family of problems: scheduling, map coloring, Sudoku, resource allocation. Anywhere you're assigning values to variables under hard constraints, the same lesson applies. Search speed isn't really about raw computing power — it's about how much you know before you commit to a choice.
Plain backtracking commits first and checks later. Constraint propagation checks first and commits only when a choice is still safe. That shift — from "try and see" to "look before you leap" — is the core idea behind most modern solvers, whether they're placing queens or assigning delivery routes.
The takeaway: smarter search beats faster search. Reducing the number of choices you consider matters more than speeding up how fast you consider them.