title: Solving puzzle using constraints and permutations in Prolog
body: <p>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.</p>
  
  <p>The list of constraints goes as follows:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>In my code, I have defined a list <strong>Street</strong> 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 <strong>leftof</strong> and <strong>nextto</strong> in order to satisfy a some of the constraints of the problem.</p>
  
  <p>The code goes as follows:</p>
  
  <pre><code>%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).
  </code></pre>
  
  <p>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.</p>
  
  <p>Doing the problem myself, I believe that the Japanese person is the answer.</p>