Different version of Einstein Riddle

Help!
1

Hello, I have a task to write the Einstein riddle.
Friends: Jarek, Franek, Stefan, Albert, Szymon, Robert, Marcin live in one building, each on a different floor (0,1,2,…).
Each of them has a different pet: dog, cat, fish, hamster, parrot, snake, canary.
Which floor does each of them live on, and what kind of pet does it have, if the following statements are true?

  1. Franek doesn’t have a dog.
  2. Owner of a dog lives on floor 2.
  3. Albert doesn’t have a hamster.
  4. Owner of a hamster lives on floor 0.
  5. Marcin lives lower than Stefan.
  6. Owner of a canary lives on floor 6.
  7. Robert doesn’t have a snake.
  8. Owner of a snake lives on floor 3.
  9. Franek lives lower than Albert.
  10. Franek lives higher than Robert.
  11. Owner of a cat lives on floor 5.
  12. Owner of a parrot lives on floor 1.
  13. Szymon lives higher than Stefan.
  14. Marcin lives lower than Szymon.
  15. Marcin lives lower than Jarek.
  16. Owner of a fish lives on floor 4.
  17. Marcin lives lower than Robert.
  18. Stefan doesn’t have a canary.
  19. Stefan lives lower than Albert.
  20. Albert lives higher than Robert.
  21. Robert doesn’t have a parrot.
  22. Stefan doesn’t have a cat.
  23. Szymon lives higher than Franek.
  24. Albert lives higher than Marcin.
  25. Szymon doesn’t have a hamster.
  26. Jarek doesn’t have a snake.
  27. Franek lives higher than Marcin.
  28. Stefan lives lower than Franek.
  29. Szymon doesn’t have a dog.
  30. Marcin doesn’t a canary.
  31. Jarek doesn’t have a dog.
  32. Jarek doesn’t have a fish.
  33. Albert doesn’t have a dog.
  34. Albert lives higher than Szymon.
  35. Szymon doesn’t have a parrot.
  36. Szymon lives higher than Robert.
  37. Robert lives higher than Jarek.
  38. Marcin doesn’t have a snake.
  39. Jarek lives lower than Albert.
  40. Jarek lives lower than Franek.
  41. Stefan lives higher than Jarek.
  42. Szymon lives higher than Jarek.
  43. Robert doesn’t have a fish.
  44. Robert lives lower than Stefan.
  45. Albert doesn’t have a snake.
  46. Robert doesn’t have a cat…
  47. Jarek doesn’t have a canary.
  48. Marcin doesn’t have a fish.
  49. Jarek doesn’t have a cat
  50. Stefan doesn’t have a parrot.
  51. Albert doesn’t have a cat.
  52. Stefan doesn’t have a hamster.
  53. Franek doesn’t have a canary.
  54. Szymon doesn’t have a snake.
  55. Stefan doesn’t have a dog.
  56. Stefan doesn’t have a fish.
  57. Robert doesn’t have a hamster.
  58. Albert doesn’t have a fish.
  59. Robert doesn’t have a canary.
  60. Jarek doesn’t have a hamster.
  61. Franek doesn’t have a snake.
  62. Szymon doesn’t have a canary.
  63. Franek doesn’t have a parrot.
  64. Albert doesn’t have a parrot.
  65. Marcin doesn’t have a dog.
  66. Szymon doesn’t have a fish.

The problem is when i write

?- puzzle(Table)

the answer is

false

This is wrong, because i conclude that, for example, Robert has a dog, so lives on floor 2.
I don’t know, where is the problem.
Here is my code.

puzzle(Table) :-
  Table = [row(_, 0, hamster),   % Owner of a hamster lives on floor 0.
           row(_, 1, papuga),   % Owner of a parrot lives on floor 1.
           row(_, 2, pies),     % Owner of a dog lives on floor 2.
           row(_, 3, waz),      % Owner of a snake lives on floor 3.
           row(_, 4, rybka),    % Owner of a fish lives on floor 4.
           row(_, 5, kot),      % Owner of a cat lives on floor 5.
           row(_, 6, kanarek)], % Owner of a canary lives on floor 6.
  memberchk(row('Franek', LFranek, AFranek), Table),
  memberchk(row('Albert', LAlbert, AAlbert), Table),
  memberchk(row('Robert', LRobert, ARobert), Table),
  memberchk(row('Stefan', LStefan, AStefan), Table),
  memberchk(row('Simon', LSzymon, ASzymon), Table),
  memberchk(row('Jarek', LJarek, AJarek), Table),
  memberchk(row('Marcin', LMarcin, AMarcin), Table),
  % Franek doesn't have a dog.
  % Franek doesn't a parrot.
  % Franek doesn't a snake.
  % Franek doesn't a canary.
  \+ memberchk(AFranek, [dog, parrot, snake, canary]),
  % Albert no dog
  % Albert no cat
  % Albert no fish
  % Albert no hamster
  % Albert no parrot
  % Albert no snake
  % Albert no canary
  \+ memberchk(AAlbert, [dog, cat, fish, hamster, parrot, snake, canary]),
  % Robert no cat.
  % Robert no fish. 
  % Robert no hamster.
  % Robert no parrot.
  % Robert no snake.
  % Robert no canary.  
  \+ memberchk(ARobert, [cat, fish, hamster, parrot, snake, canary]),
  % Stefan no dog.
  % Stefan no cat.
  % Stefan no fish.
  % Stefan no hamster.
  % Stefan no parrot.    
  % Stefan no canary.
  \+ memberchk(AStefan, [dog, cat, fish, hamster, parrot, canary]),
  % Szymon no dog.
  % Szymon no fish.
  % Szymon no hamster
  % Szymon no parrot
  % Szymon no snake
  % Szymon no canary
  \+ memberchk(ASzymon, [dog, fish, hamster, parrot, snake, canary]),
  % Jarek no dog
  % Jarek no cat
  % Jarek no fish
  % Jarek no hamster
  % Jarek no snake
  % Jarek no canary
  \+ memberchk(AJarek, [dog, cat, fish, hamster, snake, canary]),
  % Marcin no dog
  % Marcin no fish
  % Marcin no snake
  % Marcin no canary
  \+ memberchk(AMarcin, [dog, fish, snake, canary]),
  LMarcin < LStefan,   % 5.
  LFranek < LAlbert,   % 9.
  LFranek > LRobert,   % 10.
  LSzymon > LStefan,   % 13. 
  LMarcin < LSzymon,   % 14.
  LMarcin < LJarek,    % 15.
  LMarcin < LRobert,   % 17.
  LStefan < LAlbert,   % 19.
  LAlbert > LRobert,   % 20.
  LSzymon > LFranek,   % 23.
  LAlbert > LMarcin,   % 24.
  LFranek > LMarcin,   % 27.
  LStefan < LFranek,   % 28.
  LAlbert > LSzymon,   % 34.
  LSzymon > LRobert,   % 36.
  LRobert > LJarek,    % 37.
  LJarek < LAlbert,    % 39.
  LJarek < LFranek,    % 40.
  LStefan > LJarek,    % 41.
  LSzymon > LJarek,    % 42.
  LRobert < LStefan.   % 44.

