%   File   : /usr/lib/prolog/teach/mandc/breadth1
%   Author : Alan Bundy
%   Updated: 24 June 82
%   Purpose: Breadth First Search version of Missionaries and Cannibals,
%	     Revised version.
%   Mod	   : Elimination of singleton variables for NIP
%          : Ken Johnson, April 1987

go2 :-					/* to solve the m & c problem */
	abolish(state, 3),		/* clear memory */
	assert(state(0,bank(3,3,1), bank(0,0,0))),	/* record initial state */
	breadth(0).			/* conduct search from it */


/* to develop breadth first search */
breadth(_) :-
	state(_,bank(0,0,0), bank(3,3,1)), !,		/* if goal state found */
	nl, write('Goal state found'), nl, nl.		/* print message and stop */

breadth(Depth) :-			/* otherwise */
	NewDepth is Depth+1,		/* increment depth */
	state(Depth,Left,Right),	/* pick a state at correct depth */
	nl, write('Consider the state in which:'),
	write_state(Left,Right),	/* print state */
	make_move(Left,Right,NewDepth,_,_),	/*make one move */
	fail.				/* force backtracking to occur */

breadth(Depth) :-			/* when old depth is exhausted */
	NewDepth is Depth+1,		/* increment depth */
	breadth(NewDepth).		/* recurse at new depth */

make_move(Left,Right,NewDepth,NewLeft,NewRight) :-	/* to make a move */
	apply_move(Left,Right,NewLeft,NewRight), 	/* apply a move */
	legal(NewLeft), legal(NewRight),		/* check it is legal */
	\+ state(_,NewLeft,NewRight),			/* and a new state */
	assert(state(NewDepth,NewLeft,NewRight)).	/* record it */