Solving Einstein Riddle in Prolog

Question

I am trying to solve Einstein Riddle in Prolog.

I am having a difficulty with the program I wrote, the basic method was to add all constraints and let Prolog figure out the only possible solutions.

The problem is that Prolog finds 0 solutions. I have isolated the constraint that makes the program go from a given solution to no solutions, but I don't understand why.

/*There are five houses*/
exists(A, list(A,_,_,_,_)).
exists(A, list(_,A,_,_,_)).
exists(A, list(_,_,A,_,_)).
exists(A, list(_,_,_,A,_)).
exists(A, list(_,_,_,_,A)).

middle_house(A, list(_,_,A,_,_)).

first_house(A, list(A,_,_,_,_)).

nextTo(A, B, list(B,A,_,_,_)).
nextTo(A, B, list(_,B,A,_,_)).
nextTo(A, B, list(_,_,B,A,_)).
nextTo(A, B, list(_,_,_,B,A)).
nextTo(A, B, list(A,B,_,_,_)).
nextTo(A, B, list(_,A,B,_,_)).
nextTo(A, B, list(_,_,A,B,_)).
nextTo(A, B, list(_,_,_,A,B)).

/* each statement will be described using the clues 
house conatins: Color,Owner, Drinks, Smokes, Pet*/
riddle(Houses):-
    /*exists(house(red, englishman, _,_,_),Houses),*/
    nextTo(house(_,norwegian,_,_,_), house(blue,_,_,_,_), Houses),
    exists(house(_,spanish,_,_, dog), Houses),
    exists(house(green, _, coffee, _,_), Houses),
    exists(house(_, ukrain, tea,_,_), Houses),
    nextTo(house(white,_,_,_,_), house(green,_,_,_,_), Houses),
    exists(house(_,_,_,marlbero, cat),Houses),
    exists(house(yellow,_,_,time,_), Houses),
    middle_house(house(_,_,milk,_,_), Houses),
    first_house(house(_,norwegian,_,_,_), Houses),
    nextTo(house(_,_,_,_,fox), house(_,_,_,montena,_), Houses),
    nextTo(house(_,_,_,time,_), house(_,_,_,_,horse), Houses),
        exists(house(_,_,orange,lucky,_), Houses),
    exists(house(_,japanese,parlament,_), Houses).

The current solution to this is this:

?- riddle(Houses).
Houses = list( house(green, norwegian, coffee, marlbero, cat),
               house(white, spanish, orange, lucky, dog),
               house(yellow, norwegian, milk, time, fox),
               house(blue, ukrain, tea, montena, horse),
               house(_G7257, japanese, parlament, _G7260)).

and if I uncomment the first line then that same statement returns false.

I would like help understanding why this is the case. I noted that in the partial solution the Norwegian appears twice and that this might indicate the problem.

Also, nextTo(house(white,_,_,_,_), house(green,_,_,_,_), Houses) isn't restrictive enough. According to the original puzzle, the green house is right of the white house, not just next to. — lurker
This line (the last line in your riddle/1 predicate) is missing one house argument: exists(house(_,japanese,parlament,_), Houses). It should be exists(house(_,japanese,_,parlament,_), Houses). — lurker

false false · Accepted Answer · 2017-08-22T19:48:34

Here is a general way how you can solve this problem for yourself. Actually, you really started in a quite promising direction: You tried to remove goals. But then, who was at fault in your case? The line you commented out or the rest? You cannot say that for sure, since the resulting program already worked. But there is a very similar and much more promising way: Try to generalize your program as much as possible such that it still fails. In this manner, you will obtain a smaller program that is responsible for the failure. That is, within the remaining visible part has to be an error!

Here is what I got by removing goals (adding a * in front) and by replacing some terms by _.

:- initialization(riddle(_Sol)).
:- op(950, fy, *).
*_.

riddle(Houses):-
    exists(house(red, _/* englishman */, _,_,_),Houses),
    nextTo(house(_,_/* norwegian */,_,_,_), house(blue,_,_,_,_), Houses),
    * exists(house(_,spanish,_,_, dog), Houses),
    * exists(house(green, _, coffee, _,_), Houses),
    * exists(house(_, ukrain, tea,_,_), Houses),
    nextTo(house(white,_,_,_,_), house(green,_,_,_,_), Houses),
    * exists(house(_,_,_,marlbero, cat),Houses),
    exists(house(yellow,_,_,_/* time */,_), Houses),
    * middle_house(house(_,_,milk,_,_), Houses),
    * first_house(house(_,norwegian,_,_,_), Houses),
    * nextTo(house(_,_,_,_,fox), house(_,_,_,montena,_), Houses),
    * nextTo(house(_,_,_,time,_), house(_,_,_,_,horse), Houses),
    * exists(house(_,_,orange,lucky,_), Houses),
    exists(house(_,_/* japanese */,_/* parlament */,_), Houses).

This fragment still fails, thus the error has to be in the visible part of the program.

It seems to be essential that all the house colors are present. There is only one goal that does not contain any house color at all... see it?

Solving Einstein Riddle in Prolog

1 Answers