% Author: Alex Roque
% Assignment #: 3
% Due Date: 10/11/01
% Program Title: Assignment 3 Cannibals and Missionaries
% Program Description: This assignment solves the traditional missionaries and
% Cannibals program, which uses states, succession, and the depth search.
%
% I certify that this is my work and have not consulted with anyone else.
%
%

% The design of a state in this program follows the corresponding notation:
% bank(x,y,z) represents the cannibals and missionaries in a bank at a point
% and time, where x is number of missionaries, y is number of cannibals, and
% z is either 0 for the boat not being in that bank or 1 for the boat being in that bank.



% Our five possible moves. An interesting observation is that by restricting each 
% move to have at least 1 missionary, we can enforce our "Only the missionaries can 
% row" restriction.
move(boat(1,0)).
move(boat(2,0)).
move(boat(1,1)).
move(boat(2,1)).
move(boat(3,0)).

% Here we state the situations we consider safe.

% Here we state that on any side of the river, the cannibals may
% be alone with NO missionaries.
safe(bank(0,_,_)) :- 
	!.
% Here we state that on any side of the river, the missionaries must be greater
% or equal in number than the cannibals.
safe(bank(M,C,_)) :- 
	M >= C.

% If our goal is reached, then print our state and stop.
% This means that there are no people on the left side (0,0,0), and all people are 
% on the right side (3,3,1) plus the boat.
depth(bank(0,0,0),bank(3,3,1)) :-
	write('Everyone is on the right side! Success!'), nl, nl.

% If our goal is not reached, then we apply our depth search. nextMove gets the next
% possible move and instantiates the "newLeft" and "newRight" variables with it.
% writeState outputs the new states, and then depth is recursively called.
depth(Left,Right) :-				
	nextMove(Left,Right,NewLeft,NewRight),	
	writeState(NewLeft,NewRight),		
	depth(NewLeft,NewRight).		

% This predicate makes the next move, by getting a move, making sure that it has
% not been done before, recording it to memory, and checking if the new given
% state is safe.
nextMove(Left,Right,NewLeft,NewRight) :-		
	applyMove(Left,Right,NewLeft,NewRight), 	
	not(known(NewLeft,NewRight)),			
	assert(known(NewLeft,NewRight)),		
	safe(NewLeft), safe(NewRight).		

% Loads a move and moves the boat according to its position.
% If the boat is on the left, then moves it to the right.
applyMove(bank(LeftM,LeftC,1),Right,NewLeft,NewRight) :-
	 moveBoatLoad(bank(LeftM,LeftC,1),Right,NewLeft,NewRight).	

% Loads a move and moves the boat according to its position.
% If the boat is on the right, then moves it to the left.
applyMove(bank(LeftM,LeftC,0),Right,NewLeft,NewRight) :-	
	moveBoatLoad(Right,bank(LeftM,LeftC,0),NewRight,NewLeft).

% Performs the operation that moves the boat, and adds the boat
% passengers to one side, while subtracting from the other.
% move gets a move, applicable enforces requirements, add, subtract perform
% calculations, and writeMove outputs a text description of the move.
moveBoatLoad(Source,Target,NewS,NewT) :-	
	move(BoatLoad),			
	applicable(Source,BoatLoad),	
	subtract(Source,BoatLoad,NewS),	
	add(Target,BoatLoad,NewT),	
	writeMove(BoatLoad).		

% This assures us that the boat is on that side of the bank, and that the people on the
% boat are less than those on the bank (for space purposes, becauase if there is no space
% we cannot apply our five possible moves).
applicable(bank(MS,CS,1), boat(MB,CB)) :-
	MS >= MB, CS >= CB.

% Subtracts the boat from the source and gives back the new total of people on the source
% bank. Also takes away the boat from the source bank.
subtract(bank(OsourceM,OsourceC,1), boat(OboatM,OboatC), bank(SnewM,SnewC,0)) :-
	SnewM is OsourceM-OboatM,
	SnewC is OsourceC-OboatC.

% Adds the boat load to the target and gives back the new total of people on the target
% bank. Also gives the boat to the target bank.
add(bank(OtargetM,OtargetC,0), boat(OboatM,OboatC), bank(SnewM,SnewC,1)) :-
	SnewM is OtargetM+OboatM,
	SnewC is OtargetC+OboatC.

% Our built in NOT negation as failure predicate.
not(P):-
	P,!,fail
	;
	true.

% Output

% Writes all the output information.
writeState(bank(ML,CL,BL), bank(MR,CR,_)) :-
	nl, write('The left bank contains '),
	write(ML), write(' missionaries and '),
	write(CL), write(' cannibals'),
	nl, write('The right bank contains '),
	write(MR), write(' missionaries and '),
	write(CR), write(' cannibals'), nl,
	writeBoatPosition(BL),
	boatPic(BL,Picture),
	write(Picture),nl.

% Write the position of the boat.

writeBoatPosition(1) :-
	write('The boat is on the left bank'), nl.

writeBoatPosition(0) :-
	write('The boat is on the right bank'), nl.

% Writes the move performed.
writeMove(boat(M,C)) :-
	nl, write('Move '), write(M), write(' missionaries and '),
	write(C), write(' cannibals'), nl.

% Boat Diagrams.
boatPic(1,'| \___/                     |').
boatPic(0,'|                     \___/ |').

% The executable.
% Since we will record information to our database using the built-in
% predicate "known", we will want to clean the memory of any "known" with
% an arity of 2 with the "abolish" built in predicate.
% The built-in predicate "assert" will make sure our "known" predicate is 
% recorded to the database. Finally depth provides the search.
go :-						
	abolish(known, 2),		
	assert(known(bank(3,3,1), bank(0,0,0))),
	depth(bank(3,3,1),bank(0,0,0)).