Community resourceWorksheet

OCR H446 2.2.2 Backtracking: decisions and dead ends

Part 4 of 14 · H446 2.2.2 · Computational methods

Backtracking is examined in H446 2.2.2 as a search that undoes its most recent choice, so a definition alone earns little. A workshop scheduler and a target-total search give students something to follow, and a trace table records the calls, the dead ends and the returns rather than just the final result.

Students will:

  • describe the choice points, constraint tests and dead ends in a search
  • complete a trace table of calls and returns for a backtracking search
  • explain where a search resumes once a branch breaks a constraint
  • justify why the candidate value increases on both the include and the exclude route
  • set out the stored state, the constraint test and what is undone when a room allocation fails

Inside: 7 explanation cells, 1 multiple-choice question, 2 fill-in-the-blanks cells, 2 written answers and 1 trace table. 18 marks, about 25 to 35 minutes.

Series: H446 2.2.2 · Computational methods, part 4 of 14.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Backtracking: decisions and dead ends

A workshop scheduler tries possible activities in limited rooms. Some early choices later make the remaining constraints impossible. Backtracking returns to the most recent choice point and tries another unexplored option.

By the end, you will be able to

  • explain choose, test, undo and retry;
  • identify a dead end and the correct return point;
  • trace a recursive backtracking search;
  • distinguish backtracking from restarting or blindly trying everything.

Reactivate: a recursive call has its own parameters and returns to its caller.

Search with reversible choices

Backtracking search: choose, test, undo and retrydead endundo latest choice; try the next unexplored alternativestartchoice Achoice Bfailsworks?works?works?

A typical routine is: choose an option → update the partial state → test constraints → continue if still possible → undo if the branch fails → try the next option.

Backtracking does not always begin with the leftmost branch, and it does not automatically return to the beginning. It returns to the latest decision that still has an unexplored alternative. A good constraint check can prune an impossible branch before building every completion beneath it.

Worked branch

Target total: 5. Candidate values: 1, 2, 3, 4, each usable at most once.

  • Choose 1, then 2: partial total 3.
  • Choose 3: total 6, so this is a dead end.
  • Undo 3 and try the next available decision.
  • Choosing 4 gives total 7, also a dead end.
  • Backtrack again and explore a different earlier branch, such as 1 + 4 = 5.

The partial state must be restored before the next branch; otherwise decisions from the failed route leak into it.

Multiple choice1 mark

After a branch violates a constraint, where should a backtracking search normally resume?

  • AAt the first line of the whole program
  • BAt a random node
  • CAt the deepest leaf whether or not it has alternatives
  • DAt the latest choice point with an unexplored alternative
Fill in the blanks3 marks
Backtracking makes a gap 1, checks constraints, gap 2 the change after failure, and tries an unexplored gap 3.
  • choice
  • undoes
  • alternative
  • output

Guided trace preparation

The function below explores whether distinct increasing values from 1 to 4 can reach a target. At each call, it first tries include next_value. If that route fails, control returns and it tries exclude next_value. Record the call parameters, then each Boolean returned. Do not treat a failed child call as failure of the whole search until the alternative has also failed.

Trace table60 marks

Trace the calls and returns for target 5.

Enter a value only when it changes; record returned and printed values in order.

Use one row for each statement as it runs. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. def choose(total, target, next_value):
  2. if total == target:
  3. return True
  4. if total > target or next_value > 4:
  5. return False
  6. if choose(total + next_value, target, next_value + 1):
  7. return True
  8. return choose(total, target, next_value + 1)
  10. result = choose(0, 5, 1)
  11. print(result)
Trace table with 10 columns
Rowtotal (choose)target (choose)next_value (choose)resultReturn valueDepthtotal == targettotal > target or next_value > 4choose(total + next_value, target, next_value + 1)Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Written answer4 marks

Explain where backtracking occurs in the function and why next_value increases on both recursive routes.

Refer to the failed include route, return to the caller and distinct candidates.

Students type their answer here.

Independent application: room allocation

A scheduler assigns one room to each activity. A partial allocation is a dead end when an activity has no remaining suitable room. Describe the state that must be stored, the constraint test, and what is undone before another room is tried.

Written answer6 marks

Explain how backtracking could search for a valid room allocation.

Use the terms partial solution, constraint, dead end, undo and alternative.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
After a decision, the algorithm tests a checkpoint gap 1. A branch that cannot lead to a solution is a checkpoint gap 2. Reversing the latest change checkpoint gap 3 the earlier state. Backtracking is a checkpoint gap 4, whereas recursion is one possible control structure used to implement it.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.