xonix 14 фев 2009 в 22:43

Японская версия головоломки «Волк, коза и капуста» на прологе

3 мин

6.5K

Эта головоломка уже знакома Хабрахабру по этой публикации.

Суть головоломки в следующем (цитируя bor1s):

Нужно перевезти семью из шести человек и полицейского с бандитом на другой берег реки на плоту. Однако одновременно на плот помещаются только два человека (уточнение: один из которых должен быть взрослым), мама, оставшись без папы, избивает мальчиков, папа — девочек. А бандит (уточнение: в отсутствие полицейского) просто мочит всех.

Пройти головоломку online можно по ссылке: http://freeweb.siol.net/danej/riverIQGame.swf.

Пролог обычно хорошо справляется с решением таких задач, в чем я и решил убедиться…

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])
    ).

Программа очень быстро находит и выводит 8 вариантов перехода через реку.

Разжевывать работу программы сильно не охота, но алгоритм вкратце можно описать следующим образом. Состояние системы зададим в виде state(L, Pos), где L — список людей с левой стороны моста, а Pos — местоположение плота (left, right).
В программе описан предикат step(S1, S2) который описывает возможные изменения состояния системы. Для решения проблемы присутствует предикат solve, который упрощенно можно записать как

solve(S1, S2) :-

 step(S1, S), % делаем шаг

 ( S = S2 % если конечное состояние достигнуто, то решение найдено

 ; solve(S, S2) % иначе, решаем дальше

 ).

Этот предикат, используя переборную природу пролога делает возможные (в описанных ограничениях, приведенных в начале программы) шаги, пока не достигнет конечного состояния state([], _) (слева никого не осталось). Впрочем, в предикат пришлось ввести проверку на то, что мы не попали в уже пройденное состояние, иначе программа, очевидным образом, зациклится.

Полюбоваться на варианты решения головоломки на Haskell, J, Ruby можно на форуме RSDN. Так же, если интересно, предлагаю написать решение на вашем любимом ЯП.

Дополнение. О решении другой задачки тоже на переход через реку (Побег от Зурга) можно почитать здесь. Статья рассказывает о том, что Haskell тоже довольно удобен для решения поисковых задач, наравне с традиционным в этой области Prolog'ом. Свое решение этой задачки (чуть сложнее чем в статье) на прологе я разместил здесь.

Теги:

Хабы:

Prolog

Японская версия головоломки «Волк, коза и капуста» на прологе

Публикации

Истории

Ближайшие события