Logic Puzzle in Prolog - using lists

问题:

I am trying to solve the following problem in Prolog, and I think I have coded it right, but my queries simply return false. Any advice on what to change? The problem is as follows:

"Bagel Alley, the local bagel shop, was always a location of furious activity during the morning commute as people stopped by to get their coffee and bagel on the way to work. Fresh made on site each morning, the bagels were highly popular and the fact that the shop also had great coffee was like icing on the cake! The people who worked at Bagel Alley were cheerful and friendly, as well as competent, so despite the large volume of customers, the wait was never long or unpleasant. Joe and four of his coworkers stopped by this morning to see what everyone was raving about and were pleasantly surprised to find that the shop lived up to its reputation. Determine the name of each coworker, what kind of bagel with its topping, and what flavor and size of coffee (small, medium, or large) each ordered."

1. Brad got his bagel, which wasn’t wheat, with nothing on it. Walt ordered a small coffee.

2. The two coworkers who got medium sized coffees were the one who got the hazelnut flavor and the one who got his bagel with peanut butter.

3. The one who got the onion bagel, but not with butter, also got a French vanilla coffee, but not the small size.

4. The five coworkers were Joe, the one who got a large coffee, the one who got Amaretto flavored coffee, the one who got a wheat bagel, and the one who got egg & bacon on his bagel.

5. Rick didn’t order the blueberry bagel but he did get Columbian coffee. The Amaretto coffee was ordered with the cheddar bagel but not by Walt.

6. The cream cheese did not come with the blueberry bagel but it did come with a large coffee. The sesame bagel came with butter but Carlos didn’t order it.

The Prolog code I have written is here:

bagels(Sol):-
   Sol = [[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_]],
   member([brad,X,plain,_,_], Sol), X \== wheat,
   member([walt,_,_,small,_], Sol),
   member([_,_,_,medium1,hazelnut], Sol),
   member([_,_,peanut_butter,medium2,_], Sol),
   member([_,onion,Y,Z,french_vanilla], Sol), Y \== butter, Z \== small,
   member([joe,Ja,Jb,Jc,Jd], Sol),Ja\==wheat,Jb\==egg_bacon,Jc\==large,Jd==amaretto,
   member([La,Lb,Lc,large,Ld], Sol), La\==joe,Lb\==wheat,Lc\==egg_bacon,Ld\==amaretto,
   member([Aa,Ab,Ac,Ad,amaretto], Sol), Aa\==joe,Ab\==wheat,Ac\==egg_bacon,Ad\==large,
   member([Wa,wheat,Wb,Wc,Wd], Sol), Wa\==joe,Wb\==egg_bacon,Wc\==large,Wd\==amaretto,
   member([Ea,Eb,egg_bacon,Ec,Ed], Sol), Ea\==joe,Eb\==wheat,Ec\==large,Ed\==amaretto,
   member([rick,R,_,_,columbian], Sol),R\==blueberry,
   member([A,cheddar,_,_,amaretto], Sol), A\==walt,
   member([_,B,cream_cheese,large,_], Sol), B\==blueberry,
   member([C,sesame,butter,_,_], Sol), C \== carlos,
   member([_,_,_,other,_], Sol),
   member([_,_,_,_,other], Sol).

I believe that running the query "bagels(X)." should give me the solution to the problem, but it returns false. Am I missing something? Many thanks in advance!

回答1:

First, it seems that the problem statement needs some review - in particular point 4.

What you have here is a logical puzzle. Thus you really need to stick to the logical part of Prolog. However, in your code I see (\==)/2 and (==)/2 which both do not fully realize the logical relations they pretend to represent. Instead, use dif/2 and (=)/2 respectively.

But even after replacing those, things are not much better, your program still fails. However, with a pure definition you have a chance to localize the problem. Your problem is that bagels(Sols) fails. Thus, the current definition is too specialized, too narrow. So I will try to generalize it by removing some of your requirements. To this end, I will add * in front of some of your goals. I will generalize them such that the resulting program still fails.

What is left is a generalization that shows you where you will have to modify your program. Otherwise, the error will persist.

Edit: I have highlighted what looks particularly odd to me: Two men drinking amaretto.

:- op(950, fy, *).
*_.

