The eight problem-solving Backtracking entries on this site, like the nine Greedy ones, don't compete for the same job: N-Queens places non-attacking queens, Sudoku fills a grid, Graph Coloring assigns colors to vertices, Hamiltonian Path/Cycle builds a walk, Word Search traces a path through a letter grid, Knight's Tour visits every square once, Subset Sum picks numbers that add up to a target, and Palindrome Partitioning cuts a string into palindromic pieces. Nobody chooses between them for one task. What they share is a single shape — build a candidate one piece at a time, reject it the moment it can't work, undo and try the next option — repeated eight times over eight different problems. This guide isn't "which of these eight for my problem." It's "what actually varies underneath that one repeated shape," across three questions that turn out to matter more than which puzzle is on the page: what makes a candidate illegal in the first place, whether the order candidates are tried in can only slow the search down or can also change what it reports, and whether backtracking is even the best known tool for the job. A ninth entry, Dancing Links, answers none of those three differently — it changes the repeated shape itself, and gets its own section below. A tenth, Branch and Bound, doesn't just answer the three questions differently either — it isn't answering the same kind of question at all, since it searches for the best solution rather than any valid one, and gets its own section too.
Five of the eight entries reject a candidate because it conflicts with something already placed — a structural or relational check. N-Queens rejects a row that shares a row, column, or diagonal with a queen already on the board. Sudoku rejects a digit that already appears in the same row, column, or 3×3 box. Graph Coloring rejects a color already used by an adjacent, already-colored vertex. Hamiltonian Path/Cycle rejects a neighbor that's already been visited, or, in cycle mode, accepts a final step only if it has an edge back to the start. Word Search rejects a neighboring cell whose letter doesn't match the next character, or that's already part of the current path. All five checks are the same kind of question — does this candidate conflict with something that's already committed? — just asked about a different relationship each time.
Subset Sum rejects candidates a different way
entirely: with arithmetic, not a relational conflict. Nothing about including the
next item conflicts with anything already chosen the way a shared row or an adjacent color does —
what gets checked instead is whether the running sum has already overshot the target, or whether
the remaining unconsidered items can't possibly make up the shortfall even if every one of them is
included. On the page's own 5-item, target-9 example this cuts the search to 20 recursive calls
against 32 brute-force subsets, split between 5 immediate overshoot rejects and 3 remaining-budget
prunes — and the page's own Pitfalls section shows both rules quietly assume every item is
positive: with a negative item in the mix, hitting the target exactly is no longer proof a branch
is done, and a real solution ({9, -3, 3} alongside {9}, for
target = 9) gets silently missed rather than just found more slowly.
Knight's Tour is the odd one out in a stronger way still: nothing is ever illegal. Every knight move that lands on the board and on a square not yet visited is a completely legal next step — there's no row, no color, no arithmetic bound to violate. The search can still fail (run out of legal moves with squares left unvisited), but every individual candidate it ever considers is valid; what changes outcomes is purely which valid candidate gets tried first. That makes it the cleanest possible test of the second question below, because there's no rejection logic left to confuse the measurement with.
Palindrome Partitioning rejects a third way entirely, and it's the odd one out for the opposite reason Subset Sum is: its rejection rule never looks at anything already chosen at all. Every check above — structural or arithmetic — asks whether the candidate conflicts with something already placed. Palindrome Partitioning's candidate (the next piece to cut off) is judged purely on its own characters: is this exact substring a palindrome? The answer would be identical no matter what pieces came before it in the string, which is what makes it precomputable — the page's own Pitfalls section measures the real cost of not precomputing it, checking the same substring from scratch every time the same starting point gets reached by a different partition of the prefix in front of it.
For most of these entries, candidate order is a performance knob with no effect on the final answer. Sudoku's own order selector makes this a measured comparison rather than a claim: on the page's default puzzle, always filling the first empty cell in reading order needs 273 attempts and 12 backtracks to reach the solution; picking the cell with the fewest remaining candidates first (MRV) reaches the identical unique solution in 165 attempts and zero backtracks. The gap grows with difficulty, not just with this one puzzle: a published "easy" puzzle takes reading order 37,652 attempts, and a puzzle reported in the press as the world's hardest takes it 445,778 attempts — same algorithm, same correctness, wildly different cost. Graph Coloring shows the same pattern on its own wheel graph: starting the search from a rim vertex instead of the hub still correctly reports that 3 colors are impossible, but takes 228 attempts and 75 backtracks instead of 84 and 27, because the search has to rediscover the rim's own inconsistency several different ways before reaching the hub. Knight's Tour pushes the same effect furthest, since (per above) it has no rejection logic to share the credit with: plain compass-order search on a 5×5 board needs 287 attempts and 263 backtracks where Warnsdorff's rule (always try the square with the fewest onward options first) needs 24 and zero; on 8×8, plain search doesn't finish inside a 2,000,000-attempt cap where Warnsdorff's rule finishes in 63. Order didn't change whether a tour exists on either board — Warnsdorff's rule is not itself a correctness proof, and the same page's own Pitfalls section catches it needing a real 27 backtracks on a 6×6 board started from the center — it changed the cost by five orders of magnitude on the one board it actually failed to finish plain.
Word Search's own Pitfalls section describes something that looks like the same category but isn't: trying every matching starting cell, not just the first one found. That isn't an order effect — reordering which starting cell goes first would still change only the cost, the same as everywhere else above. What actually differs is exhaustiveness: stopping the outer loop after the first starting cell's search fails, rather than trying every starting cell, can silently report a word absent that's genuinely present but only reachable from a later occurrence of its first letter. The page's own default word SEE only succeeds because the search moves on to the second 'S' after the first one dead-ends immediately. Order changes how long a correct search takes; giving up after one candidate start changes whether the search is even complete enough to trust a negative answer.
Backtracking with pruning is a reasonable default when nothing faster is known — but three of
these eight entries have a real answer for "is anything faster known," and the answer isn't the
same for all three. Graph Coloring's own text draws
the sharpest line on the site: for k ≥ 3, deciding colorability is
NP-complete, so no algorithm — backtracking or otherwise — is known to solve every
instance in polynomial time, and pruning only shrinks the constant factor, never the underlying
exponential order. But the same page's own Pitfalls section notes one specific exception baked
into the problem itself: k = 2 is exactly bipartiteness, checkable by a
single BFS or DFS pass in
O(V + E), no trial-and-error at all — the demo's own search doesn't special-case it,
which is why k = 2 on the page still shows real attempts and backtracks instead of
resolving instantly the way a dedicated check would.
Hamiltonian Path/Cycle is in the same NP-complete
family as general graph coloring, with no exception built in the way k = 2 is —
naive brute force is O(n!) walks, and skipping already-visited neighbors prunes the
constant factor without changing that order for adversarial graphs, though small sparse graphs
like the page's own six-vertex example resolve instantly regardless.
The other five don't carry that NP-complete framing in their own text, and this guide won't
attach it to them just because it sounds like it should apply — per the standing rule of checking a
source page's own words, not outside general knowledge that merely sounds related.
N-Queens and Sudoku
are each, in Graph Coloring's own words, cases that "just need a working search": exponential
worst case, no known polynomial algorithm for counting N-Queens solutions in general, but nothing
in either page frames the decision problem itself as NP-complete the way Graph Coloring and
Hamiltonian Path/Cycle explicitly do for theirs.
Word Search's own bound,
O(rows·cols·4L), is polynomial in board size for any fixed word length —
its cost grows with the word, not with an NP-hard combinatorial explosion.
Subset Sum's own page states O(2n)
worst case and stops there, with no polynomial-alternative or NP-completeness claim either way in
its own text — the same is true of Knight's Tour's own
Complexity section, which states exponential-worst-case without ever addressing whether a faster
algorithm exists. The honest takeaway isn't "some of these are secretly easy and some are secretly
hard" — it's that the question "is anything faster than backtracking known here" has a real,
checkable answer for some problems (yes for 2-coloring, no for general graph coloring and
Hamiltonian path/cycle) and simply isn't addressed on-page for the rest, which is a different
thing from "no."
Palindrome Partitioning's own page draws
a different distinction again: its O(n·2n) worst case isn't a
faster-algorithm-unknown situation like Hamiltonian Path/Cycle's, it's inherent to the question
being asked — enumerating every valid partition of a string that's all palindromes (like
aaaa) means producing an exponentially large output, and no algorithm can hand back an
exponentially large answer in less than exponential time. The page is explicit that a
different question — not every way to partition, just the fewest cuts needed — drops the
exponential entirely, solvable in O(n2) by a bottom-up table. That's the
same relationship 0/1 Knapsack has to Subset Sum: a
polynomial algorithm exists for the counting/optimization cousin of the question, not for the one
this page's own search actually answers.
Dancing Links doesn't answer any of the three questions above differently — it sits outside all three, because it doesn't share what every other entry on this page shares underneath: undoing a choice by popping an array or clearing a grid cell. It's built for exact cover (choose subsets of a universe that partition it exactly, no item missed, none doubled), reached by covering a column in a circular doubly linked list and undoing that cover by relinking the same nodes in the exact reverse order — an O(1) pointer restore per node instead of a rescan. Sudoku and N-Queens are themselves exact-cover problems in disguise (see that page's own Complexity section), so this isn't a ninth unrelated problem so much as a different engine that could, in principle, solve two of the other eight problems on this page — this site just doesn't build that reduction. Its own column-choice rule (cover whichever column has the fewest live candidates first, the same idea as Sudoku's own MRV) reproduces this page's order-changes-speed lesson at a larger scale: measured directly, four orders of magnitude apart on a purpose-built instance, because that choice controls the branching factor of every level of the search, not just one column. And it introduces a failure mode none of the other eight can have: undoing a linked structure out of order doesn't just run slower, it can silently return an answer that isn't actually a valid exact cover — see that page's own Pitfalls.
Branch and Bound shares even less with the other nine than Dancing Links does. Dancing Links still answers "is there a valid assignment" — it just undoes choices with pointer relinking instead of popping an array. Branch and Bound doesn't answer a feasibility question at all: given weighted, valued items and a capacity, which combination maximizes total value? Every earlier entry's rejection rule is a hard illegality check — a broken row, an overshot sum, a repeated letter — and a rejected candidate is gone for good because nothing built on it could ever be valid. Branch and Bound's prune is a comparison instead: an optimistic upper bound on what a branch could still be worth, checked against the best complete answer already found. A pruned branch here might still be entirely feasible — it's abandoned only because it provably cannot beat what's already in hand, the same kind of comparison-based cutoff Minimax's alpha-beta pruning uses to abandon a game-tree branch that can't affect the outcome, not one that's illegal. Measured on the page's own five-item knapsack instance, the optimistic bound (a fractional-knapsack relaxation, valid only when items are pre-sorted by value-per-weight ratio) cuts the search from 43 nodes down to 18, reaching the identical best value 22 0/1 Knapsack's own dynamic-programming table finds for the same data — by a different, equally valid tied-optimal combination of items.
Facing a problem not already on this site, these three questions are worth asking in this
order. First, what actually makes a candidate illegal? If it's a conflict with
something already placed, the check is usually cheap and local — look at Sudoku's row/column/box
test or Graph Coloring's neighbor-color test as the template. If it's arithmetic instead (a
running total, a remaining budget), double-check what assumption the arithmetic quietly depends
on the way Subset Sum's pruning depends on every item being positive — an assumption that's easy
to satisfy by construction and easy to violate by accident once the problem's inputs widen.
Second, does the order candidates are tried in only cost time, or can it cost
correctness? Reordering rows, colors, or candidate squares is free to experiment with —
Sudoku's MRV and Knight's Tour's Warnsdorff's rule are both worth trying as a first move on a slow
search, since neither risks the answer. But check separately whether the search tries every
starting point / every top-level branch, not just every ordering of one branch — Word Search's own
pitfall is a reminder that giving up after one failed start is a different, riskier shortcut than
reordering, one that can flip a correct "not found" into a wrong one silently. Third,
before writing a backtracking search at all, check whether the decision problem has a name and a
known complexity class. Graph Coloring's own k = 2 special case is the
cleanest lesson available on this site: the general problem can be NP-complete while a specific,
easy-to-miss special case of the exact same problem has a fast, non-backtracking answer sitting one
level up. A few minutes checking whether the problem in front of you is a disguised instance of
something with a known polynomial algorithm can save writing (and pruning, and debugging) a search
that never needed to exist.
| Entry | What rejects a candidate | Order changes | Faster than backtracking? |
|---|---|---|---|
| N-Queens | structural — shared row, column, or diagonal | not measured on this page | not addressed on-page |
| Sudoku | structural — shared row, column, or 3×3 box | speed only — 273/12 (reading order) vs. 165/0 (MRV), same solution | not addressed on-page |
| Graph Coloring | structural — same color on an adjacent vertex | speed only — 84/27 (hub-first) vs. 228/75 (rim-first), same answer | yes, for k = 2 only: bipartiteness, O(V+E) BFS/DFS; no known polynomial algorithm for k ≥ 3 (NP-complete) |
| Hamiltonian Path/Cycle | structural — already-visited vertex, or missing return edge for a cycle | speed only — different neighbor order finds a different valid tour, not a wrong one | no — NP-complete in general, O(n!) naive |
| Word Search | structural — letter mismatch, or cell already in the current path | exhaustiveness, not just order — must try every starting cell, or a real match can be missed | not addressed on-page (polynomial in board size for fixed word length) |
| Knight's Tour | nothing — every unvisited on-board square is legal | speed only, by orders of magnitude — 287/263 vs. 24/0 (5×5); >2,000,000 vs. 63 (8×8) | not addressed on-page |
| Subset Sum | arithmetic — running-sum overshoot, or remaining budget too small | not measured on this page | not addressed on-page |
| Palindrome Partitioning | self-contained — is this candidate piece a palindrome, independent of anything already chosen | not a correctness axis here — every valid piece must eventually be tried either way | not for this question (exponential output); yes for a different one (fewest cuts), O(n²) DP |
| Dancing Links | structural — exact-cover row/column membership, not this page's own reject/place shape | speed only, by orders of magnitude — 4/1 (fewest-candidates) vs 5/2 (leftmost) on its own example; 10 vs 144,436 attempts on a larger purpose-built one | no — general exact cover is NP-complete, same as Hamiltonian Path/Cycle's own answer |
| Branch and Bound | not illegality at all — an optimistic bound that can't beat the best complete value found so far | not applicable — this axis assumes rejection is about validity, which this entry doesn't use | yes for the same data by a different method (dynamic programming, 0/1 Knapsack); no known polynomial algorithm for this search itself |