Pull to refresh

Задача Эйнштейна на Прологе

Reading time 3 min
Views 20K
Хотел продолжить неделю задачи Эйнштейна на Хабре. После очень и не очень нестандартных решений, хотелось бы показать как логические задачки можно (и нужно) решать на языках логического программирования (простите за тавтологию).
Под катом можно увидеть почему Пролог так хорошо подходит для решения этой задачи.

Задача уже, наверно, всем поднадоела, потому буду краток.
Основы пролога уже очень хорошо расписал товарищ xonix, поэтому моя задача совсем проста.

Дом мы будем представлять как список из 5 элементов, по одному на каждый атрибут: национальность хозяина, домашний питомец, марка сигарет, напиток и цвет дома, соответственно. Всего домов 5, потому решение будем искать среди списков (списков) длины 5.
Для этого нам понадобятся стандартные предикаты:
  • member(Elem, List) — истина, если элемент Elem есть в списке List
  • nth1(N, List, Elem) — истина, если элемент Elem в списке List стоит на N-й (счет начинается с 1) позиции
  • nextto(X, Y, List) — истина, если X стоит перед (слева от) Y в списке List
Также, нам нужно уметь сказать что 2 дома стоят рядом друг с другом. Это можно реализовать вот таким простым предикатом:
neighbors(X, Y, List) :- nextto(X, Y, List).
neighbors(X, Y, List) :- nextto(Y, X, List) .
Т.е., либо X слева от Y, либо наоборот.

А вот, собственно, и решение:
einstein :-
   /* 0. Всего 5 домов */
    Houses = [_,_,_,_,_],
   /* 1. Норвежец живёт в первом доме. */
    nth1(1, Houses, [norwegian,_,_,_,_]),
   /* 2. Англичанин живёт в красном доме. */
    member([englishman,_,_,_,red], Houses),
   /* 3. Зелёный дом находится слева от белого, рядом с ним. */
    nextto([_,_,_,_,green], [_,_,_,_,white], Houses),
   /* 4. Датчанин пьёт чай. */
    member([dane,_,_,tea,_], Houses),
   /* 5. Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек. */
    neighbors([_,_,marlboro,_,_], [_,cat,_,_,_], Houses),
   /* 6. Тот, кто живёт в жёлтом доме, курит Dunhill. */
    member([_,_,dunhill,_,yellow], Houses),
   /* 7. Немец курит Rothmans. */
    member([german,_,rothmans,_,_], Houses),
   /* 8. Тот, кто живёт в центре, пьёт молоко. */
    nth1(3, Houses, [_,_,_,milk,_]),
   /* 9. Сосед того, кто курит Marlboro, пьёт воду. */
    neighbors([_,_,marlboro,_,_], [_,_,_,water,_], Houses),
   /* 10. Тот, кто курит Pall Mall, выращивает птиц. */
    member([_,bird,pallmall,_,_], Houses),
   /* 11. Швед выращивает собак. */
    member([swede,dog,_,_,_], Houses),
   /* 12. Норвежец живёт рядом с синим домом. */
    neighbors([norwegian,_,_,_,_], [_,_,_,_,blue], Houses),
   /* 13. Тот, кто выращивает лошадей, живёт в синем доме. */
    member([_,horse,_,_,blue], Houses),
   /* 14. Тот, кто курит Winfield, пьет пиво. */
    member([_,_,winfield,beer,_], Houses),
   /* 15. В зелёном доме пьют кофе. */
    member([_,_,_,coffee,green], Houses),

   /* Внимание, вопрос: у кого рыба? */
    member([Owner,fish,_,_,_], Houses),

    /* Печатаем решение */
    print('Owner of the fish: '), print(Owner), nl,
    print('Full Solution: '), print(Houses), nl.


Как видим, суммарное количество строк в программе практически совпадает с количеством условий в оригинальной задаче.
Да и сами строчки читаются почти как оригинальные условия. Пролог — очень декларативный язык, нам лишь нужно описать что мы от него хотим.
Интерпретатор выполняет за нас всю грязную работу, причем достаточно быстро. На моей машине скрипт выполняется за 0.08сек, если скомпилировать то будет еще немного быстрее.

Чтоб запустить программку нужно установить себе SWI-Prolog, скопировать текст в файл и добавить вот такой-вот хеш-бэнг:
#!/usr/bin/pl -q -t einstein -s
(ну или берем код вот отсюда)

Эти функции входят в стандартную библиотеку. Приведены тут для полноты решения, чтобы показать что даже на «чистом» Прологе решение не сильно больше.
member(X, [X | _]).
member(X, [_ | Rest]) :- member(X, Rest).

nth1(1, [Elem | _], Elem).
nth1(N, [_ | Rest], Elem) :- N > 1, K is N-1, nth1(K, Rest, Elem).

nextto(L, R, [L, R | _]).
nextto(L, R, [_ | Rest]) :- nextto(L, R, Rest).

Также, условия 0, 1 и 8 можно упростить до одного:
Houses = [[norwegian,_,_,_,_],_,[_,_,_,milk,_],_,_]
тогда не нужен предикат nth1, но мне хотелось быть как можно ближе к оригиналу.
Tags:
Hubs:
+75
Comments 23
Comments Comments 23

Articles