Free A-Level Computer Science guide

Backtracking and heuristics: explore choices and learn when to undo them

Assign activities to slots without clashes, follow a branch that fails, and see exactly which state is undone before another choice is tried. Then evaluate how a heuristic can change speed or answer quality.

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

The idea to start with

Backtracking builds a partial candidate, rejects choices that violate constraints and returns to earlier decisions when a branch cannot lead to a complete solution. Undoing the branch's state lets the next alternative start from the correct partial candidate.

A heuristic is a practical rule guiding choices. It can reorder an exact search without discarding necessary alternatives, or create a quick approximate answer by committing to locally attractive choices. Those uses have different correctness and optimality consequences.

OCR H446 · 2.2.2(f): backtracking and heuristics; reinforces 2.2.1(b), 2.3.1(a–b)

Before you start

Useful foundations

Functions and recursive calls
Lists, dictionaries and Boolean conditions
Valid solutions versus optimal solutions

By the end, you should be able to

Represent choices and constraints for a finite search problem.
Trace a failed branch and the removal of its assignment.
Explain termination and what an exhausted search establishes.
Distinguish a search-order heuristic from a greedy approximation.

Represent an original clash-free activity problem

A club assigns A, B and C to slots 1 or 2. A clashes with B; B clashes with C. Those pairs need different slots, while A and C can share.

Availability domains are A:[1,2], B:[1], C:[1,2]. B’s instructor allows only slot 1. Store clashes separately and chosen assignments in a partial dictionary.

Seek any complete valid assignment: no optimisation objective is given. Try activities A,B,C and each listed domain in order. Changing order changes failed work, without changing validity; “first valid” is acceptable here.

Choose, test, recurse and restore state

At activity index i, compare each candidate with already assigned clashes. Reject a same-slot clash immediately; later choices cannot repair it.

At the base case, copy the complete assignment. Returning None means that branch exhausted every permitted alternative. Recursion increases i and finite domains bound the loops, so the search terminates.

Maximum call depth is the activity count plus the base-case call. With n two-choice activities, exhaustive search can face 2^n complete candidates before pruning. Early rejection reduces work but does not guarantee fast large cases.

Backtracking: choose, explore, then restore

Choose and test
Try a slot; reject it if it clashes with a chosen neighbour.
Record
Store the permitted activity/slot assignment.
Explore
Recursively place the next activity. A base-case success is copied.
Restore
Delete this choice after the recursive return, so a stale assignment cannot contaminate another branch.
Continue or return
Return the copied solution if found; otherwise try the next slot.

This implementation restores after every recursive return, including success; the solution copy survives independently.

Separate heuristic ordering from heuristic commitment

Most-constrained-first starts with B, whose domain has one slot. B=1 forces A and C to try 2, avoiding the A=1 dead end. If all necessary alternatives remain, ordering preserves completeness of this finite exact search.

A greedy heuristic commits locally without revisiting. For value 6 with coins 1,3,4, largest-affordable chooses 4+1+1: three coins. 3+3 uses two, so validity does not guarantee the fewest coins.

Choose a relevant feature and judge the result. A scheduling rule may reduce failed search; a route rule may meet a deadline with a usable but unproven best answer.

Timeout means no solution found yet. Only complete exhaustion of the required search proves none exists under a correct model and algorithm.

Two ways a heuristic can guide work

Order an exact search: Try promising choices first, keeping necessary alternatives available. Completeness can remain.
Commit to an approximation: Choose locally and never revisit. A valid answer can be worse than another answer.

Worked example

Trace the rejected assignment and the successful retry

Choose A = 1. B's only candidate is 1, but A and B clash, so it is rejected. B has no alternatives and returns None.
Resume A's call and delete A = 1. The partial assignment becomes empty. Try A = 2.
B = 1 now differs from A's slot, so record it. For C, slot 1 clashes with B and is rejected; slot 2 is accepted because C does not clash with A.
At the base case copy {'A': 2, 'B': 1, 'C': 2}. The calls restore their local choices and return that copy. The printed result has exactly those entries.

Key search states in listed candidate order
Event	Partial assignment	Consequence
A tries 1	{A: 1}	B has no permitted candidate
Undo A	{}	Restore state for another branch
A tries 2, B tries 1	{A: 2, B: 1}	C cannot use 1
C tries 2	{A: 2, B: 1, C: 2}	Complete valid assignment

backtrack_slots.py — Python 3, explicit restorationPython

def assign_slots(activities, domains, clashes):
    assigned = {}

    def search(i):
        if i == len(activities):
            return assigned.copy()
        activity = activities[i]
        for slot in domains[activity]:
            conflict = any(
                other in clashes[activity] and other_slot == slot
                for other, other_slot in assigned.items()
            )
            if conflict:
                continue
            assigned[activity] = slot
            result = search(i + 1)
            del assigned[activity]
            if result is not None:
                return result
        return None

    return search(0)


activities = ["A", "B", "C"]
domains = {"A": [1, 2], "B": [1], "C": [1, 2]}
clashes = {"A": {"B"}, "B": {"A", "C"}, "C": {"B"}}
print(assign_slots(activities, domains, clashes))

Worked example

Use boundary cases to check the result contract

An empty activities list returns an empty dictionary, a complete valid assignment for no activities. It is different from None.
If B has an empty domain, there is no assignment in this model and the complete search returns None. Missing dictionary entries are outside the stated representation precondition.
If all three activities pairwise clash and each has only slots 1 and 2, no complete assignment exists: three mutually clashing activities require three distinct slots. Exhausting the two-slot search returns None.
Domains and the symmetric clash relation are assumed to describe every listed activity correctly. An omitted clash can produce a model-valid result that is invalid for the club, linking search correctness back to abstraction quality.

Original A-Level practice

5 original questions total 23 marks. Attempt each before opening the independently written indicative marking guidance.

Question 1

5 marks

Trace the worked activity problem until A is tried in slot 2. Explain why the first branch fails and what is removed before the retry.

Show solution and marking guidance

Indicative answer

First choose A = 1 (1). B can only use slot 1 (1), which clashes with A (1), so B exhausts its domain and returns failure (1). Delete A's assignment before trying A = 2 (1).

Question 2

4 marks

Activities X and Y clash. Domains are X [1, 2], Y [1]. Using X then Y in the displayed search, give the returned assignment and explain the rejected branch.

Show solution and marking guidance

Indicative answer

X = 1 is tried first (1), leaving no valid slot for Y because it also only permits 1 (1). Retry X = 2 (1), then return {'X': 2, 'Y': 1} (1).

Question 3

4 marks

Explain the distinct results {} and None for this function. State one reason the shown finite search terminates.

Show solution and marking guidance

Indicative answer

{} is a valid complete assignment when no activities were requested (1). None means the required search found no complete valid assignment (1). Recursive calls advance toward the number-of-activities base case (1) and each candidate domain is finite (1).

Question 4

4 marks

Apply the largest-affordable-coin heuristic to value 6 using coins 1, 3 and 4. Give a better result and explain what this shows about the heuristic.

Show solution and marking guidance

Indicative answer

It chooses 4, then 1, then 1 (1), giving three coins (1). Choosing 3 + 3 uses two coins (1), showing a valid greedy answer need not minimise the total coin count (1).

Question 5

6 marks

Compare assigning the most constrained activity first in a complete search with a greedy method that never revisits choices. Include the interpretation of a search stopped by a time limit.

Show solution and marking guidance

Indicative answer

Most-constrained-first changes candidate ordering using limited availability (1), which can expose failure earlier (1).
If all necessary alternatives remain explored, exact search completeness is preserved (1).
A greedy method commits locally and may miss a better or valid complete solution (1).
A timeout means no solution has been found within that limit (1), not that exhaustive search has proved none exists (1).

Specification and references

This guide addresses OCR H446 2.2.2(f): backtracking and heuristics; reinforces 2.2.1(b), 2.3.1(a–b). Check your examination year and the complete specification for the assessment scope.

These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael

Free A-Level Computer Science guide

Backtracking and heuristics: explore choices and learn when to undo them

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

The idea to start with

OCR H446 · 2.2.2(f): backtracking and heuristics; reinforces 2.2.1(b), 2.3.1(a–b)

Before you start

Useful foundations

Functions and recursive calls
Lists, dictionaries and Boolean conditions
Valid solutions versus optimal solutions

By the end, you should be able to

Represent choices and constraints for a finite search problem.
Trace a failed branch and the removal of its assignment.
Explain termination and what an exhausted search establishes.
Distinguish a search-order heuristic from a greedy approximation.

Represent an original clash-free activity problem

A club assigns A, B and C to slots 1 or 2. A clashes with B; B clashes with C. Those pairs need different slots, while A and C can share.

Availability domains are A:[1,2], B:[1], C:[1,2]. B’s instructor allows only slot 1. Store clashes separately and chosen assignments in a partial dictionary.

Choose, test, recurse and restore state

At activity index i, compare each candidate with already assigned clashes. Reject a same-slot clash immediately; later choices cannot repair it.

Backtracking: choose, explore, then restore

Choose and test
Try a slot; reject it if it clashes with a chosen neighbour.
Record
Store the permitted activity/slot assignment.
Explore
Recursively place the next activity. A base-case success is copied.
Restore
Delete this choice after the recursive return, so a stale assignment cannot contaminate another branch.
Continue or return
Return the copied solution if found; otherwise try the next slot.

This implementation restores after every recursive return, including success; the solution copy survives independently.

Separate heuristic ordering from heuristic commitment

A greedy heuristic commits locally without revisiting. For value 6 with coins 1,3,4, largest-affordable chooses 4+1+1: three coins. 3+3 uses two, so validity does not guarantee the fewest coins.

