Why I can't get an answer for the Ship Puzzle with Prolog?

818 views Asked by At

I need to solve the Ship Puzzle problem with using Prolog. Here are the facts.

There are 5 ships.

  1. The Greek ship leaves at six and carries coffee.
  2. The Ship in the middle has a black chimney.
  3. The English ship leaves at nine.
  4. The French ship with blue chimney is to the left of a ship that carries coffee.
  5. To the right of the ship carrying cocoa is a ship going to Marseille.
  6. The Brazilian ship is heading for Manila.
  7. Next to the ship carrying rice is a ship with a green chimney.
  8. A ship going to Genoa leaves at five.
  9. The Spanish ship leaves at seven and is to the right of the ship going to Marseille.
  10. The ship with a red chimney goes to Hamburg.
  11. Next to the ship leaving at seven is a ship with a white chimney.
  12. The ship on the border carries corn.
  13. The ship with a black chimney leaves at eight.
  14. The ship carrying corn is anchored next to the ship carrying rice.
  15. The ship to Hamburg leaves at six.

Which ship goes to Port Said? Which ship carries tea?

I search internet for answers, but I could not find any. So I refer 'The Zebra Puzzle' and accordingly I arranged the code for this problem. So this is my Prolog code the problem.

exists(A,(A,_,_,_,_)).
exists(A,(_,A,_,_,_)).
exists(A,(_,_,A,_,_)).
exists(A,(_,_,_,A,_)).
exists(A,(_,_,_,_,A)).

rightOf(A,B,(B,A,_,_,_)).
rightOf(A,B,(_,B,A,_,_)).
rightOf(A,B,(_,_,B,A,_)).
rightOf(A,B,(_,_,_,B,A)).

middleShip(A,(_,_,A,_,_)).

lastShip(A,(_,_,_,_,A)).

nextTo(A,B,(B,A,_,_,_)).
nextTo(A,B,(_,B,A,_,_)).
nextTo(A,B,(_,_,B,A,_)).
nextTo(A,B,(_,_,_,B,A)).
nextTo(A,B,(A,B,_,_,_)).
nextTo(A,B,(_,A,B,_,_)).
nextTo(A,B,(_,_,A,B,_)).
nextTo(A,B,(_,_,_,A,B)).

solution(PortSaidShip, TeaCarrier) :-
   Shipes = (ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_)),
   exists(ship('Greek',6,'Coffee',_,_),Shipes),
   middleShip(ship(_,_,_,_,'Black',_),Shipes),
   exists(ship('English',9,_,_,_),Shipes),
   rightOf(ship(_,_,'Coffee',_,_),ship('French',_,_,'Blue',_),Shipes),
   rightOf(ship(_,_,_,_,'Marseille'),ship(_,_,'Cocoa',_,_),Shipes),
   exists(ship('Brazilian',_,_,_,'Manila'),Shipes),
   nextTo(ship(_,_,_,'Green',_),ship(_,_,'Rice',_,_),Shipes),
   exists(ship(_,5,_,_,'Genoa'),Shipes),
   rightOf(ship('Spanish',7,_,_,_),ship(_,_,_,_,'Marseille'),Shipes),
   exists(ship(_,_,_,'Red','Hamburg'),Shipes),
   nextTo(ship(_,_,_,'White',_),ship(_,7,_,_,_),Shipes),
   lastShip(ship(_,_,'Corn',_,_),Shipes),
   exists(ship(_,8,_,'Black',_),Shipes),
   nextTo(ship(_,_,'Corn',_,_),ship(_,_,'Rice',_,_),Shipes),
   exists(ship(_,6,_,_,'Hamburg'),Shipes),
   exists(ship(PortSaidShip,_,_,_,'Port Said'),Shipes),
   exists(ship(TeaCarrier,_,'Tea',_,_),Shipes).

But when I run the program it will say 'false'.
So how can I solve this?
thank you

2

There are 2 answers

3
false On BEST ANSWER

You asked:

So how can I solve this?

The following is a general methodology, that always works for pure, monotonic Prolog programs like yours. Your actual problem is that a specific goal should succeed, but it fails. So you got an unexpected failure. To localize the responsible part of your program, we will now systematically generalize your program. Step by step. Until we have a tiny little program fragment. This technique is called sometimes program slicing and sometimes program modification.

First of all, add the following to your code:

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

:- initialization(solution(_Port, _Carrier)).

Now we will remove one goal after the other by adding a * in front of it and then rerun your program. So be prepared that you will rerun your program for a couple of times. To load the program enter at the toplevel:

?- [shipes].

This works virtually everywhere, like in SICStus, GNU, SWI, YAP. You will get now a warning about a "failed directive" or similar. So - be happy - for you can now reproduce the problem with ease!

Start adding a * at the last goal. You might try several at once. To reload after modification you might reenter that goal, or

  • in SICStus, better state ensure_loaded(shipes). This checks if the file has been modified and only reruns it if it has been reloaded

  • in SWI, enter make.

Finally, I got the following program fragment:

middleShip(A,(_,_,A,_,_)).

solution(PortSaidShip, TeaCarrier) :-
   Shipes = (ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_),ship(_,_,_,_,_)),
   * exists(ship('Greek',6,'Coffee',_,_),Shipes),
   middleShip(ship(_,_,_,_,'Black',_),Shipes),
   * exists(ship('English',9,_,_,_),Shipes),
   * rightOf(ship(_,_,'Coffee',_,_),ship('French',_,_,'Blue',_),Shipes),
   * rightOf(ship(_,_,_,_,'Marseille'),ship(_,_,'Cocoa',_,_),Shipes),
   * exists(ship('Brazilian',_,_,_,'Manila'),Shipes),
   * nextTo(ship(_,_,_,'Green',_),ship(_,_,'Rice',_,_),Shipes),
   * exists(ship(_,5,_,_,'Genoa'),Shipes),
   * rightOf(ship('Spanish',7,_,_,_),ship(_,_,_,_,'Marseille'),Shipes),
   * exists(ship(_,_,_,'Red','Hamburg'),Shipes),
   * nextTo(ship(_,_,_,'White',_),ship(_,7,_,_,_),Shipes),
   * lastShip(ship(_,_,'Corn',_,_),Shipes),
   * exists(ship(_,8,_,'Black',_),Shipes),
   * nextTo(ship(_,_,'Corn',_,_),ship(_,_,'Rice',_,_),Shipes),
   * exists(ship(_,6,_,_,'Hamburg'),Shipes),
   * exists(ship(PortSaidShip,_,_,_,'Port Said'),Shipes),
   * exists(ship(TeaCarrier,_,'Tea',_,_),Shipes).

So you need to understand four lines of code to understand your problem!

As others have already indicated, the problem is that once you use ship/6 and in other situations ship/5.

Another remark: In stead of (_,_,_,A,B) better write [_,_,_,A,B] which is the common list notation.

1
fferri On

The number of arguments to the term ship(...) in the second line (after solution predicate) is wrong. It is:

middleShip(ship(_,_,_,_,'Black',_),Shipes),

while it should be:

middleShip(ship(_,_,_,'Black',_),Shipes),

I haven't checked if this works, but this is causing your solver to fail for sure.