Japanese version of the puzzle "Wolf, goat and cabbage" on the prologue

    This puzzle is already familiar to Habrahabr in this publication.

    The essence of the puzzle is as follows (quoting bor1s ):
    It is necessary to transport a family of six and a policeman with a bandit 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 which must be an adult), mother, left without a dad, beats up boys, dad - girls. And the bandit (clarification: in the absence of a policeman) simply wets everyone.

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

    The prologue usually does a good job of solving 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 a big deal, but the algorithm can be briefly described as follows. We set the state of the system in the form state (L, Pos), where L is the list of people on the left side of the bridge, and Pos is the raft location (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 predicate solve, which can be simplified as

    solve(S1, S2) :-
    step(S1, S), % делаем шаг
    ( S = S2 % если конечное состояние достигнуто, то решение найдено
    ; solve(S, S2) % иначе, решаем дальше
    ).


    Using the enumerated nature of the prologue, this predicate makes possible (in the described restrictions given at the beginning of the program) steps until it reaches the final state ([], _) state (no one is left). However, we had to introduce a check into the predicate that we did not end up in an already passed state, otherwise the program will obviously go in cycles.

    You can admire the options for solving the puzzle in Haskell, J, Ruby on the RSDN forum . Also, if interested, I suggest writing a solution in your favorite YP.

    Addition. You can read about solving another problem on crossing the river (Escape from Zurg) here. The article talks about the fact that Haskell is also quite convenient for solving search problems, along with the traditional Prolog in this area. I placed my solution to this problem (a little more complicated than in the article) on the prologue here .

    Also popular now: