Learn the vocabulary of undoing a choice the moment a partial solution violates a constraint.
0 / 5 completed
1 / 5
At standup, a dev mentions an algorithm that builds a solution one choice at a time, and the moment a partial solution is found to violate a constraint, it undoes that last choice and tries a different one instead of continuing down a doomed path. What is this technique called?
Backtracking builds a solution one choice at a time and, the instant a partial solution is found to violate a constraint, undoes that last choice and tries a different alternative instead of wasting further effort continuing down a path that was already doomed. Memoization is an unrelated technique about caching return values, not about abandoning invalid partial solutions. This undo-and-retry pattern is exactly what lets backtracking explore a huge space of possible solutions, like placing queens on a chessboard, without ever having to fully explore a branch it's already proven can't succeed.
2 / 5
During a design review, the team adds a constraint check performed after every single partial choice, specifically so an invalid branch is abandoned as early as possible rather than only detected once a complete, doomed solution has been fully built. Which capability does this early check provide?
Checking the constraint after every single partial choice provides pruning invalid branches early, avoiding the wasted work of continuing to build out a partial solution that's already guaranteed to fail once it's already violated a constraint. Waiting to check constraints only once a complete solution has been fully built wastes all the effort spent constructing the rest of a branch that was doomed from an early, easily detectable point. This early-pruning behavior is exactly what makes backtracking practical for problems with a huge space of possible solutions, since it avoids fully exploring the vast majority of branches that could never have worked.
3 / 5
In a code review, a dev notices a backtracking implementation builds every single complete candidate solution in full before ever checking whether it satisfies the problem's constraints. What does this represent?
This is a missed early-pruning opportunity, since waiting until an entire candidate solution is fully built before checking any constraint means the algorithm wastes effort constructing the remainder of a branch that may have already been invalid from a much earlier, easily detectable point. A cache eviction policy is an unrelated concept about discarded cache entries. This late-checking pattern defeats much of backtracking's actual benefit, since early pruning of invalid branches is exactly what keeps the search efficient for a problem with a large space of possible candidate solutions.
4 / 5
An incident report shows a scheduling solver using backtracking took far longer than expected to find a valid assignment, because its implementation only checked constraints once a complete candidate schedule had been fully built, rather than checking after each partial assignment. What practice would prevent this?
Checking the relevant constraints after every partial choice prunes an invalid branch immediately, the moment it first violates a constraint, instead of only discovering the problem once an entire candidate schedule has already been fully built, which is exactly the fix for the slow solver described in this incident. Continuing to check constraints only at the very end is exactly what let the solver waste so much time constructing doomed candidates in full. This early-check, early-prune discipline is the core idea that separates an efficient backtracking implementation from one that's technically backtracking but gets almost none of its practical benefit.
5 / 5
During a PR review, a teammate asks why the team invests effort in checking constraints as early as possible during backtracking instead of just letting the algorithm build every candidate solution fully and filtering out the invalid ones at the very end. What is the reasoning?
Checking constraints as early as possible prunes an invalid branch the moment it first becomes invalid, avoiding all the further wasted work of continuing to build out the rest of what's already a doomed candidate, whereas filtering only at the very end pays that full wasted cost for every single invalid branch the search happens to construct. For a problem with a large space of possible candidates, this difference compounds dramatically, since early pruning can eliminate huge doomed subtrees in a single check rather than exploring them in their entirety. The tradeoff is that early constraint checks need to be cheap enough to run frequently, since a constraint check that's itself expensive can eat into the very savings it's meant to provide.