# Find the bug in this logic puzzle

**URL:** <https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649>\
**Category:** Help!\
**Created:** [November 11, 2021, 4:00pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649 "2021-11-11T16:00:01Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![godmar](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/godmar/32/3831_2.png) [@godmar](https://swi-prolog.discourse.group/u/godmar)\
**Post date:** [November 11, 2021, 4:00pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/1 "2021-11-11T16:00:01Z")

</div>

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:

```prolog
%
% 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
$ 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](https://swish.swi-prolog.org/p/seating477.pl)

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [November 11, 2021, 4:28pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/2 "2021-11-11T16:28:04Z")

</div>

> [@godmar](#):
>
> I’m particularly confused by the `dif/2` predicate

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](https://en.wikipedia.org/wiki/Zebra_Puzzle) and for other ways to solve them including with Prolog see:

RosettaCode [Zebra puzzle](https://rosettacode.org/wiki/Zebra_puzzle) and just [Prolog variations](https://rosettacode.org/wiki/Zebra_puzzle#Prolog).

---

<div class="post-metadata">

**Author:** ![godmar](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/godmar/32/3831_2.png) [@godmar](https://swi-prolog.discourse.group/u/godmar)\
**Post date:** [November 11, 2021, 4:30pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/3 "2021-11-11T16:30:50Z")

</div>

I know it’s a Zebra puzzle. The Puzzle is a problem from [bebraschallenge.org](https://www.bebraschallenge.org/). I wrote the code myself.

---

<div class="post-metadata">

**Author:** ![Ian](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/ian/32/1026_2.png) [@Ian](https://swi-prolog.discourse.group/u/Ian)\
**Post date:** [November 11, 2021, 4:36pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/4 "2021-11-11T16:36:47Z")

</div>

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.

```prolog
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.

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [November 11, 2021, 4:49pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/5 "2021-11-11T16:49:16Z")

</div>

With regards to dif/2, I personally think of it as a half way point to [constraints](https://www.swi-prolog.org/pldoc/man?section=clp) 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](https://www.swi-prolog.org/pldoc/man?section=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. 🙂

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [November 11, 2021, 4:57pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/6 "2021-11-11T16:57:09Z")

</div>

> [@godmar](#):
>
> `(threaded, 64 bits, version 7.6.4)`

You should consider upgrading to a newer version. 🙂 For [Windows](https://swi-prolog.discourse.group/t/install-swi-prolog-development-version-on-windows-10/1131) and [Ubuntu](https://swi-prolog.discourse.group/t/install-swi-prolog-development-version-on-ubuntu-using-ppa/2402) it is relatively easy, I don’t use Mac so can’t speak about that.

---

<div class="post-metadata">

**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\
**Post date:** [November 11, 2021, 6:43pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/7 "2021-11-11T18:43:56Z")

</div>

> [@godmar](#):
>
> ```prolog
> 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).
> 
> ```

Try changing the last two lines to

```prolog
  \+ 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

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

```

to avoid duplicates.

---

<div class="post-metadata">

**Author:** ![Ian](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/ian/32/1026_2.png) [@Ian](https://swi-prolog.discourse.group/u/Ian)\
**Post date:** [November 11, 2021, 7:43pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/8 "2021-11-11T19:43:11Z")

</div>

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!

```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).

```

---

<div class="post-metadata">

**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\
**Post date:** [November 11, 2021, 7:55pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/9 "2021-11-11T19:55:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![godmar](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/godmar/32/3831_2.png) [@godmar](https://swi-prolog.discourse.group/u/godmar)\
**Post date:** [November 11, 2021, 7:55pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/10 "2021-11-11T19:55:55Z")

</div>

> [@Ian](#):
>
> Hint it isn’t since you are using last incorrectly.

I see. It should be

```prolog
last(Friends, X)

```

as per [last/2](https://www.swi-prolog.org/pldoc/man?predicate=last/2). The API of this list library isn’t exactly uniform, it seems. `member/2` is `member(Elem, List)`.

> [@joeblog](#):
>
> Try changing the last two lines to
> 
> ```prolog
> \+ next(franny, alice, Friends), % Franny is not next to Alice.
> \+ next(franny, david, Friends). % Franny is not next to David.
> 
> ```

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

> [@joeblog](#):
>
> Also, replace `length(Friends, 8), ` with
> 
> ```prolog
> permutation([alice,bruce,claire,david,eugene,franny,greta,henry], Friends),
> 
> ```
> 
> to avoid duplicates.

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:

```prolog
%
% 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.

> [@EricGT](#):
>
> You should consider upgrading to a newer version. 🙂

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.

---

<div class="post-metadata">

**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\
**Post date:** [November 11, 2021, 8:08pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/11 "2021-11-11T20:08:42Z")

</div>

As you may have noticed, Prolog is a bit tribalistic, and using [**dif** (@A, @B)](https://www.swi-prolog.org/pldoc/doc_for?object=dif/2) instead of [@A **\==** @B](https://www.swi-prolog.org/pldoc/doc_for?object=(%5C%3D%3D)/2) is an example in that since dif is part of [Constraint Logic Programming](https://www.swi-prolog.org/pldoc/man?section=clp), 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.

---

<div class="post-metadata">

**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\
**Post date:** [November 12, 2021, 11:13am UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/12 "2021-11-12T11:13:26Z")

</div>

Without using [**permutation** (?Xs, ?Ys)](https://www.swi-prolog.org/pldoc/doc_for?object=permutation/2), fixing the argument order in [**last** (?List, ?Last)](https://www.swi-prolog.org/pldoc/doc_for?object=last/2), and changing the last two lines

```prolog
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

```prolog
  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

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [November 12, 2021, 12:40pm UTC](https://swi-prolog.discourse.group/t/find-the-bug-in-this-logic-puzzle/4649/13 "2021-11-12T12:40:11Z")

</div>

> [@EricGT](#):
>
> With regards to [dif/2](https://www.swi-prolog.org/pldoc/doc_for?object=dif/2), I personally think of it as a half way point to [constraints](https://www.swi-prolog.org/pldoc/man?section=clp) and when when I see it being used I ask myself why not just use constraints instead? As such [dif/2](https://www.swi-prolog.org/pldoc/doc_for?object=dif/2) is not a friend of mine.

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.