Choose a relevant feature and judge the result. A scheduling rule may reduce failed search; a route rule may meet a deadline with a usable but unproven best answer.

Timeout means no solution found yet. Only complete exhaustion of the required search proves none exists under a correct model and algorithm.

Two ways a heuristic can guide work

Order an exact search: Try promising choices first, keeping necessary alternatives available. Completeness can remain.
Commit to an approximation: Choose locally and never revisit. A valid answer can be worse than another answer.

Worked example

Trace the rejected assignment and the successful retry

Choose A = 1. B's only candidate is 1, but A and B clash, so it is rejected. B has no alternatives and returns None.
Resume A's call and delete A = 1. The partial assignment becomes empty. Try A = 2.
B = 1 now differs from A's slot, so record it. For C, slot 1 clashes with B and is rejected; slot 2 is accepted because C does not clash with A.
At the base case copy {'A': 2, 'B': 1, 'C': 2}. The calls restore their local choices and return that copy. The printed result has exactly those entries.

Key search states in listed candidate order
Event	Partial assignment	Consequence
A tries 1	{A: 1}	B has no permitted candidate
Undo A	{}	Restore state for another branch
A tries 2, B tries 1	{A: 2, B: 1}	C cannot use 1
C tries 2	{A: 2, B: 1, C: 2}	Complete valid assignment

backtrack_slots.py — Python 3, explicit restorationPython

def assign_slots(activities, domains, clashes):
    assigned = {}

    def search(i):
        if i == len(activities):
            return assigned.copy()
        activity = activities[i]
        for slot in domains[activity]:
            conflict = any(
                other in clashes[activity] and other_slot == slot
                for other, other_slot in assigned.items()
            )
            if conflict:
                continue
            assigned[activity] = slot
            result = search(i + 1)
            del assigned[activity]
            if result is not None:
                return result
        return None

    return search(0)


activities = ["A", "B", "C"]
domains = {"A": [1, 2], "B": [1], "C": [1, 2]}
clashes = {"A": {"B"}, "B": {"A", "C"}, "C": {"B"}}
print(assign_slots(activities, domains, clashes))

Worked example

Use boundary cases to check the result contract

An empty activities list returns an empty dictionary, a complete valid assignment for no activities. It is different from None.
If B has an empty domain, there is no assignment in this model and the complete search returns None. Missing dictionary entries are outside the stated representation precondition.
If all three activities pairwise clash and each has only slots 1 and 2, no complete assignment exists: three mutually clashing activities require three distinct slots. Exhausting the two-slot search returns None.
Domains and the symmetric clash relation are assumed to describe every listed activity correctly. An omitted clash can produce a model-valid result that is invalid for the club, linking search correctness back to abstraction quality.

Original A-Level practice

5 original questions total 23 marks. Attempt each before opening the independently written indicative marking guidance.

Question 1

5 marks

Trace the worked activity problem until A is tried in slot 2. Explain why the first branch fails and what is removed before the retry.

Show solution and marking guidance

Indicative answer

First choose A = 1 (1). B can only use slot 1 (1), which clashes with A (1), so B exhausts its domain and returns failure (1). Delete A's assignment before trying A = 2 (1).

Question 2

4 marks

Activities X and Y clash. Domains are X [1, 2], Y [1]. Using X then Y in the displayed search, give the returned assignment and explain the rejected branch.

Show solution and marking guidance

Indicative answer

X = 1 is tried first (1), leaving no valid slot for Y because it also only permits 1 (1). Retry X = 2 (1), then return {'X': 2, 'Y': 1} (1).

Question 3

4 marks

Explain the distinct results {} and None for this function. State one reason the shown finite search terminates.

Show solution and marking guidance

Indicative answer

{} is a valid complete assignment when no activities were requested (1). None means the required search found no complete valid assignment (1). Recursive calls advance toward the number-of-activities base case (1) and each candidate domain is finite (1).

Question 4

4 marks

Apply the largest-affordable-coin heuristic to value 6 using coins 1, 3 and 4. Give a better result and explain what this shows about the heuristic.

Show solution and marking guidance

Indicative answer

It chooses 4, then 1, then 1 (1), giving three coins (1). Choosing 3 + 3 uses two coins (1), showing a valid greedy answer need not minimise the total coin count (1).

Question 5

6 marks

Compare assigning the most constrained activity first in a complete search with a greedy method that never revisits choices. Include the interpretation of a search stopped by a time limit.

Show solution and marking guidance

Indicative answer

Most-constrained-first changes candidate ordering using limited availability (1), which can expose failure earlier (1).
If all necessary alternatives remain explored, exact search completeness is preserved (1).
A greedy method commits locally and may miss a better or valid complete solution (1).
A timeout means no solution has been found within that limit (1), not that exhaustive search has proved none exists (1).

Specification and references

This guide addresses OCR H446 2.2.2(f): backtracking and heuristics; reinforces 2.2.1(b), 2.3.1(a–b). Check your examination year and the complete specification for the assessment scope.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael