Backtracking in Logic Programming
You'll learn how Prolog systematically explores all possible solutions by trying alternatives and undoing failed attempts.
The Core Idea
When Prolog executes a query, it doesn't just find one answer and stop. It searches through all possible ways to satisfy your goal. If a choice leads to failure, Prolog backtracks—it undoes that choice, rewinds to the last decision point, and tries the next alternative. This continues until either a solution is found or all possibilities are exhausted.
Think of it like navigating a maze: you walk down a path until you hit a dead end, then you walk back to the last intersection and try a different route.
How Backtracking Works
When you make a query, Prolog:
- Tries to unify your goal with the first matching fact or rule
- If that succeeds, moves to the next subgoal
- If it fails, backtracks to the previous choice point
- Tries the next alternative clause
- Repeats until success or all options are tried
For example, if you have multiple parent facts and query parent(X, mary), Prolog will find the first matching X, but if you ask for more solutions (typically with ; in the interpreter), it backtracks and finds other values of X that also satisfy the query.
Why It Matters
Backtracking is what makes logic programming "search-based." You describe what you want (the relationships and constraints), and Prolog automatically explores the solution space. You don't write loops or explicit control flow—the backtracking mechanism handles the search strategy for you.
Key Takeaway: Backtracking is Prolog's built-in search engine that automatically explores all possible solutions by trying alternatives and reversing failed choices, making logic programs declarative and flexible.