2

I am trying to solve the 'missionaries and cannibals' problem using Prolog, in which you have an input number of missionaries and cannibals on one side of an island, and they have to all cross to the other side in a boat that has a specified maximum capacity, with the constraint of:

  1. On either side of the island, and in the boat, cannibals cannot outnumber missionaries.

  2. There has to be at least one person in the boat.

I have attempted to achieve this with the following code:

    % M = number of missionaries
    % C = number of cannibals

    % AM = number of missionaries on left island
    % BM = number of missionaries on right island

    % AC = number of cannibals on left island
    % BC = number of cannibals on right island

    % B = 1 if boat is on left island, -1 if boat is on right island
    % L = list of previous states / moves
    % K = maximum capacity of boat

Key above for all variables that follow:

    checkIsland(M,C) :- C =< M.

    checkState(AM, AC, BM, BC) :-
        checkIsland(AM, AC),
        checkIsland(BM, BC).

    checkMove(AM,AC,BM,BC,B,L):-
        checkState(AM,AC,BM,BC),
        not(member([AM,AC,BM,BC,B],L)).

    checkBoat(M,C,K) :-
        C =< M,
        (M + C) =< K,
        (M + C) >= 1.

    state(_,0,0,_,_,-1,_).
    state(K,AM,AC,BM,BC,B,L) :-
        % checkMove(NewAM, NewAC, NewBM, NewBM, NewB, L),
        abs((NewAM - NewBM), FinalM),
        abs((NewAC - NewBC), FinalC),           
        checkBoat(FinalM, FinalC),
        append([AM,AC,BM,BC,B], L, NewL),
        state(K,NewAM, NewAC,NewBM,NewBC,NewB,NewL).

I think I am fairly close, with the main (only?) issue being with the state function, as I don't understand how you are supposed to generate the possible moves / actually make a move. Could someone please advise.

I am trying to solve it specifically using the functions above as it's a past exam paper question.

Edit:

To clarify the purpose of the state/7 predicate, it's used to find and output a list of all the states that occur through the solving process. For example.

If you call state(2,2,1,0,0,1,[]) (which says that there's a boat of capacity two on the left island, and that there are two missionaries and one cannibal on the left island, and zero missionaries and zero cannibals on the right island), then printing out the result of L may end up giving:

2, 1, 0, 0, 1    % The initially input state
1, 0, 1, 1, -1   % 1 missionary, 1 cannibal and the boat move to the right island
1, 1, 1, 0, 1    % 1 cannibal and the boat move to the left island
0, 0, 2, 1, -1   % 1 missionary, 1 cannibal and the boat move to the right island,
                   and the goal is met
  • This is a common Prolog problem and has been asked about [before](https://stackoverflow.com/search?q=%5Bprolog%5D+cannibals+is%3Aquestion) – Guy Coder Jan 05 '19 at 16:25
  • 1
    I am trying to specifically use and understand how to approach the problem with the functions I posted, as it is from a past exam paper with a similar one being asked every year. The BFS answer is not what I'm looking for. –  Jan 05 '19 at 16:30
  • Of interest: [Missionaries and cannibals problem in Picat.](http://picat-lang.org/planner/missionaries_and_cannibals.pi) – Guy Coder Jan 05 '19 at 16:35
  • A common mistake is expressions like `(M + C) =< K,`. Prolog does *not* attach semantics to operators. `M + C` is just `M + C` (or more canonical `+(M, C)`, the fact that `+/2`, so it does not *add* the two numbers together). You need the `is/2` predicate to *evaluate* expression trees. – Willem Van Onsem Jan 05 '19 at 16:45
  • 1
    @WillemVanOnsem realise that's the case for `=`, but are you sure it's the case for comparison operators? Because if you write `5 + 1 > 6` in SWI you get `false`, but if you write `5 + 2 > 6` in SWI it returns `true`. –  Jan 05 '19 at 16:48
  • 2
    @WillemVanOnsem actually, `=2` is a Prolog operator that will evaluate arithmetic expressions. So `(M + C) =< K` is valid. The numeric comparative operators all work this way. – lurker Jan 05 '19 at 16:56
  • 1
    @Lana: ah yes, that's true. Somehow I didn't think of that :) – Willem Van Onsem Jan 05 '19 at 17:07
  • 1
    You're calling `checkBoat(FinalM, FinalC)` with two arguments, but it's defined with three arguments. – lurker Jan 06 '19 at 01:33
  • @lurker Well spotted, thanks, although it still doesn't work for checking different combinations / solving the problem. –  Jan 06 '19 at 02:04
  • What does the predicate `state/7` mean? What is the relation it describes about its arguments? (You should add that information to your question.) – lurker Jan 06 '19 at 02:09
  • `state/7` should probably be called `solve/7` as it's just used to find and output a list of all the states throughout the solving process (so the initially input state when all the missionaries and cannibals are on the left island, to when all the missionaries and cannibals are on the right island). Please see updated question. –  Jan 06 '19 at 03:50

0 Answers0