Strange warning and computation result in constraint logic program

344 views Asked by At

First, sorry for posting the whole program, but as I don't know were the problem is I don't know which parts are irrelevant. These are two slightly different implementations of the same logic puzzle in SWI-Prolog, the first one succeeds the second one fails and I can't find the reason for the failure.

The puzzle:

4 persons are having a diner:
Donna, Doreen, David, Danny

the woman (Donna,Doreen) are sitting vis-a-vis.
the men (David,Danny) are sitting vis-a-vis.

Each of them picked a unique meal and beverage.

1) Doreen sits next to the person that ordered risotto.
2) the salad came with a coke.
3) the person with the lasagna sits vis-a-vis the person with the milk.
4) david never drinks coffee.
5) donna only drinks water.
6) danny had no appetite for risotto.

who ordered the pizza?

I choose the following approach

table with positions:

  1
4 O 2
  3

domain: positions{1,2,3,4}
variables: persons, meals, beverages

First the inefficient succeeding implementation:

solution(Pizza, Doreen, Donna, David, Danny) :-

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk),

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    next_to(Doreen,Risotto),
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    \+ David = Coffee,
    Donna = Water,
    \+ Danny = Risotto.



unique(X1,X2,X3,X4) :-
    pos(X1),
    pos(X2),
    \+ X1 = X2,
    pos(X3),
    \+ X1 = X3, \+ X2 = X3,
    pos(X4),
    \+ X1 = X4, \+ X2 = X4, \+ X3 = X4.

right(1,2).
right(2,3).
right(3,4).
right(4,1).

vis_a_vis(1,3).
vis_a_vis(3,1).
vis_a_vis(2,4).
vis_a_vis(4,2).

next_to(X,Y) :- right(X,Y).
next_to(X,Y) :- right(Y,X).

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

This works and gives the right result. But when I try to reorder the clauses of the solution procedure to be more efficient (this is the second implementation)

solution(Pizza, Doreen, Donna, David, Danny) :-

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    \+ David = Coffee,
    Donna = Water,
    \+ Danny = Risotto,

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk).

    %% all other predicates are like the ones in the first implementation

I get a unassigned variable warning when trying to load the file:

Warning: /home/pizza.pl:28:
Singleton variable in \+: Coffee

and the computation returns false. But shouldn't it return the same result? I see no reason for the difference...

1

There are 1 answers

2
CapelliC On BEST ANSWER

the warning is due to the fact that Coffe and Risotto are unbound when the negation is executed. If you replace \+ David = Coffee, by David \= Coffee, you will avoid the warning, but the solution cannot will not be computed. Should be clear indeed that since Coffee is unbound, David \= Coffee will always fail. You can use dif/2, the solution will work and will be more efficient. I've named solution1/2 your first snippet, and solution2/5 this one (using dif/2):

solution2(Pizza, Doreen, Donna, David, Danny) :-

    % general setting
    vis_a_vis(Donna,Doreen),
    vis_a_vis(David,Danny),

    % the six constraints
    next_to(Doreen,Risotto), % note: you forgot this one
    Salad = Coke,
    vis_a_vis(Lasagna,Milk),
    dif(David, Coffee),
    Donna = Water,
    dif(Danny, Risotto),

    % assignment of unique positions to the variables
    unique(Doreen,Donna,David,Danny),
    unique(Lasagna,Pizza,Risotto,Salad),
    unique(Water,Coke,Coffee,Milk).

a small test:

?- time(aggregate_all(count,solution1(P,A,B,C,D),N)).
% 380,475 inferences, 0.058 CPU in 0.058 seconds (100% CPU, 6564298 Lips)
N = 8.

?- time(aggregate_all(count,solution2(P,A,B,C,D),N)).
% 10,626 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 4738996 Lips)
N = 8.