Solving puzzle using constraints and permutations in Prolog

Question

I have been asked to solve a puzzle similar to the zebra puzzle using Prolog. Instead, I am trying to find the nationality of the individual who eats pie. I know there are differing solutions for the problem, however I am trying to solve the puzzle by using constraints and permutations. However, running the pie_eater predicate returns false and when tracing the code it does not stop running.

The list of constraints goes as follows:

1) the Irish person lives next to the yellow house

2) the person who likes donuts lives next to the person who enjoys embroidery

3) the person who enjoys trainspotting lives next to the one who likes pizza

4) the person who enjoys pachinko likes beets

5) the Czech lives in the purple house

6) the person living in the center house listens to grunge

7) the person who enjoys glassblowing listens to hip hop

8) the American likes tofu

9) the Dutch person listens to J-Pop

10) the pink house's owner listens to country

11) the owner of the green house enjoys embroidery

12) the Irish person lives in the first house

13) the pink house is on the left of the orange house

14) the Japanese person enjoys gardening

15) the person who enjoys trainspotting has a neighbor who listens to jazz

In my code, I have defined a list Street containing 5 houses. I then defined variables for each corresponding adjective for each element of the list to use for my permutation guesses. I translated each constraint into code. To generate the answer, I created permutations for each set of variables for each house. At the bottom, I defined predicates leftof and nextto in order to satisfy a some of the constraints of the problem.

The code goes as follows:

%who eats pie
pie_eater(PieEater) :-
        puzzle(X),
        member(house(PieEater, _, _, _, pie), X).


puzzle(Street) :- 

        Street = [H1, H2, H3, H4, H5], %street of 5 houses

        %vars for permutation
        H1 = house(Nat1, Col1, Mus1, Hob1, Food1),
        H2 = house(Nat2, Col2, Mus2, Hob2, Food2),
        H3 = house(Nat3, Col3, Mus3, Hob3, Food3),
        H4 = house(Nat4, Col4, Mus4, Hob4, Food4),
        H5 = house(Nat5, Col5, Mus5, Hob5, Food5),

        % facts
        nextto(house(irish, _, _, _, _), house(_, yellow, _, _, _), Street), %irish next to yellow house
        nextto(house(_, _, _, _, donuts), house(_, _, _, embroidery, _), Street), %donut next to embrodier lover
        nextto(house(_, _, _, trainspotting, _), house(_, _, _, _, pizza), Street),  %trainspotting next to pizza ouse      
        member(house(_, _, _, pachinko, beets), Street), %pachinko person eats beets
        member(house(czech, purple, _, _, _), Street), %czech person lives in purple house
        [_, _, house(_, _, grunge, _, _), _, _] = Street, %middle house listens to grunge
        member(house(_, _, hiphop, glassblowing, _), Street), %hiphop lover likes glassblowing
        member(house(american, _, _, _, tofu), Street), %american likes tofu
        member(house(dutch, _, jpop, _, _), Street), %dutch person likes jpop
        member(house(_, pink, country, _, _), Street),  %pink house person likes country music
        member(house(_, green, _, embroidery, _), Street), %green house person likes embroidery
        [house(irish, _, _, _, _), _, _, _, _] = Street, %irish person in first house
        leftof(house(_, pink, _, _, _),house(_, orange, _, _, _), Street),  %pink house left of orange house
        member(house(japanese, _, _, gardening, _), Street), %japanese person likes gardening
        member(house(_, _, jazz, trainspotting, _), Street), %trainspotting person likes jazz
        member(house(_, _, _, _, pie), Street), %one person likes pie

        %permutation guesses
        permutation([irish, czech, american, dutch, japanese],[Nat1, Nat2, Nat3, Nat4, Nat5]), %nat permutations
        permutation([yellow, purple, pink, green, orange],[Col1, Col2, Col3, Col4, Col5]), %color permutations
        permutation([grunge, hiphop, jpop, country, jazz],[Mus1, Mus2, Mus3, Mus4, Mus5]), %music permutation
        permutation([trainspotting, pachinko, glassblowing, embroidery, gardening],[Hob1, Hob2, Hob3, Hob4, Hob5]), %hobby permutation
        permutation([donuts, beets, pizza, tofu, pie],[Food1, Food2, Food3, Food4, Food5]). %food permutation

 %defining other predicates to help solve puzzle
 nextto(X, Y, List) :- leftof(X, Y, List). 
 nextto(X, Y, List) :- leftof(Y, X, List).

 %check if left of
 leftof(L, R, [L,R|_]).
 leftof(L, R, [_ | Rest]) :- leftof(L, R, Rest).

