Skip to main content

Working Backwards from the Goal Shrinks the Search

What This Concept Is​

Working backwards is the heuristic of starting from the desired conclusion and asking "what would have to be true just before this?" Repeated, the question narrows the search space dramatically.

Concretely, the same move takes a different shape in each domain:

  • in proofs: "what lemma would immediately give me the goal?"
  • in algorithms: "what state would the final step operate on?"
  • in debugging: "what input produced this output?"
  • in planning: "what decision puts me one move from done?"
  • in architecture: "what interface, if given to me, would make this easy?"

Working backwards is most effective when the conclusion is concrete and the given is diffuse. Forward search starts in a wide region of possibilities and has to navigate toward a narrow target; backward search starts at the narrow target and has to navigate toward a wide source. The asymmetry usually favours backward.

A key distinction: working backwards is a discovery procedure, not a proof style. You reason backwards to find the chain; then you write it forward to make the argument. The two directions must agree -- every backward step "$B$ implies $A$" must read, in the forward write-up, as "from $B$ I can derive $A$" (an implication that holds). If the implication is merely "$A$ suggests $B$", the chain is broken.

Distinguish working backwards from two nearby moves:

  • contradiction starts from the negation of the goal, not the goal, and derives absurdity. Working backwards starts from the goal itself and derives prerequisites.
  • construction builds the object forward from the given. Working backwards finds the pivot state the forward construction needs to reach, then the forward pass completes it.

Why It Matters Here​

Forward search over a large solution space is often exponential or worse. Backward search can push through a much smaller funnel because each backward step restricts the prerequisites instead of expanding the possibilities.

In CS, working backwards appears in:

  • dynamic programming (the value at the final state determines the recurrence; base cases are derived last, not first)
  • parsing (accept state and reverse transitions determine what the tokenizer must produce)
  • retrosynthesis and automated planning (literally backward-chaining search)
  • test-driven development (the desired assertions drive the implementation)
  • regression debugging (given the observed bad output, reason backwards to the input that caused it)
  • game theory / chess endgames (retrograde analysis -- work back from checkmate)

Forward pipeline: Semester 2 (DP recurrences, backward induction), Semester 4 (debugging via post-mortem inference), Semester 5 (protocol correctness via desired post-condition), Semester 7 (architecture decisions: "what would this look like in a year?" is a backward question).

Concrete Examples​

Example 1 -- the jug puzzle​

Problem: Measure exactly 4 liters using a 3-liter jug and a 5-liter jug.

Forward search explores many move sequences, most dead ends. Backward:

  • Goal state. The 5-liter jug contains 4 liters.
  • One step before. Either remove 1 from a full 5, or add 4 to an empty 5. "Add 4" is impossible in one step. "Remove 1" means the 3-jug absorbed 1 from a full 5. For that to work, the 3-jug must have had capacity exactly 1 -- i.e. it held 2 -- just before pouring.
  • Two steps before. The 3-jug holds 2. How? Either we just emptied it partially (not legal -- the jugs only support pour-until-full or pour-until-empty), or the 5-jug had 2, we poured into the 3-jug (empty), and the 3-jug now holds 2.
  • Three steps before. The 5-jug holds 2. How? We filled the 5-jug (5), poured into an empty 3-jug until 3 was full (5 - 3 = 2 remains in 5-jug).

Reverse the chain for the forward write-up:

  1. Fill 5-jug. $(0, 5)$ where pairs are $(3\text{-jug}, 5\text{-jug})$.
  2. Pour 5-jug into 3-jug until 3-jug is full. $(3, 2)$.
  3. Empty 3-jug. $(0, 2)$.
  4. Pour 5-jug into 3-jug. $(2, 0)$.
  5. Fill 5-jug. $(2, 5)$.
  6. Pour 5-jug into 3-jug until 3-jug is full (adds 1). $(3, 4)$. Done.

The backward pass found the pivot state "$5$-jug holds $2$". Forward search would have needed to explore most of the configuration graph.

Example 2 -- finding a proof by backward chaining​

Problem: Show that if $n$ is odd then $n^2 + 1$ is even.

