Minimum number of moves
This page http://cseweb.ucsd.edu/classes/fa09/cse130/misc/prolog/goat_etc.html demonstrates how to solve the popular wolf, goat and cabbage puzzle.
change(e,w).
change(w,e).
move([X, X,Goat,Cabbage], wolf,[Y, Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf, X,Cabbage], goat,[Y,Wolf, Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat, X],cabbage,[Y,Wolf,Goat, Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).
oneEq(X,X,_).
oneEq(X,_,X).
safe([Man,Wolf,Goat,Cabbage]) :-
oneEq(Man,Goat, Wolf),
oneEq(Man,Goat,Cabbage).
solution([e,e,e,e],[]).
solution(Config,[FirstMove|OtherMoves]) :-
move(Config,FirstMove,NextConfig),
safe(NextConfig),
solution(NextConfig,OtherMoves).
But in order to find an up-to-date solution with this program, it is necessary to indicate the exact number of required moves, for example:
?- length(X,7), solution([w,w,w,w],X). X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ; false.
Is there a standard way to find a solution with minimum moves without specifying the number of moves in the above program?
source to share
As we know, there are a finite number of solutions that have the same minimum number of steps, we will monitor the achievement of universal completion.
minlen_solution(Xs,S) :-
( setof(t,solution([w,w,w,w],Xs),_) % eliminate redundant answers
*-> Xs = S
; minlen_solution([_|Xs],S) % no solution? try bigger length
).
minlen_solution/2
uses (*->)/2
what is called "soft cut" to fix the minimum solution length.
Portability note:
- In SWI-Prolog, the construction is
(*->)/2
. - SICStus Prolog offers this function with a predicate
if/3
. More information is available here .
Request example:
?- minlen_solution([],Xs).
Xs = [goat,nothing,cabbage,goat, wolf,nothing,goat]
; Xs = [goat,nothing, wolf,goat,cabbage,nothing,goat].
If we wanted to find all solutions of length greater than or equal to 8, we can go something like this:
?- length(Xs,8), solution([w,w,w,w],Xs). % try length = 8
false. % no solutions!
?- length(Xs,9), solution([w,w,w,w],Xs). % try length = 9
...
However, we still have to fix the minimum length.
With, minlen_solutions/2
we can directly specify the lower bound on the length of the decision list like so:
?- length(Xs,8),minlen_solution(Xs,S).
S = [goat, goat, goat,nothing,cabbage, goat, wolf,nothing,goat]
; S = [goat, goat, goat,nothing, wolf, goat,cabbage,nothing,goat]
; S = [goat,nothing,cabbage,cabbage,cabbage, goat, wolf,nothing,goat]
; S = [goat,nothing,cabbage,cabbage, wolf, goat,cabbage,nothing,goat]
; S = [goat,nothing,cabbage, goat, goat, goat, wolf,nothing,goat]
; S = [goat,nothing,cabbage, goat, wolf,cabbage,cabbage,nothing,goat]
; S = [goat,nothing,cabbage, goat, wolf,nothing, goat, goat,goat]
; S = [goat,nothing,cabbage, goat, wolf,nothing,nothing,nothing,goat]
; S = [goat,nothing,cabbage, goat, wolf, wolf, wolf,nothing,goat]
; S = [goat,nothing,nothing,nothing,cabbage, goat, wolf,nothing,goat]
; S = [goat,nothing,nothing,nothing, wolf, goat,cabbage,nothing,goat]
; S = [goat,nothing, wolf, goat,cabbage,cabbage,cabbage,nothing,goat]
; S = [goat,nothing, wolf, goat,cabbage,nothing, goat, goat,goat]
; S = [goat,nothing, wolf, goat,cabbage,nothing,nothing,nothing,goat]
; S = [goat,nothing, wolf, goat,cabbage, wolf, wolf,nothing,goat]
; S = [goat,nothing, wolf, goat, goat, goat,cabbage,nothing,goat]
; S = [goat,nothing, wolf, wolf,cabbage, goat, wolf,nothing,goat]
; S = [goat,nothing, wolf, wolf, wolf, goat,cabbage,nothing,goat].
For readability, only the response expressions for S
are shown above.
Please note that all queries that use minlen_solution/2
universally complete.
source to share