% File : /usr/lib/prolog/teach/mandc/heuristic % Author : Alan Bundy % Updated: 27 May 82 % Purpose: Heuristic Search version of Missionaries and Cannibals. % Modified: For NIP, by elimination of singleton variables % Ken Johnson April 1987 go1 :- /* to solve the m & c problem */ abolish(known, 2), /* clear memory */ assert(known(bank(3,3,1), bank(0,0,0))), /* record initial state */ heuristic([triple(5, bank(3,3,1), bank(0,0,0))]). /* conduct search from it */ /* Agenda is a list of undeveloped states */ heuristic(_) :- known(bank(0,0,0), bank(3,3,1)), !, /* if goal state found */ nl, write('Goal state found'), nl, nl. /* then print message and stop */ heuristic([triple(_,Left,Right) | Rest]) :- /* otherwise */ nl, write('Consider the state in which:'), write_state(Left,Right), /* print state */ successors(Left,Right,Rest,NewAgenda), /* find all successors */ heuristic(NewAgenda). /* and recurse */ successors(Left,Right,OldAgenda,NewAgenda) :- /* to find all successors */ assert(agenda(OldAgenda)), /* initiate agenda record */ keep_trying(Left,Right), /* make all moves */ retract(agenda(NewAgenda)). /* return and delete agenda record */ keep_trying(Left,Right) :- /* to make all moves */ make_move(Left,Right,NewLeft,NewRight), /* make one move */ evaluate(NewLeft,Score), /* evaluate new state */ agenda(Agenda), /* find current agenda record */ insert(Agenda,triple(Score,NewLeft,NewRight),NewAgenda), /* insert it into agenda */ assert(agenda(NewAgenda)), /* record new agenda record */ retract(agenda(Agenda)), /* delete old agenda record */ fail. /* force backtracking to occur */ keep_trying(_,_). /* when no move moves left, then succeed */ /* insert state into agenda */ insert([],Triple,[Triple]). /* if agenda is empty then make this only member */ insert([triple(Score1,Left1,Right1) | Rest], /* otherwise */ triple(Score, Left, Right), /* put state at front */ [triple(Score,Left,Right), triple(Score1,Left1,Right1) | Rest]) :- Score =< Score1, !. /* if its score is less than existing front runner */ insert([X|Rest], Triple, [X|NewRest]) :- /* otherwise */ insert(Rest,Triple,NewRest). /* recurse into agenda */ /* evaluate state */ evaluate(bank(M,C,B), Score) :- Score is M+C-B. /* Add up M and C and subtract B */