riverbest.pl

人携带狐狸

% The problem:
%   A man needs to cross the river with a fox, a goose and a bag of beans.
%   Each time the man can only bring one of them across the river.
%   Without the man, the fox will eat the goose, the goose will eat the beans.
%
% States:
%   Format: state(FoxPos, GoosePos, BeansPos, ManPos)
%   Initial: state(left, left, left, left)
%   Goal: state(right, right,right, right)
%
%

% Define movement
move(left, right).
move(right, left).

% Valid states
validState(state(_, GoosePos, _, ManPos)):-
	ManPos = GoosePos, !.
validState(state(FoxPos, GoosePos, BeansPos, _)):-
	FoxPos \= GoosePos,
	BeansPos \= GoosePos.

% Can the man bring something to the other side?
canBring(nothing,
	 state(FoxPos, GoosePos, BeansPos, ManPos), 
         state(FoxPos, GoosePos, BeansPos, NewManPos)):-
	move(ManPos, NewManPos),
	validState(state(FoxPos, GoosePos, BeansPos, NewManPos)).
canBring(fox,
	 state(ManPos, GoosePos, BeansPos, ManPos),
	 state(NewManPos, GoosePos, BeansPos, NewManPos)):-
	move(ManPos, NewManPos),
	validState(state(NewManPos, GoosePos, BeansPos, NewManPos)).
canBring(goose, 
	 state(FoxPos, ManPos, BeansPos, ManPos), 
	 state(FoxPos, NewManPos, BeansPos, NewManPos)):-
	move(ManPos, NewManPos),
	validState(state(FoxPos, NewManPos, BeansPos, NewManPos)).
canBring(beans, 
	 state(FoxPos, GoosePos, ManPos, ManPos), 
	 state(FoxPos, GoosePos, NewManPos, NewManPos)):-
	move(ManPos, NewManPos),
	validState(state(FoxPos, GoosePos, NewManPos, NewManPos)).

% Find the path to goal.
solve(state(right, right, right, right), [], _).
solve(State, [Item|Path], History):-
	findall(NewState/Item, canBring(Item, State, NewState), NextStates),
	insertCandidates([], NextStates, OrderedNextStates),
	member(node(BestState,Item,_), OrderedNextStates),
	\+member(BestState, History),
	solve(BestState, Path, [State|History]).
    
% Calculate the estimate cost and inseart Candidate to candidate list in order
insertCandidates(Candidates, [], Candidates):- !.
insertCandidates(Candidates, [State/Item|StatesT], Result):-
	heuristic(State, Heuristic),
	insert(Candidates, node(State,Item,Heuristic), NewCandidates),
	insertCandidates(NewCandidates, StatesT, Result).

% Really inseart Candidate to candidate list 
insert([node(Board1,Item1,Heuristic1)|CandidatesT], node(Board2,Item2,Heuristic2), Result):-
	Heuristic2 > Heuristic1,
	insert(CandidatesT, node(Board2,Item2,Heuristic2), NewCandidates),
	Result = [node(Board1,Item1,Heuristic1)|NewCandidates], !.
insert(Candidates, State, [State|Candidates]).

% The heuristic
heuristic(state(Fox,Goose,Beans,Man), Heuristic):-
	countLeft([Fox,Goose,Beans,Man], Heuristic).
    
countLeft([], 0).
countLeft([left|T], Count):- 
	countLeft(T, Count2),
	Count is Count2 + 1.
countLeft([right|T], Count):-
	countLeft(T, Count).
    
    
% entry point
solvePuzzle:-
	solve(state(left,left,left,left), Path, []), 
	!,  
	printPath(Path, left).

printPath([], _).
printPath([Item|Path], Position) :-
	writef('bring %w to the %w\n', [Item, Position]),
	move(Position, NewPosition),
	printPath(Path, NewPosition).