Prolog Logic Test Example

Question

I have a test coming up on Prolog and I can't really grasp the basic ideas of it. I kind of understand some of the examples I have been going through, but I can't sit down and know off hand how to solve a specific problem.

Our professor gave us some examples and I was wondering if someone could walk me through how to do it so I have some sort of idea how to approach things like this.

The example came from our book:

Donna, Danny, David, and Doreen were seated at a table. 
The men sat across from each other, as did the women. 
They each ordered a different drink and main course.

Facts:

Doreen sat beside the person that ordered steak
The chicken came with a coke
The person with lasagna sat across from the person with milk
David never drinks coffee
Donna only drinks water
Danny could not afford to order steak

I tried something where each person had a list associated with them and you would populate in the facts, but I don't think this is the correct approach. Could someone walk me through this? Thanks!

EDIT:

This is the code I ended up with, it finishes most of the puzzle, it leaves one of the entrees and one of the drinks out, but that should be fixable:

  sat_across([X,_,Y,_], X, Y).
  sat_across([_,X,_,Y], X, Y).

  sat_beside(T, X, Y) :-  % this is tricky
      nth1(N,T,X), nth1(M,T,Y),
      (N =:= M+1 ; N =:= M-1 ; N == 1, M == 4 ; N == 4, M == 1).
      not_connected(T, Place) :- \+ member(Place, T).
  connected(T, Place) :- member(Place, T).

  solve(T) :- T = [_,_,_,_],
      sat_across(T, (danny,_,_), (david,_,_)),
      sat_across(T, (donna,_,_), (doreen,_,_)),
      sat_beside(T, (doreen,_,_), (_,_,steak)),
      connected(T, (_,coke,chicken)),
      sat_across(T, (_,_,lasagna), (_,milk,_)),
      not_connected(T, (david,coffee,_)),
      connected(T, (donna,water,_)),
      not_connected(T, (danny,_,steak)).

Answer 1

Use pattern matching, with each position carrying an attribute triple: Name,Drink,Food.

Then we have a [N,S,W,E] table (abusing of contract Bridge convention) and we must apply all available constraints: I think could be done this way...

sat_across([X,_,Y,_], X, Y).
sat_across([_,X,_,Y], X, Y).
sat_across([X,_,Y,_], Y, X).
sat_across([_,X,_,Y], Y, X).

sat_beside(T, X, Y) :-  % this is tricky
    nth1(N,T,X), nth1(M,T,Y),
    (N =:= M+1 ; N =:= M-1 ; N == 1, M == 4 ; N == 4, M == 1).

cant_afford(T, Place) :- \+ member(Place, T).

solve(T) :- T = [N,S,W,E],
      sat_across(T, (danny,_,_), (david,_,_)),
      sat_across(T, (donna,_,_), (doreen,_,_)),
      sat_beside(T, (doreen,_,_), (_,_,steak)),
      ....
      cant_afford(T, (danny,_,steak)),
      ....

Answer 2

You should recognize that there are eight variables in this problem: the drinks and main courses for each person, so DonnaDrink, DannyFood, etc.

Your program should contrain these eight variables with = and \= according to the facts given, perhaps using extra predicates such as gender.

(This is actually a simple variant of the zebra puzzle, but without all the ordering.)

Answer 3

Sorry if I'm necro'ing this thread, but I wasn't really satisfied by the answers (they seem inelegant / incomplete).

This is a variant on the Zebra problem. The only real question is "What position is X in," where X can be a person, an entree, or a drink. Thus, your domain is { 1, 2, 3, 4 }, where each number represents a seat.

Then add your constraints, make sure that each item is in a unique position relative to other items of its type (that is, a person can only be in 1 seat, etc), and set prolog loose.

Oh, and don't forget to put your negative constraints last. Here's what I ended up with:

%  Organize the seating, so:
%  1  2
%  3  4
%  This means that "across" is always (n+2)%4
%  and "beside" is (n+1)%2

pos(1). pos(2). pos(3). pos(4).

beside(A,B) :- pos(A), B is (A+1) mod 2.
across(A,B) :- pos(A), B is (A+2) mod 4.

zebra(Donna,Danny,David,Doreen,
     Steak,Lasagna,Pizza,Chicken,
     Coke,Milk,Coffee,Water) :-
  % Our 4 given positive constraints
  beside(Doreen,Steak),
  Chicken=Coke,
  across(Lasagna,Milk),
  Donna=Water,
  % The men and women sat across from each other
  across(David,Danny),
  across(Doreen,Donna),
  % Ensure that each item is only in 1 position
  uniq_pos(Steak,Lasagna,Pizza,Chicken),
  uniq_pos(Coke,Milk,Coffee,Water),
  uniq_pos(Donna,Danny,David,Doreen),
  % The remaining two negative constraints.
  \+ David=Coffee,
  \+ Danny=Steak.

% Ensures that all 4 items are in unique positions.
uniq_pos(A,B,C,D) :-
  pos(A), pos(B), pos(C), pos(D),
  \+ A=B, \+ A=C, \+ A=D,
          \+ B=C, \+ B=D,
                  \+ C=D.

Seems to work. Prolog tells me that:
David, in seat 1, got steak and milk,
Doreen, in seat 2, got chicken and coke,
Danny, in seat 3, got lasagna and coffee, and
Donna, in seat 4, got pizza and water.

Hope this helps someone else who's trying to understand this problem.