Backtracking Algorithms (OCR A-Level Computer Science): Flashcards

Technique to systematically search solutions; abandons invalid paths to try alternatives

Decision trees, combinatorial optimisation, constraint satisfaction

Abandons path and tries different one

Choose a path/start with initial partial solution

Expand if valid, backtrack if invalid

Place $N$ queens on $N \times N$ board, none threaten each other

Explores all possibilities in organised manner

Quickly eliminates paths not meeting constraints

Simple to implement using recursion

Inefficient, may explore many possibilities

$O(2^n)$ for certain problems

Leads to incorrect solutions

Causes infinite recursion

Combinatorial and constraint satisfaction problems

Can lead to stack overflow for deep recursive calls