Example: The Zebra Puzzle

We now provide a simplified form of the Zebra Puzzle (Figure 4.2), a common puzzle for constraint resolution. This puzzle was solved by Aït-Kaci (1984) using roughly the same methods as we use here. The puzzle illustrates the expressive power of the combination of extensional types, inequations and type constraints. Such puzzles, sometimes known as logic puzles or constraint puzzles, require one to find a state of affairs within some situation that simultaneously satisfies a set of constraints. The situation itself very often implicitly levies certain constraints.

Figure 4.2: The Zebra Puzzle.

We can represent the simplified Zebra Puzzle in ALE as:

  % Subsumption
  %=======================
  
  bot sub [house,descriptor,background].
  
    descriptor sub [nat_type,ani_type,bev_type].
      nat_type sub [norwegian,ukranian,spaniard].
        norwegian sub [].
        ukranian sub [].
        spaniard sub [].
      ani_type sub [fox,dog,zebra].
        fox sub [].
        dog sub [].
        zebra sub [].
      bev_type sub [juice,tea,milk].
        juice sub [].
        tea sub [].
        milk sub [].
  
    house sub []
        intro [nationality:nat_type,animal:ani_type,beverage:bev_type].
  
    background sub [clue]
               intro [house1:house,house2:house,house3:house].
      clue sub [maximality].
        maximality sub [].
  
  ext([norwegian,ukranian,spaniard,fox,dog,zebra,juice,tea,milk]).
  
  % Constraints
  %=============================
  background cons
    (house1:nationality:N1,                          % inequational constraints
     house2:nationality:(N2,(=\= N1)),
     house3:nationality:((=\= N1),(=\= N2)),
  
     house1:animal:A1,
     house2:animal:(A2,(=\= A1)),
     house3:animal:((=\= A1),(=\= A2)),
  
     house1:beverage:B1,
     house2:beverage:(B2,(=\= B1)),
     house3:beverage:((=\= B1),(=\= B2))).
  
  clue cons
    (house3:beverage:milk,                             % clue 1
  
     (house1:nationality:spaniard,house1:animal:dog    % clue 2
     ;house2:nationality:spaniard,house2:animal:dog
     ;house3:nationality:spaniard,house3:animal:dog),
  
     (house1:nationality:ukranian,house1:beverage:tea  % clue 3
     ;house2:nationality:ukranian,house2:beverage:tea
     ;house3:nationality:ukranian,house3:beverage:tea),
  
     house1:nationality:norwegian,                     % clue 4
  
     (house1:nationality:norwegian,house2:beverage:tea % clue 5
     ;house2:nationality:norwegian,house3:beverage:tea
     ;house2:nationality:norwegian,house1:beverage:tea
     ;house3:nationality:norwegian,house2:beverage:tea),

     (house1:beverage:juice,house1:animal:fox          % clue 6
     ;house2:beverage:juice,house2:animal:fox
     ;house3:beverage:juice,house3:animal:fox)).
  
  
  maximality cons
    (house1:nationality:(norwegian;ukranian;spaniard), % maximality constraints
     house2:nationality:(norwegian;ukranian;spaniard),
     house3:nationality:(norwegian;ukranian;spaniard),
  
     house1:animal:(fox;dog;zebra),
     house2:animal:(fox;dog;zebra),
     house3:animal:(fox;dog;zebra),
  
     house1:beverage:(juice;tea;milk),
     house2:beverage:(juice;tea;milk),
     house3:beverage:(juice;tea;milk)).

The subsumption hierarchy is shown pictorially in Figure 4.3. The type, background, with the assistance of the types subsumed by house and descriptor, represents the situation of three houses (the features of background), each of which has three attributes (the features of house). The implicit constraints levied by the situation appear as constraints on the type, background, namely that no two houses can have the same value for any attribute. These are represented by inequations. But notice that, since we are interested in treating the values of attributes as tokens, we must represent those values by extensional types. If we had not done this, then we could still, for example, have two different houses with the beverage, juice, since there could be two different feature structures of type juice that were not token-identical. Notice also that all of these types are maximal, and hence satisfy the restriction that ALE places on extensional types.

The explicit constraints provided by the clues to the puzzle are represented as constraints on the type clue, a subtype of background. We also need a subtype of clue, maximality, to enforce another constraint implicit to all constraint puzzles, namely the one which requires that we provide only maximally specific answers, rather than vague solutions which say, for example, that the beverage for the third house is a type of beverage (bev_type), which may actually still satisfy a puzzle's constraints.

To solve the puzzle, we simply type:

| ?- mgsat maximality.

MOST GENERAL SATISFIER OF: maximality

maximality
HOUSE1 house
       ANIMAL fox
       BEVERAGE juice
       NATIONALITY norwegian
HOUSE2 house
       ANIMAL zebra
       BEVERAGE tea
       NATIONALITY ukranian
HOUSE3 house
       ANIMAL dog
       BEVERAGE milk
       NATIONALITY spaniard


ANOTHER?  y.

no
| ?-

So the Ukranian owns the zebra, and the Norwegian drinks juice. A most general satisfier of maximality will also satisfy the constraints of its supertypes, background and clue.

Figure 4.3: Inheritance Network for the Zebra Puzzle.

Although ALE is capable of representing such puzzles and solving them, it is not actually very good at solving them efficiently. To solve such puzzles efficiently, a system must determine an optimal order in which to satisfy all of the various constraints. ALE does not do this since it can express definite clauses in its constraints, and the reordering would also be very difficult for the user to keep track of while designing a grammar. A system that does do this is the general constraint resolver proposed by Penn and Carpenter (1993)^4.16.