Staring at my code for hours, I feel as if it should work however, I still cannot figure out why I cannot generate a correct permutation given that I have defined all of the constraints. At this point I am stuck.

Doing the problem myself, I believe that the Japanese person is the answer.

Answer 1

Constraint 15 was not represented properly. Changing it to

nextto(house(_, _, _, trainspotting, _), house(_, _, jazz, _, _), Street)

allows the code to work.

Answer 2

Here's the code that I've used for this in the past:

?- puzzle(Who), write(Who), nl, fail.

first(H,[H|_]).

on_the_left(X,Y,[X,Y|_]).
on_the_left(X,Y,[_|Hs]) :- on_the_left(X,Y,Hs).

next_to(X,Y,[X,Y|_]).
next_to(X,Y,[Y,X|_]).
next_to(X,Y,[_|Hs]) :- next_to(X,Y,Hs).

middle(X,[_,_,X,_,_]).

puzzle(Who) :-
    Houses = [
            house(Nationality, Colour, Music, Hobby, Food),
            house(_, _, _, _, _),
            house(_, _, _, _, _),
            house(_, _, _, _, _),
            house(_, _, _, _, _)],
    next_to(house(irish, _, _, _, _), house( _, yellow, _, _, _), Houses), % 01) the Irish person lives next to the yellow house
    next_to(house(_, _, _, _, donuts), house( _, _, _, embroidery, _), Houses), % 02) the person who likes donuts lives next to the person who enjoys embroidery
    next_to(house(_, _, _, trainspotting, _), house( _, _, _, _, pizza), Houses), % 03) the person who enjoys trainspotting lives next to the one who likes pizza
    member(house(_, _, _, pachinko, beets), Houses), % 04) the person who enjoys pachinko likes beets
    member(house(czech, purple, _, _, _), Houses), % 05) the Czech lives in the purple house
    middle(house(_, _, grunge, _, _), Houses), % 06) the person living in the center house listens to grunge
    member(house(_, _, hiphop, glassblowing, _), Houses), % 07) the person who enjoys glassblowing listens to hip hop
    member(house(american, _, _, _, tofu), Houses), % 08) the American likes tofu
    member(house(dutch, _, jpop, _, _), Houses), % 09) the Dutch person listens to J-Pop
    member(house(_, pink, country, _, _), Houses), % 10) the pink house's owner listens to country
    member(house(_, green, _, embroidery, _), Houses), % 11) the owner of the green house enjoys embroidery
    first(house(irish, _, _, _, _), Houses), % 12) the Irish person lives in the first house
    on_the_left(house(_, pink, _, _, _), house(_, orange, _, _, _), Houses), % 13) the pink house is on the left of the orange house
    member(house(japanese, _, _, gardening, _), Houses), % 14) the Japanese person enjoys gardening
    next_to(house(_, _, _, trainspotting, _), house( _, _, jazz, _, _), Houses), % 15) the person who enjoys trainspotting has a neighbor who listens to jazz
    member(house(Who, _, _, _, pie), Houses),
        write(Houses), nl.

The outputs:

[house(irish, green, jazz, embroidery, pizza), house(dutch, yellow, jpop, trainspotting, donuts), house(czech, purple, grunge, pachinko, beets), house(japanese, pink, country, gardening, pie), house(american, orange, hiphop, glassblowing, tofu)]
japanese

Answer 3

running your code with debbuger, it looks like this part never succeeded.

    member(house(_, _, jazz, trainspotting, _), Street), 

when calling this, contents of variables are:

 

     H1 = house(irish, green, Mus1, embroidery, pizza)
     H2 = house(dutch, yellow, jpop, trainspotting, donuts)
     H3 = house(czech, purple, grunge, pachinko, beets)
     H4 = house(japanese, pink, country, gardening, Food4)
     H5 = house(american, orange, hiphop, glassblowing, tofu)

