% Initial goal % Move 3 cannibals and 3 priests to the other bank solve :- move(3, 3, 0, 0, 0, 0, 6). % Valid configurations for boat occupants boat(0, 1). boat(1, 0). boat(1, 1). boat(0, 2). boat(2, 0). % Cross from the initial bank to the other cross(0, 0, Cannibals2, Priests2, A, B) :- A is 0, B is 0. cross(Cannibals1, Priests1, Cannibals2, Priests2, A, B) :- boat(A, B), A =< Cannibals1, B =< Priests1, ((Priests1 - B) =:= 0 | (Priests1 - B) >= (Cannibals1 - A)), ((Priests2 + B) =:= 0 | (Priests2 + B) >= (Cannibals2 + A)). % Cross back to the initial bank cross-back(0, 0, Cannibals2, Priests2, C, D) :- C is 0, D is 0. cross-back(Cannibals1, Priests1, Cannibals2, Priests2, C, D) :- boat(C, D), C =< Cannibals2, D =< Priests2, ((Priests2 - D) =:= 0 | (Priests2 - D) >= (Cannibals2 - C)), ((Priests1 + D) =:= 0 | (Priests1 + D) >= (Cannibals1 + C)). % The move predicate calculates one round trip move(0, 0, Cannibals2, Priests2, PrevCannibals, PrevPriests, PrevMax). move(Cannibals1, Priests1, Cannibals2, Priests2, PrevCannibals, PrevPriests, PrevMax) :- % cross one-way cross(Cannibals1, Priests1, Cannibals2, Priests2, A, B), Cannibals11 is Cannibals1 - A, Cannibals22 is Cannibals2 + A, Priests11 is Priests1 - B, Priests22 is Priests2 + B, % cross-back cross-back(Cannibals11, Priests11, Cannibals22, Priests22, C, D), Cannibals111 is Cannibals11 + C, Cannibals222 is Cannibals22 - C, Priests111 is Priests11 + D, Priests222 is Priests22 - D, % Conditions that guarantee progress NewMax is Cannibals111 + Priests111, (NewMax =< PrevMax), (PrevCannibals =\= A | PrevPriests =\= B), (A =\= C | B =\= D), % output round trip info write(A), write(' cannibals and '), write(B), write(' priests crossed the river '), write(C), write(' cannibals and '), write(D), write(' priests crossed back '), % recursion move(Cannibals111, Priests111, Cannibals222, Priests222, C, D, NewMax).