Find the bug in this logic puzzle

Help!
1

I’m using: SWI-Prolog version 7.6.4

I want the code to: output all solutions.

But what I’m getting is: duplicates and wrong solutions

My code looks like this:

%
% 8 friends are sitting at a round table.
%
seating(Friends) :-
  length(Friends, 8),
  member(bruce, Friends),               % One of the friends is Bruce
  opposite(alice, david, Friends),          % Alice is sitting directly opposite of David
  inbetween(greta, henry, eugene, Friends), % Henry is sitting between Greta and Eugene.
  inbetween(greta, X, claire, Friends),
  member(X, Friends),                % There is one person between Greta and Claire.
  leftof(eugene, david, Friends),    % Eugene is sitting immediately to David's left.
  next(franny, Y, Friends),          % Franny is not next to Alice or David.
  dif(alice, Y), dif(david, Y).

opposite(X, Y, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(X, Y, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(X, Y, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(X, Y, Friends) :- Friends = [_, _, _, X, _, _, _, Y].
opposite(Y, X, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(Y, X, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(Y, X, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(Y, X, Friends) :- Friends = [_, _, _, X, _, _, _, Y].

inbetween(L, M, R, Friends) :- leftof(L, M, Friends), leftof(M, R, Friends).
inbetween(L, M, R, Friends) :- leftof(R, M, Friends), leftof(M, L, Friends).

next(X, Y, Friends) :- leftof(X, Y, Friends).
next(X, Y, Friends) :- leftof(Y, X, Friends).

leftof(X, Y, Friends) :- nextto(X, Y, Friends).
leftof(X, Y, Friends) :- Friends = [Y|_], last(X, Friends).

I’m getting:

$ prolog seating.pl 
Welcome to SWI-Prolog (threaded, 64 bits, version 7.6.4)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- seating(H).
H = [bruce, franny, claire, alice, greta, henry, eugene, david] ;
H = [bruce, franny, claire, alice, greta, henry, eugene, david] ;
H = [franny, bruce, claire, alice, greta, henry, eugene, david] ;
H = [franny, bruce, claire, alice, greta, henry, eugene, david] ;
H = [franny, bruce, claire, alice, greta, henry, eugene, david] ;
H = [franny, bruce, claire, alice, greta, henry, eugene, david]
...

The second solution is wrong since franny is sitting next to David (it’s a round table).

My Prolog is very rusty - I haven’t done it in some 20 years. I would appreciate any help.
The constraints of the puzzle are in comments.

I’m particularly confused by the dif/2 predicate, but even without it, it’s not properly backtracking through all solutions.

https://swish.swi-prolog.org/p/seating477.pl

2

Did you get this from somewhere or did you create it yourself?

Usually such code is commented in a blog somewhere.

FYI if you don’t already know.

This is a zebra puzzle and for other ways to solve them including with Prolog see:

RosettaCode Zebra puzzle and just Prolog variations.

3

I know it’s a Zebra puzzle. The Puzzle is a problem from bebraschallenge.org. I wrote the code myself.

4

Have you tried using trace to step through your code?

You are also calling your predicates in different modes. e.g. inbetween with a mixture of grounded and variable terms, do your predicates support being called in that mode? Try testing them out individually with different modes.

For example, is inbetween doing what you expect?
e.g.

length(F,8), inbetween(a,b,c,F).

and look at the results.
Is leftof doing what you expect? Hint it isn’t since you are using last incorrectly.

5

With regards to dif/2, I personally think of it as a half way point to constraints and when when I see it being used I ask myself why not just use constraints instead? As such dif/2 is not a friend of mine.

The way I currently think of dif/2 is that in true logic any of the statements can be used in any order but with Prolog that is not always true because the statements are executed in the way the predicate is written. To get around this dif/2 sort of comes to the rescue in that it will will try different ways simultaneously and the first one that gets an answer is used and the other way is discarded. IIRC this is done by using coroutining (which may be another thread or something) and thus why dif/2 is resource and time expensive to call.

HTH

So for me personally, to solve a zebra puzzle I would just go all in and use constraints. :slightly_smiling_face:

6

You should consider upgrading to a newer version. :slightly_smiling_face: For Windows and Ubuntu it is relatively easy, I don’t use Mac so can’t speak about that.

7

Try changing the last two lines to

  \+ next(franny, alice, Friends),          % Franny is not next to Alice.
  \+ next(franny, david, Friends).          % Franny is not next to David.

Also, replace length(Friends, 8), with

permutation([alice,bruce,claire,david,eugene,franny,greta,henry], Friends),

to avoid duplicates.

1 Like
8

So I’ve posted a ‘fixed’ version of your code with as little changes as possible.

If you want to figure it out yourself consider the following:

With a circular table of 8 seats, any seating position will have 8 solutions by symmetry, so to break symmetry and reduce the number of solutions, put someone into the first seat.

Your code is only checking that at least 1 neighbour of Franny is not David or Alice, in fact each person has two neighbours, so your constraint has to apply to all of them. (This is why you are getting solutions with David next to Franny, as her other neighbour is neither David or Alice).

Hope this helps to explain your results, welcome back to Prolog!

seating(Friends) :-
  length(Friends, 8),
  Friends = [bruce|_],                      % One of the friends is Bruce, to break symmetry assume
                                            % Bruce is in the first chair. (circular table).
  opposite(alice, david, Friends),          % Alice is sitting directly opposite of David
  inbetween(greta, henry, eugene, Friends), % Henry is sitting between Greta and Eugene.
  inbetween(greta, X, claire, Friends),     % Someone is between Greta and Claire, and its a Friend.
  member(X, Friends),                         %
  leftof(eugene, david, Friends),           % Eugene is sitting immediately to David's left.
  member(franny, Friends),                  % Franny is at the table.
  forall( next(franny, Y, Friends),         % Neither neighbour of Franny is Alice or David.
    (dif(alice, Y), dif(david, Y))).


opposite(X, Y, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(X, Y, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(X, Y, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(X, Y, Friends) :- Friends = [_, _, _, X, _, _, _, Y].
opposite(Y, X, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(Y, X, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(Y, X, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(Y, X, Friends) :- Friends = [_, _, _, X, _, _, _, Y].

inbetween(L, M, R, Friends) :- leftof(L, M, Friends), leftof(M, R, Friends).
inbetween(L, M, R, Friends) :- leftof(R, M, Friends), leftof(M, L, Friends).

next(X, Y, Friends) :- leftof(X, Y, Friends).
next(X, Y, Friends) :- leftof(Y, X, Friends).

leftof(X, Y, Friends) :- nextto(X, Y, Friends).
leftof(X, Y, Friends) :- Friends = [Y|_], last(Friends, X).
9

It should be last(Friends, X). Well spotted.

10

I see. It should be

last(Friends, X)

as per last/2. The API of this list library isn’t exactly uniform, it seems. member/2 is member(Elem, List).

I had originally tried that, but wrongly attributed the failure to my not understanding \+.

I was hoping to find a solution that doesn’t require me to list all 8 friends, but rather in a way that Prolog infers the membership (who the friends are).

In any event, with \+, permutation, and correct use of last I get the expected answer:

%
% 8 friends are sitting at a round table.
%
seating(Friends) :-
  permutation([alice,bruce,claire,david,eugene,franny,greta,henry], Friends),
  opposite(alice, david, Friends),          % Alice is sitting directly opposite of David
  inbetween(greta, henry, eugene, Friends), % Henry is sitting between Greta and Eugene.
  inbetween(greta, X, claire, Friends), 
  member(X, Friends),                % There is one person between Greta and Claire.
  leftof(eugene, david, Friends),    % Eugene is sitting immediately to David's left.
  \+ next(franny, alice, Friends),   % Franny is not next to Alice or David.
  \+ next(franny, david, Friends).

opposite(X, Y, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(X, Y, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(X, Y, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(X, Y, Friends) :- Friends = [_, _, _, X, _, _, _, Y].
opposite(Y, X, Friends) :- Friends = [X, _, _, _, Y, _, _, _].
opposite(Y, X, Friends) :- Friends = [_, X, _, _, _, Y, _, _].
opposite(Y, X, Friends) :- Friends = [_, _, X, _, _, _, Y, _].
opposite(Y, X, Friends) :- Friends = [_, _, _, X, _, _, _, Y].

inbetween(L, M, R, Friends) :- leftof(L, M, Friends), leftof(M, R, Friends).
inbetween(L, M, R, Friends) :- leftof(R, M, Friends), leftof(M, L, Friends).
    
next(X, Y, Friends) :- leftof(X, Y, Friends).
next(X, Y, Friends) :- leftof(Y, X, Friends).

leftof(X, Y, Friends) :- nextto(X, Y, Friends).
leftof(X, Y, Friends) :- Friends = [Y|_], last(Friends, X).

Last question: does this look idiomatic? Is there a better way to express opposite, inbetween, etc.?
The member(X, Friends) to express that the person between greta and claire is a friend is now redundant, it seems.

This was installed with apt-get on a Ubuntu 20.04.3 LTS a few minutes ago, so I’d rather the package maintainers upgrade if this is necessary.

11

As you may have noticed, Prolog is a bit tribalistic, and using dif (@A, @B) instead of @A \== @B is an example in that since dif is part of Constraint Logic Programming, a dialect as opposed to plain vanilla.

Personally, I prefer plain vanilla to dialects since I hop between a lot of programming languages. But a problem like this could probably be knocked down to a couple of lines of code with expertise in CLP.

12

Without using permutation (?Xs, ?Ys), fixing the argument order in last (?List, ?Last), and changing the last two lines

seating(Friends) :-
  length(Friends, 8),
  member(bruce, Friends),               % One of the friends is Bruce
  opposite(alice, david, Friends),          % Alice is sitting directly opposite of David
  inbetween(greta, henry, eugene, Friends), % Henry is sitting between Greta and Eugene.
  member(X, Friends),                % There is one person between Greta and Claire.
  inbetween(greta, X, claire, Friends),
  leftof(eugene, david, Friends),    % Eugene is sitting immediately to David's left.
  member(franny, Friends),               % One of the friends is Franny
  \+ next(franny, alice, Friends),
  \+ next(franny, david, Friends).

Then running seating(Friends), Friends = [alice|_]. gives one solution [alice, greta, henry, eugene, david, bruce, franny, claire] which as far as I can tell doesn’t break any constraints. Note member(franny, Friends), is needed for the negation statements to work.

It’s interesting that the original

  next(franny, Y, Friends),          % Franny is not next to Alice or David.
  dif(alice, Y), dif(david, Y).

doesn’t filter out [alice, greta, henry, eugene, david, franny, bruce, claire]. I guess it passes because although franny is next to david, she is also next to bruce

13

There is nothing half baked about dif/2. It is a clear constraint that suits a clear purpose. Acting on arbitrary terms, there is also no domain specific knowledge in it. That means it doesn’t do anything clever such as clpfd which you can tell X #> 1 and X #=< 1 and than deduces X = 1. You can only do that if you know arithmetic and you know (demand) X to be constraint to a term from the domain (integer for clpfd). dif/2 only knows about (dis)equality and thus doesn’t do any of this magic. dif/2 is mostly good if you have some relation(X,Y) and you only want the answers where X and Y are not equal. Now you can use \==/2 at a point where the terms are ground or you can use dif/2 before relation(X,Y) which makes sure that paths during the computation are abandoned as soon as X and Y become equal.

1 Like