does this information help? derpnallday's suggestion may be true( I have no idea why his answer undervoted.)

by the way, I once solved another zebra problem using clpfd.

The following version of the puzzle appeared in Life International in 1962:

There are five houses. The Englishman lives in the red house. The Spaniard owns the dog. Coffee is drunk in the green house. The Ukrainian drinks tea. The green house is immediately to the right of the ivory house. The Old Gold smoker owns snails. Kools are smoked in the yellow house. Milk is drunk in the middle house. The Norwegian lives in the first house. The man who smokes Chesterfields lives in the house next to the man with the fox. Kools are smoked in the house next to the house where the horse is kept. The Lucky Strike smoker drinks orange juice. The Japanese smokes Parliaments. The Norwegian lives next to the blue house. Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

:-use_module(library(clpfd)).

zebra_prob:-

% left ------> right
House=[Color1,Color2,Color3,Color4,Color5],
Pet=[Pet1,Pet2,Pet3,Pet4,Pet5],
Race=[Race1,Race2,Race3,Race4,Race5],
Drink=[Bev1,Bev2,Bev3,Bev4,Bev5],
Smoke=[Cig1,Cig2,Cig3,Cig4,Cig5],

% Race 1:English 2:Spaniard 3:Ukrainian 4:Norwegian 5:Japanese
% HouseColor 1:red 2:green 3:ivory 4:yellow 5:blue
% Pet 1:dog 2:snails 3:fox 4:horse 5:zebra
% Drink 1:coffee 2:tea 3:milk 4:orange juice 5:water
% Smoke 1:Old Gold 2:Kool 3:Chesterfields 4:Lucky Strike 5:Parliaments

all_different(House), %house
all_different(Pet), %pet
all_different(Race), %country
all_different(Drink), %drink
all_different(Smoke), %smoke

House ins 1..5,
Pet ins 1..5,
Race ins 1..5,
Drink ins 1..5,
Smoke ins 1..5,

% The Englishman(1) lives in the red house(1).
Race1 #= 1 #<==> Color1 #= 1,
Race2 #= 1 #<==> Color2 #= 1,
Race3 #= 1 #<==> Color3 #= 1,
Race4 #= 1 #<==> Color4 #= 1,
Race5 #= 1 #<==> Color5 #= 1,

% The Spaniard(2) owns the dog(1).
Race1 #= 2 #<==> Pet1 #= 1,
Race2 #= 2 #<==> Pet2 #= 1,
Race3 #= 2 #<==> Pet3 #= 1,
Race4 #= 2 #<==> Pet4 #= 1,
Race5 #= 2 #<==> Pet5 #= 1,

% Coffee(1) is drunk in the green house(2).
Bev1 #= 1 #<==> Color1 #= 2,
Bev2 #= 1 #<==> Color2 #= 2,
Bev3 #= 1 #<==> Color3 #= 2,
Bev4 #= 1 #<==> Color4 #= 2,
Bev5 #= 1 #<==> Color5 #= 2,

% The Ukrainian(3) drinks tea(2).
Race1 #= 3 #<==> Bev1 #= 2,
Race2 #= 3 #<==> Bev2 #= 2,
Race3 #= 3 #<==> Bev3 #= 2,
Race4 #= 3 #<==> Bev4 #= 2,
Race5 #= 3 #<==> Bev5 #= 2,

% The green house(2) is immediately to the right of the ivory house(3).
Color1 #= 3 #<==> Color2 #= 2 ,
Color2 #= 3 #<==> Color3 #= 2 ,
Color3 #= 3 #<==> Color4 #= 2 ,
Color4 #= 3 #<==> Color5 #= 2 ,

% So, green house(2) is not leftmost.
Color1 #\= 2,

% The Old Gold(1) smoker owns snails(2).
Cig1 #= 1 #<==> Pet1 #= 2,
Cig2 #= 1 #<==> Pet2 #= 2,
Cig3 #= 1 #<==> Pet3 #= 2,
Cig4 #= 1 #<==> Pet4 #= 2,
Cig5 #= 1 #<==> Pet5 #= 2,

