mandc(Start, Sol):- mandc(Start, [Start], Sol).


mandc(state(0, 0, boat_right), _, []).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
        newstate(CurrentState, NextState),
        not(member(NextState, Visited)),
        make_move(CurrentState, NextState, Move),
        mandc(NextState, [NextState | Visited], RestOfMoves).

make_move(state(M1, C1, boat_left), state(M2, C2, boat_right), move(M, C, right)) :-
        M is M1 - M2,
        C is C1 - C2.
make_move(state(M1, C1, boat_right), state(M2, C2, boat_left), move(M, C, left)) :-
        M is M2 - M1,
        C is C2 - C1.
        
newstate(state(M1, C1, boat_left), state(M2, C2, boat_right)) :-
        carry(M, C),
        M =< M1,
        C =< C1,
        M2 is M1 - M,
        C2 is C1 - C,
        legal(M2, C2).
        
newstate(state(M1, C1, boat_right), state(M2, C2, boat_left)) :-
        carry(M, C),
        M2 is M1 + M,
        C2 is C1 + C,
        M2 =< 3,
        C2 =< 3,
        legal(M2, C2).
        
carry(2, 0).
carry(1, 0).
carry(1, 1).
carry(0, 1).
carry(0, 2).

legal(X, X).
legal(3, _).
legal(0, _).