Mutable State and Undo

Often, a shared board array is mutated: set field, recursive call, reset field. An alternative is immutable copies (more expensive).

Source of errors: forgetting the undo, then the next branch is contaminated.

Where used

In-place backtracking saves allocations; undo must be exact. The same pattern is found in editors (command stack) and in transactions with rollback.

Depth

Mutable state avoids copying large sub-candidates. A recursion level makes a small change, calls the next step, and then undoes exactly that change. This pattern is efficient but requires strict symmetric treatment of forward and backward operations.

The undo operation must also occur when the recursive call does not find a solution or collects multiple solutions. An alternative strategy produces a new immutable structure for each branch. This is often easier to check but requires more allocations and copying work.

Difficulty levels

1. Specify the appropriate inverse operation for each mutation.
2. Consistently update and reset multiple coupled structures.
3. Weigh between copying and undo based on size and risk of error.

Pitfalls

An early return can skip the undo. Flat copies of nested lists are equally problematic because inner objects are still shared, and changes may seep into other branches.