Minimum number of moves

Question

In this page http://cseweb.ucsd.edu/classes/fa09/cse130/misc/prolog/goat_etc.html it is demonstrated 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 actual solution with this program it is necessary to specify the exact number of moves needed, like this:

?- 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 minimum moves solution without having to specify the number of moves in the above program?

score 2 · Accepted Answer · answered Jul 02 '15 at 04:52

2

length/2 has generative capability, then just avoid specifying the value:

?- length(X,_),solution([w,w,w,w],X).

answered Jul 02 '15 at 04:52

CapelliC

59,646
5
47
90

s(X) for demonstrating iterative deepening. – repeat Jul 04 '15 at 16:56

repeat · Answer 2 · 2015-07-02T11:29:01.710

As we know that there is a finite number of solutions having the same minimum number of steps, we will keep an eye on achieving universal termination.

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, called "soft cut", to commit to the minimum solution length.

A note on portability:

In SWI-Prolog, the construct has the form (*->)/2.
SICStus Prolog offers this feature with predicate if/3. More information is available here.

Sample query:

?- 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 could go about it 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 would still have to commit to the minimum length.

With minlen_solutions/2 we can directly specify a lower-bound for the solution list length 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 the sake of readability, only answer substitutions for S are shown above.

Note that all queries which use minlen_solution/2 universally terminated.

Minimum number of moves

2 Answers2