% Kools(2) are smoked in the yellow(4) house.
Cig1 #= 2 #<==> Color1 #= 4,
Cig2 #= 2 #<==> Color2 #= 4,
Cig3 #= 2 #<==> Color3 #= 4,
Cig4 #= 2 #<==> Color4 #= 4,
Cig5 #= 2 #<==> Color5 #= 4,

% Milk(3) is drunk in the middle house.
Bev3 #= 3,

% The Norwegian(4) lives in the first house. (I assume that "first" means leftmost)
Race1 #= 4,

% The man who smokes Chesterfields(3) lives in the house next to the man with the fox(3).
(Cig1 #= 3 #/\ Pet2 #= 3) #\/
(Cig2 #= 3 #/\ Pet3 #= 3) #\/
(Cig3 #= 3 #/\ Pet4 #= 3) #\/
(Cig4 #= 3 #/\ Pet5 #= 3) #\/
(Pet1 #= 3 #/\ Cig2 #= 3) #\/
(Pet2 #= 3 #/\ Cig3 #= 3) #\/
(Pet3 #= 3 #/\ Cig4 #= 3) #\/
(Pet4 #= 3 #/\ Cig5 #= 3) ,

% Kools(2) are smoked in the house next to the house where the horse(4) is kept.
(Cig1 #= 2 #/\ Pet2 #= 4) #\/
(Cig2 #= 2 #/\ Pet3 #= 4) #\/
(Cig3 #= 2 #/\ Pet4 #= 4) #\/
(Cig4 #= 2 #/\ Pet5 #= 4) #\/
(Pet1 #= 4 #/\ Cig2 #= 2) #\/
(Pet2 #= 4 #/\ Cig3 #= 2) #\/
(Pet3 #= 4 #/\ Cig4 #= 2) #\/
(Pet4 #= 4 #/\ Cig5 #= 2) ,

% The Lucky Strike(4) smoker drinks orange juice(4).
Cig1 #= 4 #<==> Bev1 #= 4,
Cig2 #= 4 #<==> Bev2 #= 4,
Cig3 #= 4 #<==> Bev3 #= 4,
Cig4 #= 4 #<==> Bev4 #= 4,
Cig5 #= 4 #<==> Bev5 #= 4,

% The Japanese(5) smokes Parliaments(5).
Race1 #= 5 #<==> Cig1 #= 5,
Race2 #= 5 #<==> Cig2 #= 5,
Race3 #= 5 #<==> Cig3 #= 5,
Race4 #= 5 #<==> Cig4 #= 5,
Race5 #= 5 #<==> Cig5 #= 5,

% The Norwegian(4) lives next to the blue house(5).
(Race1 #= 4 #/\ Color2 #= 5) #\/
(Race2 #= 4 #/\ Color3 #= 5) #\/
(Race3 #= 4 #/\ Color4 #= 5) #\/
(Race4 #= 4 #/\ Color5 #= 5) #\/
(Color1 #= 5 #/\ Race2 #= 4) #\/
(Color2 #= 5 #/\ Race3 #= 4) #\/
(Color3 #= 5 #/\ Race4 #= 4) #\/
(Color4 #= 5 #/\ Race5 #= 4) ,

label(House),
label(Pet),
label(Race),
label(Smoke),
label(Drink),

write('house:'),write(House),nl,
write('pet:'),write(Pet),nl,
write('race:'),write(Race),nl,
write('drink:'),write(Drink),nl,
write('smoke:'),write(Smoke),nl,nl.
　

[3] 23 ?- zebra_prob.
house:[4,5,1,3,2]
pet:[3,4,2,1,5]
race:[4,3,1,2,5]
drink:[5,2,3,4,1]
smoke:[2,3,1,4,5]

true ;
false.



% Race  1:English 2:Spaniard 3:Ukrainian 4:Norwegian 5:Japanese
% HouseColor 1:red 2:green 3:ivory 4:yellow 5:blue
% Pet 1:dog 2:snails 3:fox 4:horse 5:zebra
% Drink 1:coffee 2:tea 3:milk 4:orange juice 5:water
% Smoke 1:Old Gold 2:Kool 3:Chesterfields 4:Lucky Strike 5:Parliaments

Now, who drinks water? Who owns the zebra?
5:water is drunk by 4:Norwegian
5:zebra is tamed by 5:Japanese