Backtracking in Rules
We can also have backtracking in rules.
For example consider the following program.
hold_party( X ) :- birthday( X ), happy( X ).
birthday( tom ).
birthday( fred ).
birthday( helen ).
happy( mary ).
happy( jane ).
happy( helen ).
If we now pose the query
?- hold_party( Who ).
In order to solve the above query,
- Prolog first attempts to find a clause of
birthday, it being the first subgoal of birthday.
This binds X to tom.
- We then attempt the goal
happy(tom).
This will fail, since it doesn't match the above database.
- As a result, Prolog backtracks.
This means that Prolog goes back to its last choice point and sees if there is an alternative solution.
In this case, this means going back and attempting to find another clause of
birthday.
- This time we can use clause two, binding
X to fred.
This then causes us to try the goal happy(fred).
Again this will fail to match our database.
- As a result, we backtrack again.
This time we find clause three of
birthday, and bind X to helen, and attempt the goal happy(helen).
This goal matches against clause 3 of our happy database.
- As a result,
hold_party will succeed with X=helen.