Japanese version of the Wolf, Goat and Cabbage puzzle in the prologue

This puzzle is already familiar to Habrahabru from this publication.

The essence of the puzzle is as follows (quoting bor1s ):

It is necessary to transport a family of six people and a policeman with a gangster to the other side of the river on a raft. However, at the same time only two people are placed on the raft (clarification: one of whom must be an adult), the mother, left without a father, beats the boys, the father - the girls. A gangster (clarification: in the absence of a police officer) just wets everyone.

You can complete the online puzzle at: http://freeweb.siol.net/danej/riverIQGame.swf .

The prologue usually copes well with such problems, which I decided to make sure ...
')

son (son1).
son (son2).

daughter (daughter1).
daughter (daughter2).

adult (father).
adult (mother).
adult (police).

notsafe_ (criminal, X ): - X \ = police .
notsafe_ (mother, Y ): - son ( Y ).
notsafe_ (father, Y ): - daughter ( Y ).

notsafe ( X , Y ): - notsafe_ ( X , Y ); notsafe_ ( y , x ).

safe ( X , Y ): - \ + notsafe ( X , Y ).

safebridge ([ X , Y ]): - ( adult ( X ); adult ( Y )), safe ( X , Y ) ,! .
safebridge ([ X ]): - adult ( X ).

all ([
son1, son2, father,
daughter1, daughter2, mother,
criminal, police
]).

allsafe ( L ): -
forall ( member ( H , L ),
( adult ( H )
; son ( H ),
( member (mother, L )
-> member (father, L )
; true
)
; daughter ( H ),
( member (father, L )
-> member (mother, L )
; true
)
; H = criminal, member (police, L )
)) ! .
allsafe ([_]).
allsafe ([]).

allPairs ([ H | T ], [ H , P2 ]): -
member ( P2 , T ).

allPairs ([_ | T ], P ): -
allPairs ( T , P ).

step_ ( state ( Left1 , left), state ( Left2 , right)): -
( allPairs ( Left1 , OnBridge )
; member ( A , Left1 ),
OnBridge = [ A ]
),

safebridge ( OnBridge ),

subtract ( Left1 , OnBridge , Left2 ),
allsafe ( Left2 ),

all ( All ),
subtract ( All , Left2 , Right ),
allsafe ( Right ).

step ( state ( Left1 , left), state ( Left2 , right)): -
step_ ( state ( Left1 , left), state ( Left2 , right)).

step ( state ( Left1 , right), state ( Left2 , left)): -
all ( All ),
subtract ( All , Left1 , Right1 ),
step_ ( state ( Right1 , left), state ( Right2 , right)),
subtract ( All , Right2 , Left2 ).

notequal ( state ( L1 , P1 ), state ( L2 , P2 )): -
\ + (
P1 = P2 ,
sort ( L1 , L ),
sort ( L2 , L )
).
solve ( Inp , Outp , PrevSteps , [ Step | Steps ]): -
Step = step ( Inp , S1 ),
Step , forall ( member ( step ( State1 , _), PrevSteps ), notequal ( State1 , S1 )), % to prevent loops

( S1 = Outp
-> Steps = []
; solve ( S1 , Outp , [ Step | PrevSteps ], Steps )
).

solve : -
all ( All ),
findall ( Steps , solve ( state ( All , left), state ([], _), [], Steps ), Solutions ),
length ( Solutions , SolLength ),
format ( 'Found ~ w solutions: ~ n' , [ SolLength ]),
forall ( member ( Solution , Solutions ),
( format ( '~ nSolution: ~ n' ),
forall ( member ( Step , Solution ),
printStep ( Step )
)
)).

printStep ( step ( state ( L1 , Pos1 ), state ( L2 , _))): -
( Pos1 = left
-> subtract ( L1 , L2 , Moved ),
format ( '~ w -> left: ~ w ~ n' , [ Moved , L2 ])
; Pos1 = right
-> subtract ( L2 , L1 , Moved ),
format ( '~ w <- left: ~ w ~ n' , [ Moved , L2 ])
).

The program very quickly finds and displays 8 options for crossing the river.

Chewing the work of the program is not much hunting, but the algorithm can be briefly described as follows. The system state is defined as state (L, Pos), where L is the list of people on the left side of the bridge, and Pos is the location of the raft (left, right).
The program describes the predicate step (S1, S2) which describes the possible changes in the state of the system. To solve the problem, there is a solve predicate, which can be simplifiedly written as

solve(S1, S2) :-
step(S1, S), %
( S = S2 % ,
; solve(S, S2) % ,
).


This predicate, using the selectable nature of the prologue, makes possible (in the described constraints given at the beginning of the program) steps until it reaches the final state state ([], _) (there is no one left). However, the predicate had to introduce a check that we did not fall into the already passed state, otherwise the program would obviously loop.

Admire the options for solving the puzzle in Haskell, J, Ruby can be on the forum RSDN . Also, if interested, I propose to write a solution on your favorite PL.

Addition. On solving another problem, too, to cross the river (Escape from Zurg) can be read here . The article tells that Haskell is also quite convenient for solving search problems, along with the traditional Prolog in this area. I posted my solution to this problem (a little more complicated than in the article) on the prologue here .