bagels(Sol):-
   Sol = [[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_]],
   member([brad,X,plain,_,_], Sol),
      dif(X,wheat),
   member([walt,_,_,small,_], Sol),
   member([_,_,_,medium1,hazelnut], Sol),
   * member([_,_,peanut_butter,medium2,_], Sol),
   member([_,onion,Y,Z,french_vanilla], Sol),
      * dif(Y,butter),
      dif(Z,small),
   member([joe,Ja,Jb,Jc,Jd], Sol),
      * dif(Ja,wheat), * dif(Jb,egg_bacon),
      dif(Jc,large),
      Jd=amaretto,
   * member([La,Lb,Lc,large,Ld], Sol),
      * dif(La,joe), * dif(Lb,wheat), * dif(Lc,egg_bacon), * dif(Ld,amaretto),
   member([Aa,Ab,Ac,Ad,amaretto], Sol),
      dif(Aa,joe),
      * dif(Ab,wheat), * dif(Ac,egg_bacon), * dif(Ad,large),
   member([Wa,wheat,Wb,Wc,Wd], Sol),
      * dif(Wa, joe), * dif(Wb, egg_bacon),
      dif(Wc, large),
      dif(Wd, amaretto),
   member([Ea,Eb,egg_bacon,Ec,Ed], Sol),
      * dif(Ea, joe),
      dif(Eb, wheat),
      * dif(Ec, large),
      dif(Ed, amaretto),
   member([rick,R,_,_,columbian], Sol),
      * dif(R,blueberry),
   * member([A,cheddar,_,_,amaretto], Sol),
      * dif(A,walt),
   member([_,B,cream_cheese,large,_], Sol),
      * dif(B,blueberry),
   * member([C,sesame,butter,_,_], Sol),
      * dif(C, carlos),
   * member([_,_,_,other,_], Sol),
   * member([_,_,_,_,other], Sol).

Still, you might be unhappy: Why is there so much code left? The reason for this is that you forgot to state some general observations in the beginning. In particular that they wanted all a different topping. With that information the program fragment shrinks down to just the lines highlighted. However, one has to start with the following goals using library(lambda).

bagels(Sol):-
   Sol = [[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_],[_,_,_,_,_]],
    maplist(Sol+\P^member([P|_], Sol),
          [brad,walt,joe,rick,carlos]),
    maplist(Sol+\D^member([_,_,_,_,D], Sol),
          [amaretto,french_vanilla,hazelnut,columbian,other]),
    ...

回答2:

I've tried to improve readability, using a DCG to pass the state around (look for 'Implicitly passing states around' in this page), so this snippet is very different than your solution.

You can see that negative knowledge is espressed in two different ways: where people is involved, we can directly use \=, since names are always instantiated, but for other values, like kind(brad, K), I use {dif(K, wheat)}, since K could be not instantiated yet.

state(S), [state(T)] --> [state(T)], {member(S, T)}.

kind(P, K)  --> state([P, K, _, _, _]).
topping(P, T)   --> state([P, _, T, _, _]).
flavor(P, F)    --> state([P, _, _, F, _]).
size(P, S)  --> state([P, _, _, _, S]).


hint1 -->
  kind(brad, K), {dif(K, wheat)}, topping(brad, plain), size(walt, small).
hint2 -->
  size(P1, medium), size(P2, medium), {P1 \= P2},
  flavor(P1, hazelnut), topping(P2, peanut_butter).
hint3 -->
  kind(P, onion), flavor(P, french_vanilla), size(P, S), {dif(S, small)}.
hint4 -->
  size(P1, large), flavor(P2, amaretto), kind(P3, wheat), topping(P4, egg_bacon),
  {forall(select(X, [joe,P1,P2,P3,P4], Ps), maplist(\=(X), Ps))}.
hint5 -->
  kind(rick, K), {dif(K, blueberry)}, flavor(rick, columbian),
  kind(P, cheddar), flavor(P, amaretto), {P \= walt}.
hint6 -->
  topping(P1, cream_cheese), kind(P2, blueberry), {P1 \= P2}, size(P1, large),
  kind(P, sesame), topping(P, butter), {P \= carlos}.

bagels(Sol):- Sol =
    [[brad,_,_,_,_],
     [walt,_,_,_,_],
     [joe,_,_,_,_],
     [rick,_,_,_,_],
     [carlos,_,_,_,_]],
  phrase((hint1, hint2, hint3, hint4, hint5, hint6), [state(Sol)], _).

Alas, I get too much solutions... maybe there is a bug in my hints' translation, or the all_different should be applied to all attributes as well, as done for hint n.4

?- aggregate(count,S^bagels(S),N).
N = 7.