Problem with simple recursion task in Prolog

Question

I'm currently solving some problems in prolog and I can't seem to get it work with one question regarding recursion, I have been presented with this table: Gryffindor Table.

Given that information, I made my own KB with this content:

/*
 This order represents how they are sit from left to right
 parvati_patil is left to lavender_brown,
 lavender_brown is left to neville_longbottom
 and so on, until we reach parvati again at the end.
*/

seatedTogether(parvati_patil, lavender_brown).
seatedTogether(lavender_brown, neville_longbottom).
seatedTogether(neville_longbottom, alicia_spinnet).
seatedTogether(alicia_spinnet, fred_weasley).
seatedTogether(fred_weasley, george_weasley).
seatedTogether(george_weasley, lee_jordan).
seatedTogether(lee_jordan, dennis_creevey).
seatedTogether(dennis_creevey, dean_thomas).
seatedTogether(dean_thomas, ginny_weasley).
seatedTogether(ginny_weasley, angelina_johnson).
seatedTogether(angelina_johnson, seamus_finnigan).
seatedTogether(seamus_finnigan, colin_creevey).
seatedTogether(colin_creevey, harry_potter).
seatedTogether(harry_potter, hermione_granger).
seatedTogether(hermione_granger, ron_weasley).
seatedTogether(ron_weasley, natalie_mcdonald).
seatedTogether(natalie_mcdonald, katie_bell).
seatedTogether(katie_bell, parvati_patil).

% X is left to Y if they are seatedTogether(X,Y)
isAtLeft(X,Y):-seatedTogether(X,Y).
% X is right to Y if they are seatedTogether(Y,X)
isAtRight(X,Y):-seatedTogether(Y,X).

/*
 This rule just tells us who X is two places away from Y,
 X is two places away from Y if 
 X is seatedTogether(X,Z)
 and that Z is seatedTogether(Z,Y).
*/
twoPlacesAway(X,Y):-seatedTogether(X, Z), seatedTogether(Z,Y).

/*
  This rule just tells us whos sitting @ the table
  by just unifying X with the values of seatedTogether(X,Y)
  without regarding Y.
*/
atTable(X):-seatedTogether(X,_).


/*
  Between two:
  Its supposed to tell us whos Z is between X and Y
  The perfect case (for me) would be that X and Y are sitting
  together, so they have no one in the middle.
  The other way around would be that
  X is not equal to Y
  X1 is sitting left to X,
  and then we call it again with
  X1, Y and Z1 as args,
  after each call, we equal
  Z to X1 value.
*/
betweenTwo(X,Y,Z):-isAtLeft(X,Y),isAtRight(Y,X).
betweenTwo(X,Y,Z):-
    X \= Y,
    isAtLeft(X, X1),
    betweenTwo(X1, Y, Z1),
    Z = X1.

The problem comes with the last rule definition, if I call it like this:

betweenTwo(ron_weasley, alicia_spinnet, Z).

The value of Z should be:

• natalie_mcdonald,
• katie_bell,
• parvati_patil,
• lavender_brown,
• neville_longbottom.

But Z only unifies with the value of

• natalie_mcdonald.

I believe I'm super close to it, but I'm really lost on what's going wrong with that rule. I defined it so X step by step equals the value of Y, but with the value before Y it should fall in the perfect case and stop moving, and unify the rest of elements before it. Any ideas?

Answer 1

First: your base case (what you call "perfect case") says "if X is at left of Y, and Y is at right of X, then every Z is between them", instead of "no one is between them" (the conditions are redundant as well). The base case should say when the predicate holds (that is, when some Z is between X and Y), not when it doesn't. See also this answer: https://stackoverflow.com/a/3001941/9204

Second: in the non-base case, you have

isAtLeft(X, X1),
betweenTwo(X1, Y, Z1),
Z = X1.

When Prolog searches for X1 in isAtLeft(ron_weasley, X1), the only answer is natalie_mcdonald, and later Z = X1 forces Z to be natalie_mcdonald too.

So this part of your code is equivalent to

isAtLeft(X, Z),
betweenTwo(Z, Y, Z1).

or in words "Z is between X and Y if: X is not equal to Y, X is directly to the left of Z, and some Z1 is between Z and Y", which doesn't make sense.

You should note the warning about singleton variable Z1, too.