Tensions in Practice: Simple rollback in tension with skipping irrelevant choices¶
Finite search · explicit conflict explanation
A small search chooses A, B and C in that order. A and B can each be 0 or 1; C can only be 0. The completed triple must satisfy A ≠ C, meaning A and C must differ. A chronological search tries B’s other value after the first failure. A conflict-aware search proves B cannot change this failure and jumps back to A. Both find the same valid triple, but one pays for an explanation to skip a branch.
Keep rollback machinery simple
Try the next recent alternative without extracting a separate reason for each failure.
Avoid alternatives that cannot resolve the conflict
Use a sound explanation to skip choices irrelevant to the failed constraint.
Why these aims pull against each other
A failed check tells a simple search that one triple failed. A sound conflict explanation tells a stronger search that every triple with A = 0 fails because C has no other value, regardless of B.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Text states carry the meaning; color is not a measured score or universal preference.
What this choice protects
What it costs
When it fits
Compare the arrangements
Recent choice first
When C has no alternative, move back to B before moving back to A. All alternatives are tried in order 0 then 1.
| A B C | Check | |
|---|---|---|
| Check 1 | 0 0 0 | Fails |
| Check 2 | 0 1 0 | Fails |
| Check 3 | 1 0 0 | Passes |
- What it protects
- The rollback rule needs only the choice stack and pass/fail result.
- What it costs
- It checks 0 1 0 even though changing B cannot repair A = C.
- When it fits
- Conflicts are cheap to test, branches are small, or extracting sound explanations costs more than the avoided work.
Illustration note: The checker runs after a complete triple in this stipulated example; no forward constraint propagation is used by either arrangement.
Explain and jump
After 0 0 0 fails, use the failed A ≠ C constraint and C’s singleton domain to rule out A = 0 for every B.
| A B C | Check | |
|---|---|---|
| Check 1 | 0 0 0 | Fails |
| Check 2 | 1 0 0 | Passes |
| Check 3 | None | Already done |
- What it protects
- The second check is the successful 1 0 0; the irrelevant B alternative is skipped.
- What it costs
- The search must extract, validate and retain enough conflict information to justify the jump. An unsound explanation could skip a solution.
- When it fits
- Reliable explanations are available and avoided subtrees justify their processing cost.
Illustration note: The explanation includes C’s complete domain. A single failed value of C would not by itself justify skipping all its alternatives. B is reselected after the jump; no independent state is silently kept.
What this illustration does—and does not—establish
Backtracking: Recency Rollback versus Conflict-Directed Backjump (scopal) supplies conflict-directed jumping. The small domains expose exactly why B is irrelevant and make the skipped work checkable.
- This is feasibility search, not optimization or a claim of a globally fastest algorithm.
- All choices and domains are finite and reversible; no external effects are undone.
- The two versus three checks exclude the extra work of deriving the conflict explanation.
Source entries
Backtracking
Backtracking: Recency Rollback versus Conflict-Directed Backjump (scopal) supplies the conflict examined here.
Recency Rollback versus Conflict-Directed Backjump (scopal)
The default reverses the *most recent* commitment, on the assumption the conflict surfaced at the deepest decision — but the true cause may lie several decisions back, where backjumping should leap.