Place eight queens on a chessboard so none attacks another, and you've stumbled onto one of computer science's favorite teaching problems. The N-Queens puzzle looks simple, but it's a perfect stage for comparing two very different problem-solving philosophies: backtracking and hill climbing.
If you've played the Queens Game on a colored grid, you've already done this kind of reasoning by hand — ruling out rows, columns, and diagonals until one placement remains. Algorithms face the same challenge, just at scale, and they can go about it in opposite ways: build a solution step by step and retreat when stuck, or start with a rough guess and keep improving it.
This article is for students, developers, and curious puzzle fans who want to understand why N-Queens shows up more than once in AI coursework — once as a search problem, once as an optimization problem — and what that difference actually means in practice. You'll get a clear comparison of how each algorithm works, why one guarantees an answer while the other doesn't, and which approach holds up better as the board grows large.
Why N-Queens Shows Up Twice in AI Courses
Most students meet N-Queens twice, and the two versions rarely feel like the same problem. First it appears in the search unit as a backtracking exercise: place queens column by column, check constraints, and undo a placement when you hit a dead end. It's clean, systematic, and always finds an answer if one exists.
Later it resurfaces in the local search unit, dressed up as hill climbing or min-conflicts. Now you start with all queens on the board, already conflicting, and nudge them toward a solution one swap at a time. There's no backtracking, no guaranteed success, and sometimes no solution at all if the search stalls.
Same puzzle, same eight queens, completely different algorithmic philosophy. That whiplash is the point — comparing them directly is what makes both approaches finally click.
A Quick Refresher on the N-Queens Problem
The classic N-Queens problem asks you to place N chess queens on an N×N board so that none attacks another. That means:
- No two queens share a row.
- No two queens share a column.
- No two queens share a diagonal.
It's a pure constraint-satisfaction puzzle, which is exactly why computer science courses love it. The puzzle dates back to 1848, when German chess composer Max Bezzel published the eight queens version. It took a couple of years for anyone to nail down the full solution set — Franz Nauck got there in 1850.
For the standard 8x8 board, there are exactly 92 distinct solutions, though many are rotations or mirror images of one another; only 12 are truly unique. Scale N up or down and the picture changes: solutions exist for every board size except N=2 and N=3, where the board is simply too small to fit non-attacking queens.
That's the baseline. Now let's look at how two very different algorithms — hill climbing and backtracking — actually find those solutions.
Backtracking: Systematic Search With Pruning
Backtracking solves N-Queens by building a solution one column at a time and abandoning any path the moment it breaks a rule.
Here's the process:
- Place a queen in column 1, in any row.
- Move to column 2 and try each row in turn.
- Before locking in a placement, check it against every queen already on the board — same row, same diagonal, or (in the color-region version) same region already used.
- If a row works, move to the next column. If none work, backtrack: remove the previous queen and try its next option.
This is exhaustive, but far from brute force. The moment a placement conflicts with an earlier queen, the algorithm skips every arrangement that would have followed from it — that's the "pruning" part. Instead of checking all possible boards, it discards huge branches of the search tree early.
The payoff is reliability. Backtracking explores the space methodically and will find a valid arrangement whenever one exists, or prove none exists by exhausting every option. For puzzle-sized boards, like the grids in Queens, that guarantee matters more than raw speed.
Hill Climbing: Starting Full and Reducing Conflicts
Backtracking builds a solution one queen at a time. Hill climbing takes the opposite approach: start with every queen already on the board, then fix mistakes.
Here's how it works for N-Queens. Place one queen in each column, at a random row. The board is complete but almost certainly invalid — queens will share rows and diagonals. From there, the algorithm repeatedly picks a queen and moves it within its column to the row that produces the fewest conflicts with other queens, counting shared rows and diagonal attacks. This is the "min-conflicts" heuristic: at each step, reduce the total number of attacking pairs on the board.
The process repeats until either no conflicts remain (a solution) or no single move improves things (a local minimum, where the search gets stuck despite the board still being invalid).
This matters for the Queens puzzle too, once you add color regions: you're still adjusting one queen per row or column, and every move should measurably cut down on rule violations — same-column clashes, adjacent touches, or missing regions. Thinking in terms of "which move lowers my conflict count" is a useful mental model even when you're solving by hand.
Why Hill Climbing Gets Stuck — and How Random Restarts Help
Hill climbing looks smart until it isn't. On random 8-queens starting boards, plain hill climbing solves the puzzle only about 14% of the time. The other 86% of runs stall at a local minimum — a placement where every possible move to a new column or row makes conflicts worse or leaves them unchanged, so the algorithm has no "downhill" step to take.
What's striking is how fast this happens either way. Successful runs finish in about 4 steps on average; stuck runs stall in about 3. The algorithm isn't slow — it's short-sighted. It commits early to a queen arrangement that looks promising, then discovers there's no local move that reduces attacking pairs, even though a completely different layout would solve the board easily.
Random-restart hill climbing fixes this with a blunt but effective trick: when the search stalls, throw out the board and start over with a fresh, randomly placed set of queens. Each restart is a new roll of the dice, uncorrelated with the last one, so a plateau that trapped one attempt rarely traps the next. Run enough restarts and you eventually land on a starting configuration whose downhill path leads all the way to zero conflicts — no memory of prior failures needed, just persistence.
Guaranteed Correctness vs No Guarantee: The Core Tradeoff
This is the real difference between the two approaches, and it matters far beyond N-Queens or the Queens puzzle. Backtracking explores the search space exhaustively, backing up whenever a placement fails. If a solution exists, backtracking will find it. If none exists, it will prove that too. That's a completeness guarantee.
Hill climbing offers no such promise. It moves toward fewer conflicts step by step, but it can settle into a local minimum — a state where every neighboring move looks worse, even though the board isn't solved. On classic 8-queens instances, plain hill climbing succeeds only a slice of the time and stalls the rest.
So the tradeoff is simple:
- Backtracking: slower, but always correct.
- Hill climbing: fast, but sometimes wrong.
Which one you want depends on whether you need an answer or the answer.
When Each Approach Wins as N Grows Large
Board size changes the calculus completely. Backtracking's search tree grows exponentially with N, and even aggressive pruning can't save it once N reaches into the hundreds or thousands. Each added row multiplies the branches to check, and the systematic guarantee that makes backtracking trustworthy is exactly what makes it slow at scale.
Local search doesn't have this problem, because it never explores a tree. It holds one full board and repairs conflicts step by step. The min-conflicts heuristic is the standout example: it can solve n-queens instances with a million queens in roughly 50 steps on average. That number is almost unbelievable next to backtracking's combinatorial blowup, but it holds because local search cost depends on how many conflicts exist near a solution, not on how many possible boards exist in total.
So the practical rule is simple:
- Small N, or when you need every solution or a proof of unsolvability: backtracking.
- Large N, when any valid solution will do: min-conflicts or similar local search.
There's a twist worth knowing. Finding one full solution to standard n-queens is easy at scale, but n-Queens Completion — deciding whether a partially filled board can be completed into a valid solution — is NP-complete. Researchers at the University of St Andrews proved this in 2017. So the puzzle you casually solve on a Queens board is deceptively simple compared to the completion variant, which is genuinely hard in the worst case.
Choosing the Right Algorithm for Your Problem
The right choice depends on what you actually need.
- Small board, must have an answer: Use backtracking. On an 8x8 Queens puzzle, systematic search with pruning finds a valid arrangement every time, and the board is small enough that speed isn't a concern.
- Huge board, "a" solution is fine: Use hill climbing with random restarts, or a min-conflicts style approach. Local search scales to enormous n where backtracking becomes impractical.
- You need to verify uniqueness or completeness: Backtracking, since it can confirm no solution exists or enumerate all of them — something hill climbing can't do.
- You're exploring a custom variant of Queens (extra region constraints, partial boards): Lean toward backtracking, since guarantees matter more than raw speed when correctness rules define the puzzle.
In short: backtracking trades speed for certainty, hill climbing trades certainty for scale. Match the algorithm to whether you need proof or just a fast, workable answer.