riverastar.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 A* search to find the optimal solution
%

% 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, Path):-
        astar([astate(State, [], 0)], Path).
% A* search, each candidate is in form of astate(State, ReversedPath, EstimatedValue)
astar([astate(state(right, right, right, right), ReversedPath, _)|_], Path):-
        reverse(ReversedPath, Path), !.
astar([astate(State, ReversedPath, _)|CandidatesT], Path):-
        findall(astate2(NextState, [Item|ReversedPath]), canBring(Item, State, NextState), States),
        insertCandidates(CandidatesT, States, NewCandidates),
        astar(NewCandidates, Path).

% Calculate the estimate cost and inseart Candidate to candidate list in order
insertCandidates(Candidates, [], Candidates):- !.
insertCandidates(Candidates, [astate2(State, ReversedPath)|StatesT], Result):-
        heuristic(State, Heuristic),         % h(state)
        length(ReversedPath, CurrentCost),   % g(state)
        Estimate is CurrentCost + Heuristic, % f(state) = g(state) + h(state)
        insert(Candidates, astate(State, ReversedPath, Estimate), NewCandidates),
        insertCandidates(NewCandidates, StatesT, Result).

% Really inseart Candidate to candidate list 
insert([astate(Board1, Path1, Estimate1)|CandidatesT], astate(Board2, Path2, Estimate2), Result):-
        Estimate2 > Estimate1,
        insert(CandidatesT, astate(Board2, Path2, Estimate2), NewCandidates),
        Result = [astate(Board1, Path1, Estimate1)|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).