Prolog道路交叉口

Question

如何在Prolog中实现此问题的解决方案？

路的西侧有3只狗和3只猫。如果在任何时候，一边的狗比猫多(除了0只猫)，狗就会吃掉猫。如果你一次只能携带两只动物横过马路，而且你不能空手横渡，你怎么才能把所有的动物安全地送到东边(最短的路)？

狗是可以互换的，猫也是一样的。

Answer 1

% state(person on side, animals west, animals east)
initial_state(state(west, cats_dogs(3, 3), cats_dogs(0, 0))).
desired_state(state(east, cats_dogs(0, 0), cats_dogs(3, 3))).

solve(Path) :-
    initial_state(Initial),
    desired_state(Desired),
    % Use iterative deepening for convenience, so no need to guard against circular states
    length(Path, _),
    path(Initial, Desired, Path).

path(Desired, Desired, []).
path(Initial, Desired, [State1|Path]) :-
    move(Initial, State1),
    path(State1, Desired, Path).

road_side(west).
road_side(east).

% Map east & west onto this and other sides
cats_dogs_side(west, W, E, W, E).
cats_dogs_side(east, W, E, E, W).

move(Initial, State1) :-
    Initial = state(HumanSide, West, East),
    % Change from west & east to this and other, in terms of sides
    cats_dogs_side(HumanSide, West, East, This, Other),
    cats_dogs_move(This, Other, This1, Other1),
    % Human moves to other side
    dif(HumanSide, HumanSide1),
    road_side(HumanSide1),
    % Change back to west & east sides, for state-representation consistency
    cats_dogs_side(HumanSide, This1, Other1, West1, East1),
    State1 = state(HumanSide1, West1, East1).

cats_dogs_move(This, Other, This1, Other1) :-
    between(1, 2, AnimalsToMove),
    between(0, AnimalsToMove, CatsToMove),
    DogsToMove is AnimalsToMove - CatsToMove,
    move_safe(This, Other, CatsToMove, DogsToMove, This1, Other1).

move_safe(This, Other, CatsToMove, DogsToMove, This1, Other1) :-
    shift_animals(-1, CatsToMove, DogsToMove, This, This1),
    shift_animals(1, CatsToMove, DogsToMove, Other, Other1),
    safe_cats_dogs(This1),
    safe_cats_dogs(Other1).

shift_animals(Sign, CatsToMove, DogsToMove, cats_dogs(Cats, Dogs), cats_dogs(Cats1, Dogs1)) :-
    Cats1 is Cats + (Sign * CatsToMove),
    Cats1 >= 0,
    Dogs1 is Dogs + (Sign * DogsToMove),
    Dogs1 >= 0.

% Check that side is safe
safe_cats_dogs(cats_dogs(Cats, Dogs)) :-
    (   Dogs > Cats,
        Cats > 0
    ->  false
    ;   true ).

结果在swi-prolog (前2)：

?- time(solve(Path)).
% 2,287,324 inferences, 0.245 CPU in 0.242 seconds (101% CPU, 9329359 Lips)
Path = [state(east,cats_dogs(3,1),cats_dogs(0,2)),state(west,cats_dogs(3,2),cats_dogs(0,1)),state(east,cats_dogs(3,0),cats_dogs(0,3)),state(west,cats_dogs(3,1),cats_dogs(0,2)),state(east,cats_dogs(1,1),cats_dogs(2,2)),state(west,cats_dogs(2,2),cats_dogs(1,1)),state(east,cats_dogs(0,2),cats_dogs(3,1)),state(west,cats_dogs(0,3),cats_dogs(3,0)),state(east,cats_dogs(0,1),cats_dogs(3,2)),state(west,cats_dogs(0,2),cats_dogs(3,1)),state(east,cats_dogs(0,0),cats_dogs(3,3))] ;
% 328 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 1197565 Lips)
Path = [state(east,cats_dogs(3,1),cats_dogs(0,2)),state(west,cats_dogs(3,2),cats_dogs(0,1)),state(east,cats_dogs(3,0),cats_dogs(0,3)),state(west,cats_dogs(3,1),cats_dogs(0,2)),state(east,cats_dogs(1,1),cats_dogs(2,2)),state(west,cats_dogs(2,2),cats_dogs(1,1)),state(east,cats_dogs(0,2),cats_dogs(3,1)),state(west,cats_dogs(0,3),cats_dogs(3,0)),state(east,cats_dogs(0,1),cats_dogs(3,2)),state(west,cats_dogs(1,1),cats_dogs(2,2)),state(east,cats_dogs(0,0),cats_dogs(3,3))] ;