18. Backtracking

Consider the Prolog database from the previous page:

1. Fact: spouse (john, jane)
2. Fact: spouse (david, mary)
3. Fact: spouse(george, susan)
4. Fact: female (jane)
5. Fact: female (mary)
6. Fact: female (susan)
7. Fact: male (john)
8. Fact: male (david)
9. Fact: male (george)
10. Rule: husband(A,B) IF spouse(A,B) AND male (A)
11. Rule: wife (A,B) IF spouse(A,B) AND female(B)

In the first example, we said 'scan the database'. This implies that all the rules and facts were considered when looking for an exact match. All well and good. But computers can only do one thing at a time - even searching is a one-at-a-time process.

In practical terms, this means the computer will most likely fail to find an exact match on the very first path it chooses to try. And the more facts and rules within the database, the less likely this is to happen.

But the computer will keep on trying different paths by moving back to the point of last success and then try a different path, it will do this until it either finds a perfect match - in which case the goal is 'true', or it fails to find a complete match, in which case the goal is 'false'.

This action of moving up and down various paths is called 'backtracking'.

Example.

Consider the same goal as before

 wife(david,mary)?

The sequence of events for finding and answer will be something like this:

1. Does Rule 10 match the goal - No, try the next rule (backtrack)
2. Does Rule 11 match the goal - Yes
3. Check the first part of the Rule 11: spouse(A,B)
4. Does Fact 1 match spouse(david,mary) - No (backtrack)
5. Does Fact 2 match spouse(david,mary) - Yes
6. Now check the next part of the rule - female(mary)
7. Does Fact 4 match female(mary) - No (backtrack)
8. Does Fact 5 match female(mary) - Yes
9. An exact match to the goal is found - Return TRUE