Backward from the goal:

  • Goal. $n^2 + 1$ is even.
  • One step before. $n^2 + 1 \equiv 0 \pmod{2}$, equivalently $n^2 \equiv 1 \pmod{2}$.
  • Two steps before. $n^2$ is odd.
  • Three steps before. $n$ is odd (since odd $\times$ odd $=$ odd). This is the given.

Forward write-up (reversing the chain): $n$ is odd $\Rightarrow$ $n = 2k + 1$ for some integer $k$ $\Rightarrow$ $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, odd $\Rightarrow$ $n^2 + 1$ is even. The proof is short because the backward pass already identified every step.

Common Confusion / Misconceptions​

Skipping to the answer. Working backwards is not "write down what I want and hope." Each backward step must be reversible: if $B$ implies $A$ (your goal) and also $C$ implies $B$, then $C$ is a valid new goal only if the implications are forward-valid. In proofs, backward reasoning discovers the structure; the final write-up must be forward.

Direction drift. Losing track of direction. Write GOAL: at the top and annotate each backward step with a reverse arrow ($\leftarrow$). When you flip to write-up, reverse the arrows and make sure each forward $\Rightarrow$ holds.

"Backwards cheats." Believing backward reasoning "cheats" in proof writing. It does not. It is a discovery procedure, not a proof style. Most clever proofs you admire were discovered backwards and written forward.

Working backwards from the wrong goal. If your problem has multiple equivalent restatements, working backwards from a poorly-chosen one produces chains that get longer, not shorter. Pick the most concrete form of the goal before starting.

How To Use It​

Backward-reasoning protocol:

  1. Write the desired final state or conclusion at the top.
  2. Ask: what is the last step that would produce this?
  3. Write the prerequisite state or statement.
  4. Check: is the implication prerequisite $\Rightarrow$ conclusion valid in the forward direction?
  5. Repeat until the prerequisite is the given (or a known-solvable subproblem).
  6. Reverse the chain for the final write-up.
  7. Before submitting, re-read forward and verify every $\Rightarrow$ is justified.

Backward reasoning that uses biconditionals ($\Leftrightarrow$) is safest -- the chain is reversible by definition. Implications in only one direction require the explicit check in step 4.

Transfer / Where This Shows Up Later​

  • Semester 2 (DP). Every DP problem starts with the value at the final state. The recurrence is derived backwards; the base cases are what you fall back to.
  • Semester 2 (algorithmic game theory). Retrograde analysis in combinatorial games is backward induction.
  • Semester 3 (test-driven development). TDD starts with the assertion and works backwards to the code that would make it pass.
  • Semester 4 (debugging). Given a stack trace or a bad output, work backwards: "what state would produce this? what step produced that state?"
  • Semester 5 (protocol design). "What must the final commit message look like?" is the starting point for a distributed protocol.
  • Semester 7 (architecture). ADRs often begin with "the system we want in one year" and work backwards to this quarter's decision.
  • Semester 10 (capstone). Working backwards from the demo day scope keeps the weekly plan honest.

Check Yourself​

  1. Why is a backward chain of reasoning usually smaller than a forward one for the same problem? Is this always true?
  2. What does "reversible step" mean when reasoning backwards in a proof? What happens if a step is reversible backwards but not forwards?
  3. Give an example from Module 2 (graphs) where working backwards would shorten a search.
  4. What is the difference between working backwards and proof by contradiction? Give a problem where one works and the other does not.
  5. How does working backwards connect to dynamic programming's "value iteration"? State the analogy in one sentence.

Mini Drill or Application​

Drill A. Solve by working backwards, writing each step: Find the smallest positive integer $n$ such that $n^2 + 1$ is divisible by 13.

Start: $13 \mid n^2 + 1$ $\Leftrightarrow$ $n^2 \equiv -1 \equiv 12 \pmod{13}$. Continue until you can enumerate $n \in {1, 2, \dots, 12}$ and pick the smallest.

Drill B. A chess knight is on $a1$ and must reach $h8$ in the fewest moves. Work backwards from $h8$, not forwards from $a1$. Enumerate squares at BFS-depth 1, 2, 3, ... until $a1$ appears, then read off the path.

Drill C (unseen). Problem: A lily pad doubles in size every day and covers the whole pond on day 30. On which day does it cover half the pond? Solve by working backwards from day 30 and state why forward reasoning would be slower.

Read This Only If Stuck​