riverhistory.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)
%
% This example uses state History to avoid repeated state
%

% 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):-
	canBring(Item, State, NewState),
	\+ member(NewState, History),
	solve(NewState, Path, [State|History]).

% 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).