Backtracking (Working Backward)

By the end you should be able to: Apply the working-backward strategy to problems with a known goal state, and distinguish it from algorithmic backtracking as used in search.

Working backward means starting at the goal and reasoning towards the starting position, rather than the other way round.

It is the right choice when the end state is precisely known but the route to it is not — and especially when there are many possible starting moves but few ways to arrive at the goal.

Why reversing direction helps

Consider a maze with one entrance and one exit. From the entrance there might be dozens of paths, most leading nowhere. From the exit, often only one or two corridors arrive at it. Searching from the exit means examining far fewer dead ends.

The general rule: work from whichever end has fewer options.

Two different meanings of "backtracking"

The syllabus lists this topic as "Backtracking (Working backward)", and the two ideas are related but not identical. Keep them apart.

1. Working backward (the strategy in this module). Start at the goal, reason towards the start. A planning technique. Used by people solving puzzles, proving theorems, and planning projects from a deadline.

2. Backtracking (the search algorithm). Explore forward; when you hit a dead end, undo the last choice and try the next alternative. Used for the N-Queens problem, Sudoku, and maze solving.

They share the intuition of reversing a step, but the first reverses direction of reasoning while the second reverses a decision already made. An exam question about "working backward" wants the first.

Where working backward is used

Project planning. The submission is due 30 November. Work back: draft by 15 November, experiments by 1 November, literature by 15 October.
Mathematical proofs. Assume the conclusion, determine what would establish it.
Puzzles where the final configuration is given.
Debugging. Start from the wrong output and reason backwards to the cause. This is often the fastest route to a bug.

When it doesn't help

If the goal is vague ("make the program faster"), there is no definite end state to work back from. Working backward needs a concrete, specified goal — which is another reason making problems well-defined comes first.