Zebra puzzle in Prolog

Question

I have attempted to a zebra puzzle in prolog and I was seeking some feedback as to the way I went about solving the puzzle.

Here is the puzzle:

Two weeks ago, four enthusiasts made sightings of objects in the sky in their neighborhood. Each of the four reported his or her sightings on a different day. The FBI came and was able to give each person a different explanation of what he or she had "really" seen. Can you determine the day (Tuesday through Friday) each person sighted the object, as well as the object that it turned out to be?

• Mr. K made his sighting at some point earlier in the week than the one who saw the balloon, but at some point later in the week, than the one who spotted the Kite (who isn't Ms. G).
• Friday's sighting was made by either Ms. Barn or the one who saw a plane (or both).
• Mr. Nik did not make his sighting on Tuesday.
• Mr. K isn't the one whose object turned out to be a telephone pole.

Here is a representation of how I found the solution to the problem:

I know K didn't spot the balloon (1) or the kite (2) or the telephone pole (6), so K spotted the plane. Also, K's day can't be Friday (1), so Friday was B's day (4).

I also know the kite wasn't spotted by K (2) or G (3). Nor was it spotted by B, since B's day was Friday and the kite can't have been spotted on Friday (2). So N spotted the kite. Also, we know kite day is two days before balloon day (1,2), so kite day must have been Tuesday or Wednesday; but N's day wasn't Tuesday (5), so kite day was Wednesday, which means K's day was Thursday (2) and balloon day was Friday (1).

And the rest I got by elimination. Summing up:

G spotted a telephone pole on Tuesday.
N spotted a kite on Wednesday.
K spotted a plane on Thursday.
B spotted a balloon on Friday.

And here is my prolog code:

before(X,Y,Ds) :-
    remainder(X,Ds,Rs),
    member(Y,Rs).

remainder(X,[X|Ds],Ds).
remainder(X,[_|Ds],Rs) :- remainder(X,Ds,Rs).

members([],_).
members([X|Xs],Ds) :-
member(X,Ds),
members(Xs,Ds).

puzzle :-
Days = [[tuesday,_,_],[wednesday,_,_],[thursday,_,_],[friday,_,_]],
before([_,mr_klien,_],[_,_,balloon],Days),
before([_,_,frisbee],[_,mr_klien,_],Days),
(member([friday,ms_barnum,_],Days);
    member([friday,_,clothesline],Days);
    member([friday,ms_barnum,clothesline],Days)),
members([[_,mr_klien,_],[_,ms_barnum,_],[_,ms_green,_],[_,mr_niven,_]],Days),
members([[_,_,balloon],[_,_,frisbee],[_,_,clothesline], [_,_,water_tower]],Days),
member([_,NOT_ms_green,frisbee],Days), NOT_ms_green \= ms_green,
member([tuesday,NOT_mr_niven,_],Days), NOT_mr_niven \= mr_niven,
member([_,NOT_mr_klien,water_tower],Days), NOT_mr_klien \= mr_klien,
write(Days),
nl,
fail.

Answer 1

This is quite nice, but there are still several ways that would improve this.

Here are a few ideas:

Relations instead of side-effects

First, I recommend to avoid side-effects. Instead, think in terms of relations. By this I mean that you should not use write/1 to print a solution, but express what constitutes a solution, as in the following:

solution(Days) :-
        Days = [[tuesday,_,_],[wednesday,_,_],[thursday,_,_],[friday,_,_]],
        etc.

Here, I have made Days available for reasoning as a predicate argument. This way, you can explicitly reason about solutions, and for example write actual test cases by stating what should and should not hold about given solutions. You cannot do this if the solution only occurs in the form of output on the system terminal.

If you need to print a solution in any way, you can use the more general form above to still do that. For example:

?- solution(Ds),
   maplist(writeln, Ds).
[tuesday,ms_green,water_tower]
[wednesday,mr_niven,frisbee]
[thursday,mr_klien,clothesline]
[friday,ms_barnum,balloon]

Use higher-order predicates

Suppose I give you the following auxiliary predicate:

list_member(Ls, E) :- member(E, Ls).

Then you can use maplist/2 to express members/2 as follows:

members(Es, Ls) :- maplist(list_member(Ls), Es).

When you encounter predicates that reason over lists, check the available higher-order predicates (especially maplist/N and foldl/N) to see if they can simplify your code.

Use dif/2 instead of (\=)/2

You are currently using the impure predicate (\=)/2 in your code. This prevents you from using Prolog to its fullest potential.

Use dif/2 instead to benefit from the declarative nature of true relations: You can then pull these goals towards the beginning of the clause or at least earlier, and benefit from their pruning in addition to the added flexibility of placing the goal anywhere you like in principle.

Indentation

Never put (;)/2 at the end of a line. It looks too similar to (',')/2, which typically occurs at that position.

In total, a solution could look like (in addition to the points mentioned previously):

solution(Days) :-
        Days = [[tuesday,_,_],[wednesday,_,_],[thursday,_,_],[friday,_,_]],
        before([_,mr_klien,_],[_,_,balloon],Days),
        before([_,_,frisbee],[_,mr_klien,_],Days),
        (   member([friday,ms_barnum,_],Days)
        ;   member([friday,_,clothesline],Days)
        ;   member([friday,ms_barnum,clothesline],Days)
        ),
        members([[_,mr_klien,_],[_,ms_barnum,_],[_,ms_green,_],[_,mr_niven,_]], Days),
        members([[_,_,balloon],[_,_,frisbee],[_,_,clothesline],[_,_,water_tower]], Days),
        dif(NOT_ms_green, ms_green),
        member([_,NOT_ms_green,frisbee],Days),
        dif(NOT_mr_niven, mr_niven),
        member([tuesday,NOT_mr_niven,_],Days),
        dif(NOT_mr_klien, mr_klien),
        member([_,NOT_mr_klien,water_tower],Days).

Now we can query:

?- solution(Ds).
Ds = [[tuesday, ms_green, water_tower], [wednesday, mr_niven, frisbee], [thursday, mr_klien, clothesline], [friday, ms_barnum, balloon]] ;
false.

And also ask something different, for example:

?- Ds = [[monday, ms_green|_]|_],
   solution(Ds).
false.

Thus, the system tells us: No, that's not a solution!

This is now easily possible because we can reason explicitly about solutions, having made them available as a predicate argument.

Answer 2

On top of what mat mentioned, here are some general programming suggestions which also apply here:

Give names to data-structures.

You are using a list of lists to represent the solution. That's OK, but not every list of lists is of the shape of your solution. Also, dealing with low-level representation of the data-structure makes you write a lot of unnecessary code (you are forced to write _ many times, and it makes it harder to extract valuable information from the source code).

Give names to helper functions.

This makes it easier for humans to understand what your predicate is about. Once it is entirely made of member(X, L), it is hard to recognize common programming patterns s.a. filtering, searching, permuting etc. Once you are able to organize low-level predicates into groups and name those groups, you have made it easier for the reader to understand your intention.

Exploit nondeterminism.

Prolog has a relatively unusual feature--it allows nondeterminism in your code. It is a very powerful tool. Consider before(X, Y) as a good candidate for nondeterminism since it is true of X=wednesday, Y=thursday and X=wednesday, Y=friday.

---

Below is an example which tries to illustrate the ideas mentioned above:

days([tuesday, wednesday, thursday, friday]).

before(X, Y) :-
    days(Days),
    append([_, [X], After], Days),
    member(Y, After).

permute([], []).
permute([X | Xs], Ys) :-
    permute(Xs, Zs),
    select(X, Ys, Zs).

event_of([(Day, Event) | _], Event, Day) :- !.
event_of([(OtherDay, _) | Mappings], Event, Day) :-
    dif(Day, OtherDay),
    event_of(Mappings, Event, Day).

puzzle([
    spotted(mr_klien, KlienEvent, KlienDay),
    spotted(ms_green, GreenEvent, GreenDay),
    spotted(mr_niven, NivenEvent, NivenDay),
    spotted(ms_barnum, BarnumEvent, BarnumDay)]) :-
    days(Days),
    permute(Days, [KlienDay, GreenDay, NivenDay, BarnumDay]),
    permute(Days, [BaloonDay, KiteDay, PlaneDay, PhoneDay]),
    before(KlienDay, BaloonDay),
    before(KiteDay, KlienDay),
    dif(GreenDay, KiteDay),
    ( BarnumDay = friday ; PlaneDay = friday ),
    dif(NivenDay, tuesday),
    dif(PhoneDay, KlienDay),
    EventMapping = [
        (BaloonDay, baloon),
        (KiteDay, kite),
        (PlaneDay, plane),
        (PhoneDay, phone)
    ],
    maplist(event_of(EventMapping),
            [KlienEvent, GreenEvent, NivenEvent, BarnumEvent],
            [KlienDay, GreenDay, NivenDay, BarnumDay]).