Databases
StackOverflow2013
Postsdbo
POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
    primarykey
    data
    text
    <p>I have been given an exercise to solve the zebra puzzle using a constraint solver of my choice, and I tried it using the <a href="http://www.swi-prolog.org/man/clpfd.html" rel="nofollow">Prolog clpfd library</a>.</p> <p><strong>I am aware that there are other more idiomatic ways to solve this problem in Prolog, but this question is specifically about the <code>clpfd</code> package!</strong></p> <p>So the specific variation of the puzzle (given that there are many of them) I'm trying to solve is this one:</p> <p><strong>There are five houses</strong></p> <ol> <li>The Englishman lives in the red house</li> <li>The Swedish own a dog</li> <li>The Danish likes to drink tea</li> <li>The green house is left to the white house</li> <li>The owner of the green house drinks coffee</li> <li>The person that smokes Pall Mall owns a bird</li> <li>Milk is drunk in the middle house</li> <li>The owner of the yellow house smokes Dunhill</li> <li>The norwegian lives in the first house</li> <li>The marlboro smoker lives next to the cat owner</li> <li>The horse owner lives next to the person who smokes dunhill</li> <li>The winfield smoker likes to drink beer</li> <li>The norwegian lives next to the blue house</li> <li>The german smokes rothmanns</li> <li>The marlboro smoker has a neighbor who drinks water</li> </ol> <p>I tried to solve it with the following approach:</p> <blockquote> <p>Each attribute a house can have is modeled as a variable, e.g. "British", "Dog", "Green", etc. The attributes can take values from 1 to 5, depending on the house in which they occur, e.g. if the variable "Dog" takes the value 3, the dog lives in the third house. </p> </blockquote> <p>This approach makes it easy to model neighbor constraints like this:</p> <pre><code>def neighbor(X, Y) :- (X #= Y-1) #\/ (X #= Y+1). </code></pre> <p>But somehow, the <code>clpfd</code> package does not yield a solution, even though (IMO) the problem is modeled correctly (I used the exact same model with the <a href="http://www.emn.fr/z-info/choco-solver/" rel="nofollow">Choco constraint solver</a> and the result was correct).</p> <p>Here is the complete code:</p> <pre><code>:- use_module(library(clpfd)). neighbor(X, Y) :- (X #= (Y - 1)) #\/ (X #= (Y + 1)). solve([British, Swedish, Danish, Norwegian, German], Fish) :- Nationalities = [British, Swedish, Danish, Norwegian, German], Colors = [Red, Green, Blue, White, Yellow], Beverages = [Tea, Coffee, Milk, Beer, Water], Cigarettes = [PallMall, Marlboro, Dunhill, Winfield, Rothmanns], Pets = [Dog, Bird, Cat, Horse, Fish], all_different(Nationalities), all_different(Colors), all_different(Beverages), all_different(Cigarettes), all_different(Pets), Nationalities ins 1..5, Colors ins 1..5, Beverages ins 1..5, Cigarettes ins 1..5, Pets ins 1..5, British #= Red, % Hint 1 Swedish #= Dog, % Hint 2 Danish #= Tea, % Hint 3 Green #= White - 1 , % Hint 4 Green #= Coffee, % Hint 5, PallMall #= Bird, % Hint 6 Milk #= 3, % Hint 7 Yellow #= Dunhill, % Hint 8, Norwegian #= 1, % Hint 9 neighbor(Marlboro, Cat), % Hint 10 neighbor(Horse, Dunhill), % Hint 11 Winfield #= Beer, % Hint 12 neighbor(Norwegian, Blue), % Hint 13 German #= Rothmanns, % Hint 14, neighbor(Marlboro, Water). % Hint 15 </code></pre> <p>Did I misunderstand a concept within <code>clpfd</code>, or am I simply missing something obvious here? In case it helps, <a href="https://github.com/githubnemo/ISP/blob/master/P4/scala/main.scala" rel="nofollow">here</a> you can find the same approach implemented using Choco and Scala.</p> <hr> <p><strong>Edit:</strong> The reason why I believe that the solver isn't able to solve the problem ist that it never comes up with definite values for the variables, but only with ranges, e.g. "Fish 1..3\/5".</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USfalse
    1. USfresskoma
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. This table or related slice is empty.
      1. VTUpMod
    1. COUse label(Vars) or labeling(Options, Vars) tro solve the problem.
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. USjoel76
    2. CO"label" only works if there is a definite result, whereas what I am getting for every variable are only ranges (as explained in the edit).
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. USfresskoma
    3. COIf your CLP(FD) would have "Expr in Set", then one could formalize neighbor(X,Y) :- X - Y in [-1,1].
      singulars
      1. POSolving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
      1. USj4n bur53
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload