Who Owns The Zebra?
June 16, 2009
We previously used John McCarthy’s amb operator to solve a logic problem, but as logic problems become more complicated, they are best solved using a logic programming language such as Prolog. There are several embeddings of Prolog in Scheme; the best-known is Kanren, as described in the book The Reasoned Schemer by Daniel P. Friedman, Welliam E. Byrd and Oleg Kiselyov. Our solution follows that of Nils Holm in his book Logic Programming in Scheme.
Logic programming languages have a vocabulary different than imperative or functional languages. In place of functions, logic programming languages offer relations. Logic programming languages have goals (sometimes called objectives) that either succeed or fail. Rather than evaluating expressions, computation in logic programming languages proceeds by unification, in which the variables of two expressions are bound in a consistent manner.
Here is Holm’s solution to the zebra puzzle:
(all (== h (list (list 'norwegian (_) (_) (_) (_)) ; 10
(list (_) (_) 'milk (_) (_)) ; 9
(memo (list 'englishman (_) (_) (_) 'red) h) ; 2
(lefto (list (_) (_) (_) (_) 'green) ; 6
(list (_) (_) (_) (_) 'ivory) h) ; 6
(nexto (list 'norwegian (_) (_) (_) (_)) ; 15
(list (_) (_) (_) (_) 'blue) h) ; 15
(memo (list (_) 'kools (_) (_) 'yellow) h) ; 8
(memo (list 'spaniard (_) (_) 'dog (_)) h) ; 3
(memo (list (_) (_) 'coffee (_) 'green) h) ; 4
(memo (list 'ukrainian (_) 'tea (_) (_)) h) ; 5
(memo (list (_) 'luckystrikes 'orangejuice (_) (_)) h) ; 13
(memo (list 'japanese 'parliaments (_) (_) (_)) h) ; 14
(memo (list (_) 'oldgolds (_) 'snails (_)) h) ; 7
(nexto (list (_) (_) (_) 'horse (_)) ; 12
(list (_) 'kools (_) (_) (_)) h) ; 12
(nexto (list (_) (_) (_) 'fox (_)) ; 11
(list (_) 'chesterfields (_) (_) (_)) h) ; 11
(memo (list (_) (_) 'water (_) (_)) h)
(memo (list (_) (_) (_) 'zebra (_)) h)))))
There are four goals:
== performs unification,
memo tests whether a list contains a particular element,
lefto checks if one element is immediately to the left of another in a list, and
nexto checks if one element is immediately adjacent to another in a list (by convention, goals are spelled with names that end in the letter o).
All is an operator that succeeds only if all its sub-goals succeed.
Run* is the interface between normal Scheme and the logic extensions;
(run* (h) ...) displays the unification of
h, which is not a Scheme variable but a logic variable.
Fresh creates a new logical environment and defines
h as a logic variable, in a manner similar to the
let syntax of normal Scheme.
memo goals are part of the standard system, but
nexto are specific to the zebra puzzle:
(define (lefto x y l)
(any (all (caro l x)
(cdro l d)
(caro d y))
(all (cdro l d)
(lefto x y d)))))
(define (nexto x y l)
(any (lefto x y l)
(lefto y x l)))
Thus, the body of
zebra is an
all operator that succeeds when all of its sub-objectives succeed. The first objective unifies the logic variable
h with a list of houses, each represented as a five-element list of nationality, cigarette, drink, pet, and house color. Each fact of the puzzle is encoded as a goal; for instance, the second goal constrains the englishman to live in the red house, and the third goal constrains the ivory house to be to the left of the green house. The last two goals mention water and the zebra, because they do not appear in any of the other goals.
The solution takes less than a second:
((norwegian kools water fox yellow)
(ukrainian chesterfields tea horse blue)
(englishman oldgolds milk snails red)
(japanese parliaments coffee zebra green)
(spaniard luckystrikes orangejuice dog ivory))
The norwegian drinks water. The japanese owns the zebra.
The complete code, including the logic primitives, is given at http://programmingpraxis.codepad.org/408Ehwhb (you should be aware that it uses a later version of the logic primitives than the book). Wikipedia provides more information about the zebra puzzle, including a complete solution by deduction, without a computer.
Pages: 1 2