riverbfs.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)/ReversedPath|_], ReturnPath):-
	reverse(ReversedPath, ReturnPath).
solve([State/Path|QueueTail], ReturnPath) :-
	findall(NewState/[Item|Path], canBring(Item, State, NewState), NextStates),
	append(QueueTail, NextStates, NewQueue),
	solve(NewQueue, ReturnPath).

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