Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.
"Datalogs" was used to solve the following logic puzzle. From a puzzle book Penny Press (1997). Logic problems 19. Norwalk, CT: Penny Press., p. 7. .
3. Setup
Five of Carmi Parker's friends went on vacation at the same time last winter, and Carmi was delighted to watch each person's dog (no two of which are the same breed) while that friend was away. From the information provided, can you determine the first and last names (one first name is Kay, and one surname is Fankle) of the owner of each dog (one dog, ironically enough, is named Kitty), as well as the breed of each dog.
4. Friends
5. Rules
1. Carole (who is neither the one surnamed Peters nor the owner of the dog named Fido) owns the German shepherd.
2. The one surnamed Baxter owns the Dalmation (which isn't the dog named Alex). Alex isn't the golden retriever.
3. Alice (who is neither the one who owns the cocker spaniel nor the one who owns the Dalmation) is Sheba's owner.
4. Four of the owners are the one surnamed Johannson (who doesn't own the cocker spaniel), Heidi, the one who owns Fido, and the one who owns the greyhound.
5. Michelle is neither the one surnamed Peters (who is not Sheba's owner) nor the one who owns the cocker spaniel.
6. Alex is neither the cocker spaniel nor the dog owned by Carole. The dog named Fido isn't the cocker spaniel.
7. The one surnamed Lawton is neither the one who owns Rollie nor the one who owns the German shepherd.
6. Declarative specification
Here is a declarative specification of the problem and encoding of the constraints of the problem in a Datalog program such that, when run, the solution to the problem is obtained.
7. Key decision
A key decision is to use a table of the various logical variables and then encode each hint or rule as a one ore more Prolog constraints on the logical variables.
% 0. first last dog breed (fixed)
% 1. F1 L1 D1 B1 = cocker spaniel
% 2. F2 L2 D2 B2 = Dalmation
% 3. F3 L3 D3 B3 = German sheperd
% 4. F4 L4 D4 B4 = golden retriever
% 5. F5 L5 D5 B5 = greyhound
Do not try to solve the puzzle manually. Instead, encode each rule as clearly as possible as one or more constraints without reference to other rules.
8. Improvements
One exception is that, for computational efficiency, any logical variable what is explicitly given a value should be included in that rule but also copied/moved to early in the constraint sequence.
The following meets this criteria as shown below in the program.
% Put some known values here to speed up computation
F3 = "Carole",
L2 = "Baxter",
But these same constraints are repeated in the rule from which they were taken (and that has negligible impact on machine efficiency).
Here is the Prolog code.
9. Solution
Notice that the puzzle may have more than one solution. There are many solutions listed below.
To verify, check each rule against the solution.
Perhaps one rule was misunderstood, misinterpreted, mis-coded, etc.
10. Output
Here is the output.
Here is the output of the Prolog code.
11. Results and analysis
It turns out that "Prolog" found 16 different solutions to the problem, not just one solution as given in the book from which the problem was taken.
Discussion: If the order of the dog breed names are fixed, then there are
5 different first names,
5 different last names, and
5 different dog names.
For each of the three types of names, there are 5! (5 factorial) permutations, or
5! = 5 * 4 * 3 * 2 * 1 = 120
permutations. Thus, there are
120 * 120 * 120 = 1,728,000
ways of arranging the first, last, and dog names. Note that if the order of the dog breed names were not fixed, there would be 120*1,728,000 arrangements, but for each solution, there would be 120 other solutions that would be equivalent if the order of the rows were rearranged.
Of these 1,728,000 ways, "Prolog" found 16 ways that satisfied all of the logical constraints. Note that "Prolog" does not necessarily generate and test all 1,728,000 ways, since certain constraints can be used to limit the search.
The difficulty of tediousness of solving the puzzle by hand means that one might be tempted to stop at the first solution, even if more solutions exist.
