Two runs of one backtracking search on the same input differ by an hour; why does choice order matter that much?
answer
- the tree is not fixed
- same space, different walk
- where the contradiction is discovered
- fewest surviving options first
- fail first, succeed first
basics
~20 sThe tree an exhaustive search walks is not fixed by the problem; it is created by the order decisions are made. Ordering that forces contradictions near the root cuts enormous subtrees early, while a poor order discovers the same contradictions at the leaves.
solid answer
~50 sThe problem defines the *space* of complete assignments, but the **search tree is a product of the order you branch in**. Two rules do most of the work. **Fail first** on variables: branch next on the most constrained decision — the one with the fewest surviving options — so a contradiction appears near the root, where a single cut removes a whole subtree instead of one leaf. **Succeed first** on values: within the chosen decision, try the option most likely to complete, so a good incumbent appears early and strengthens every later comparison. Both depend on **propagation**: after each assignment you shrink the remaining options and detect emptiness immediately. None of this changes the exponential worst case — it changes which tree you actually walk, and on structured instances that is the difference between seconds and hours.
go deeper
Recall that a search that tries choices in a smarter order can finish far sooner on the same input, because it discovers impossible combinations before exploring everything beneath them.
Explain fail-first variable ordering and succeed-first value ordering, and why propagation is what supplies the surviving-option counts both rules rank by. Be able to say why neither changes the worst case.
Show the operational habit: instrument nodes explored and dead ends per second, compare ordering rules on real instance families, and cap plus restart when the runtime distribution proves heavy-tailed.
Frame ordering as tuning against an instance distribution, not a universal improvement. Decide how much bookkeeping per node the workload justifies and whether a predictable nightly runtime beats a faster average one.
## The tree is chosen, not given An exhaustive backtracking search over an overnight planning problem assigns decisions one at a time, backing up whenever the partial assignment becomes impossible. It is tempting to speak of *the* search tree as though the problem determines it. It does not. The problem determines the set of complete assignments; the **order** in which you branch determines the tree that reaches them, and two orders over the same instance can produce trees whose explored sizes differ by orders of magnitude. That is why the same code, the same input and a different ordering rule can finish in a second or still be running an hour later. ## Fail first: choosing the next decision The standard variable-ordering rule is **fail first**: branch next on the decision with the *fewest remaining legal options*, or equivalently the one most tightly constrained by what is already fixed. The reasoning is about where contradictions get discovered: - A decision with two surviving options splits the subtree two ways; a decision with fifty splits it fifty ways. - If the current partial assignment is already doomed, you want to find out **now**. Branching on the tight decision reaches the contradiction in one or two levels. - The same contradiction, reached at depth thirty instead of depth two, has already been re-derived once per leaf beneath it. That is the hour. A useful way to say it in an interview: ordering does not reduce the number of dead ends, it changes **how much work each dead end costs you**. ## Succeed first: choosing which option to try Value ordering is the mirror image. Having chosen the decision, try the option **most likely to lead to a complete plan** — the least constraining one, the one that removes fewest options elsewhere. This matters for a different reason. Any search carrying a cost bound prunes by comparing against the best complete plan found so far, and that comparison is worthless until a complete plan exists. Reaching one early: - gives later comparisons something to bite on from near the root; - converts a plain enumeration into a genuinely pruned search sooner; - gives a deadline-stopped run something to return. | | Variable ordering | Value ordering | |---|---|---| | Rule of thumb | fail first | succeed first | | Picks | which decision to branch on | which option to try first | | Goal | reach contradictions near the root | reach a complete plan early | | Pays off when | the instance is over-constrained | the instance has many solutions | The two rules pull in opposite directions on purpose, and that is not a contradiction: one is about which subtree you split, the other about which child you visit first. ## Propagation is what makes ordering measurable Both rules need a live count of surviving options, and that count comes from **propagation**: after every assignment, walk the constraints and remove options elsewhere that are now impossible. 1. Assign a decision. 2. Remove newly impossible options from the other decisions. 3. If any decision has no options left, the partial assignment is dead — back up immediately. 4. If any decision has exactly one option left, fix it and repeat from step 2. Step 4 is the cheap win: forced assignments cascade, and a chain of them can settle a large part of the plan without branching at all. Step 3 is the fail-first detector. Without propagation, a fail-first rule has nothing to rank by. ## Runtimes are heavy-tailed, so restarts help On hard instances, the runtime of a randomised backtracking search is not clustered around a typical value: most runs are quick and a minority take enormously longer, because an unlucky early branch commits the search to a barren region it cannot cheaply escape. The practical response is **restarting**: cap the run, restart with a different ordering or randomised tie-breaking, and keep whatever the run learned about dead regions. You are sampling the distribution rather than betting everything on one draw. ## What ordering cannot do - **It does not change the worst case.** On an adversarial instance every order enumerates the space. Ordering is an engineering lever, not a complexity result. - **It does not guarantee improvement.** A fail-first rule is a heuristic about instances, and on some it loses to a naive order. - **It is not free.** Maintaining surviving-option counts costs work at every node, and on cheap constraints that bookkeeping can outweigh the pruning it enables. The honest summary is that ordering plus propagation is how exponential search becomes usable on *structured* instances — and that a claim of a speed-up is a claim about your instance family, which means it has to be measured, not assumed.
- Why do fail-first variable ordering and succeed-first value ordering not contradict each other?They answer different questions. Variable ordering picks which decision splits the subtree, and a tight one makes any contradiction cheap to discover. Value ordering picks which child of that decision to enter first, and the most promising option reaches a complete plan soonest. One is about the shape of the split, the other about the order of descent.
- What does restarting a stalled search with different ordering actually exploit?The heavy-tailed runtime distribution of randomised backtracking: most runs finish fast, a few are pathologically long because of an unlucky early commitment. A capped run plus a restart re-samples that distribution instead of waiting out the worst draw, and anything learned about dead regions can be carried across.
saying these in an interview costs you the question
- Saying the search tree is determined by the problem, not the ordering
- Claiming good ordering makes exhaustive search polynomial
- Branching first on the decision with the most options to keep things open
- Treating propagation as an optimisation rather than what ordering rules rank by
- Assuming an ordering rule that helped one instance family helps all of them