Please tell me what’s wrong with it and how it should be done.
Thank you in advance.

2

An obvious problem is the language change, eg papuga in the initalisation and then parrot in the subsequent query.

Not sure if it will work if you get the names consistent.

Generally, negated queries such as

\+ memberchk(AFranek, [dog, parrot, snake, canary])

may always return false if the variable, AFranek in this case, haven’t been set first.

A subtlety about negated predicates in Prolog that initially tripped me up is they are always false if they contain a variable. This is due to a convention negation as failure explained in this paper by Keith Clark.

I’d suggest rather listing the animals Franek could have rather than the ones he doesn’t have.

3

Not completely on topic, but I’m not sure that’s generally true, we can easily get successful negative queries even with unbound variables, e.g.:

?- \+ memberchk(X, []).
true.

But maybe I misunderstood your comment.

4

Reading the riddle and writing small prolog codes, I guess order of persons w.r.t living floor as follows.

'LFranek' < 'LAlbert' <  'LJarek' <  'LMarcin' < 'LRobert' < 'LStefan' < 'LSzymon'.

I am not sure it is correct. If it is correct then search space for solutions might be simple.

5

Use e.g. trace to debug your program - SWI-Prolog -- Debugging and Tracing Programs

1 Like
6 
?- \+ memberchk(X, []).
true.

“Anything is not in the empty set” I guess is true, but it doesn’t help much in figuring out what X is.

I generally find it a good rule of thumb to write queries avoiding negation wherever possible, because there are a lot of traps. I put some notes I wrote for myself as I worked through this on the web here

7

I recall this puzzle was posted previously and I did a solution which I posted a while back. I just found it on my 'puter and put it on swish here

https://swish.swi-prolog.org/p/floors-pets.swinb

I used negated memberchk which works fine since the variables are given values at the top of the rule.

The problem with the above code is the names of the pets have been written in Polish at the top and then what seems suspiciously similar to my code using English names has been cut 'n pasted below it.

8

For this kind of puzzle, you can do this:

freeze(AFranek, \+ memberchk(AFranek, [dog, parrot, snake, canary]))

which will delay the call to \+memberchk(…) until AFranek has a value. And if you put the test before the generation of possible values, it will help prune impossible combinations more quickly (you do delayed-test&generate rather than generate&test).

Using dif/2, you can write this test instead like this:

dif(AFranek,dog), dif(AFranek,parrot), dif(AFranek,snake), dif(AFranek,canary)

or

maplist(dif(AFranek), [dog,parrot,snake,canary])

And there are more ways of setting up constraints in library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains, although that’s probably overkill for this puzzle.

3 Likes
9

Thanks I’ve added a second way of writing puzzle(Table) using freeze for future reference at SWISH -- SWI-Prolog for SHaring

10

You can also put freeze/1 around the inequality tests, and move the rules that instantiate the possibilities to the end.
That’s what I meant by delayed-test&generate vs generate&test … the delayed tests “fire” as values get instantiated, which can often remove large parts of the search space. CLP(FD) goes further, by actively propagating constraint information, e.g. all_distinct/1.

1 Like
11

I’ve put a third version of the solution at SWISH -- SWI-Prolog for SHaring which puts all the conditions within freeze clauses.

I thought that would allow them to be placed in any order, but not so. If you move one of the inequality conditions to the top, it gives a “Arguments are not sufficiently instantiated” error.

12

Your freeze won’t work:

?- freeze([A, B], A < B).
ERROR: Arguments are not sufficiently instantiated

… because giving the list 2 elements makes the list nonvar/1 and hence the freeze/2 is triggered immediately.

Can use instead:

freeze_lt(Low, High) :-
    when(ground((Low, High)), Low < High).

Example:

?- freeze_lt(A, B), A=5, B=6.
A = 5,
B = 6.

?- freeze_lt(A, B), A=5, B=4.
false.
2 Likes
13

Thanks. I’ve updated the third way of doing it to use when/2 and ground/1