ECLiPSeWiki | Examples / ZebraPuzzles

Solving Zebra (or Einstein) Puzzles

Author: Joachim Schimpf, April 2024, under Creative Commons Attribution-ShareAlike 4.0 International License

The Puzzles

A puzzle of the Zebra (or Einstein) type typically involves a number of items that fall into multiple categories and have a number of properties. The puzzle presents a set of clues, and the objective is to determine the correct arrangement of the items and their properties.

The problem is explained and further discussed in the following places

In the following, we develop a number of alternative solutions in ECLiPSe (some require at least version 7.0).

Prolog-style backtrack search

Prolog-style backtrack search

The following is a straightforward Prolog backtracking solution:

:- lib(listut). % for perm/2 list permutation

go :-

        Farm = [
            ['Adam', AdamDay, AdamTime, AdamChore],
            ['Carl', CarlDay, CarlTime, CarlChore],
            ['Fran', FranDay, FranTime, FranChore],  
            ['Nan ', NanDay , NanTime , NanChore ],
            ['Mike', MikeDay, MikeTime, MikeChore]
        ],
        Days = [AdamDay,CarlDay,FranDay,NanDay,MikeDay],
        [Mon,Tue,Wed,Thu,Fri] = [1,2,3,4,5],
        perm(Days, [Mon,Tue,Wed,Thu,Fri]),

        Chores = [AdamChore,CarlChore,FranChore,NanChore,MikeChore],
        perm(Chores, [milk,market,corn,fences,eggs]),

        Times = [AdamTime,CarlTime,FranTime,NanTime,MikeTime],
        perm(Times, [5,6,7,8,9]),

    % 1. Fran's day to mend fences is neither Tuesday nor Thursday, and is
    % completed earlier in the week than at least one other person.
        member(['Fran',FranDay,_,fences],Farm),
        FranDay \= Tue, FranDay \= Thu, FranDay < Fri,

    % 2. The one who goes to market goes later in the week than Carl, and
    % earlier in the morning than Nan, but later in the morning than Fran.
        member(['Mike',MikeDay,MikeTime,market],Farm), % Mike is the one in clu>
        MikeDay > CarlDay, MikeTime < NanTime, MikeTime > FranTime,

    % 3. Adam does not plant the corn, or go to market, his chore is completed
    % before 9:00 am, but not before 6:00 am on his assigned day of Monday.
        AdamChore \= corn, AdamChore \= market,
        AdamTime < 9, AdamTime >= 6, AdamDay = Mon,

    % 4. No one performs a chore on Thursday at 7:00 am.
        member([_,Thu,ThuTime,_],Farm), ThuTime \= 7,

    % 5. Mike's chore is completed earlier in the day than at least 3 others,
    % but later in the week than at least three others.
        MikeTime < 7, MikeDay > Wed,

    % 6. One of the boys collects eggs, another boy milks Bessie, the goat.
        member([_,EggsDay,EggsTime,eggs],Farm),
        member([_,MilkDay,_,milk],Farm),

    % 7. The milk is collected earlier in the week than the girl who plants
    % the corn, which is not planted before Wednesday.
        member(['Nan ',CornDay,_,corn],Farm), % Nan is the girl, Fran mends fen>
        MilkDay < CornDay, CornDay > Tue,

    % 8. The eggs must be collected at 7:00 am, but never on Mondays or Fridays.
        EggsTime = 7, EggsDay \= Mon, EggsDay \= Fri,

    % 9. All the other chores must be complete before Mike goes to the market.
        MikeChore = market, MikeDay = Fri, nl,
        (foreach(Sibling,Farm) do writeln(Sibling)).

Here, nondeterministic choices are made by lists:member/2, and the pair condition is tested using standard functional arithmetic.

This finds the solution easily:

    ?- go.
    [Adam, 1, 8, milk]
    [Carl, 2, 7, eggs]
    [Fran, 3, 5, fences]
    [Nan , 4, 9, corn]
    [Mike, 5, 6, market]
    Yes (0.00s cpu, solution 1, maybe more) ;
    No (0.45s cpu)

However, it takes 0.45s to verify that there is no further solution!