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

Этот сайт посвящен решению таких головоломок с помощью CLP (FD). Но полная мощь CLP (FD) здесь излишня: ваше задание может быть решено с эффективным поиском во всем пространстве решений, если вы адекватно описали ограничения.

Решение будет состоять из 5 домов, каждый атрибут которых удовлетворяет всем ограничениям, налагаемым описанием.

Помните, что для каждого атрибута следует использовать один и тот же символ (т.е. зеленый и green_house неверно, выберите один из них).

Также next_to кажется неправильным: если вы нумеруете от 1 до 5, это может быть вычислено или перечислено, но относится к ближайшему соседу.

Итак, завершите представление данных "пространство поиска решения", что-то вроде

Problem = [
 house(1, Nationality1, Color1, Pet1, Drinks1, Smokes1),
 house(2, Nationality2, Color2, Pet2, Drinks2, Smokes2),
 ...
],
% place constraints
member(house(_, englishman, red, _, _, _), Problem),
member(house(_, spaniard, _, dog, _, _), Problem),
...

member / 2 это более простая встроенная функция Prolog, но в этом случае ее достаточно для решения проблемы: когда все ограничения опубликованы, переменные будут привязаны к соответствующим значениям. Ключевым моментом является способность члена недетерминированно выбирать член (да) решения.

Поэтому, когда вам нужно выразить ограничение между двумя разными элементами, вызовите член дважды и поместите ограничения между соответствующими переменными: т.е.

человек, который курит Chesterelds, живет в доме рядом с человеком с лисой

будет переведен на

....,
member(house(N, _, _, _, _, chesterelds), Problem),
member(house(M, _, _, fox, _, _), Problem),
next_to(N, M),
...

Выражая таким образом множество ограничений, остерегайтесь идентичности символов: может быть полезно закодировать каждый предикат в отдельной процедуре, чтобы избежать излишнего наложения имен. Но верна и обратная сторона: если один и тот же символ используется не только в ограничении, необходимо будет обойти символ, чтобы сузить область поиска.

Я позволю вам подумать о правильном представлении «геометрических» предикатов: next_to и right_of можно перечислить или выразить с помощью арифметики.

Эта головоломка (также известная как головоломка с зеброй) много раз обсуждалась ранее в Stackoverflow, см., Например:

• Решение проблемы Кто владеет Zebra программно?
• Почему я не могу получить ответ на зебра в прологе?
• Решение логической головоломки в Prolog
• Загадка Эйнштейна

Перевод Пролога может быть простым, правило за правилом, по-прежнему следуя парадигме создания экземпляра домена путем выбора из него . Здесь это область атрибутов дома; в связанном ответе атрибуты дома фиксируются программистом, а домен представляет собой фактические жилые дома, что позволяет очень сжатое кодирование.

Другими словами, разница заключается в нотации: сложная нотация уже уводит нас на полпути, но это был человек, который изобрел ее и последовал ей (как программист, имеющий записать norwegian в первую спецификацию дома напрямую, в соответствующей позиции аргумента position) - не компьютер.

Здесь мы стараемся внести в код как можно меньше человеческих знаний, следуя ограничениям домашнего задания. _{(хотя, конечно, все можно спорить, и в конечном итоге в предотвращении вмешательства человека будет компьютерная программа, которая принимает английский текст в качестве входных данных ... что снова будет открыто для критики относительно того, насколько конкретно эта программа предназначена для поиска решения этой конкретной головоломки или типа головоломок и т. д. и т. д.)}

Мы кодируем его в стиле сверху вниз. Видимо вопрос отсутствует. Это должно быть «кто пьет воду? Кому принадлежит зебра?»:

zebra( Z, W ,HS) :-         
    length(        HS, 5),      % nation? color? what's that? define it later...
    member(  H1,   HS),    nation( H1, eng    ),    color( H1, red    ),
    member(  H2,   HS),    nation( H2, spa    ),    owns(  H2, dog    ),            
    member(  H3,   HS),    drink(  H3, coffee ),    color( H3, green  ),         
    member(  H4,   HS),    nation( H4, ukr    ),    drink( H4, tea    ),
    right_of(B, A, HS),    color(  A , ivory  ),    color( B , green  ),
    member(  H5,   HS),    smoke(  H5, oldgold),    owns(  H5, snails ),   
    member(  H6,   HS),    smoke(  H6, kools  ),    color( H6, yellow ), 
    middle(  C,    HS),    drink(  C , milk   ),  
    first(   D,    HS),    nation( D , nor    ),
    next_to( E, F, HS),    smoke(  E , chester),    owns(  F , fox    ),
    next_to( G, H, HS),    smoke(  G , kools  ),    owns(  H , horse  ),
    member(  H7,   HS),    smoke(  H7, lucky  ),    drink( H7, orange ),
    member(  H8,   HS),    nation( H8, jpn    ),    smoke( H8, parlamt),
    next_to( I, J, HS),    nation( I , nor    ),    color( J , blue   ),
    member(  W,    HS),    drink(  W , water  ),
    member(  Z,    HS),    owns(   Z , zebra  ).

right_of( B, A, HS) :- append( _, [A, B | _], HS).
next_to( A, B, HS) :- right_of( B, A, HS) ; right_of( A, B, HS).
middle( A, [_,_,A,_,_]).
first( A, [A | _]).

nation(H, V) :-  attr( H, nation-V).
owns(  H, V) :-  attr( H, owns-V).        % select an attribute
smoke( H, V) :-  attr( H, smoke-V).       %   from an extensible record H
color( H, V) :-  attr( H, color-V).       %   of house attributes
drink( H, V) :-  attr( H, drink-V).       %   which *is* a house

attr(House, Attr-Value) :- 
    memberchk( Attr-X, House),            % unique attribute names
    X = Value.

Тестирование, выполнение исчерпывающего поиска с отказоустойчивым циклом,

3 ?- time((zebra(Z,W,_), maplist(nation,[Z,W],R), writeln(R), false ; true)).
[jpn,nor]
% 180,974 inferences, 0.016 CPU in 0.020 seconds (78% CPU, 11600823 Lips)
true.

Вот как определяются дома:

5 ?- zebra(_, _, HS), maplist( writeln, HS),
     false.
[smoke-kools,  color-yellow, nation-nor,    owns-fox,      drink-water |_G859]
[nation-ukr,   drink-tea,    smoke-chester, owns-horse,    color-blue  |_G853]
[nation-eng,   color-red,    smoke-oldgold, owns-snails,   drink-milk  |_G775]
[nation-spa,   owns-dog,     color-ivory,   smoke-lucky,   drink-orange|_G826]
[drink-coffee, color-green,  nation-jpn,    smoke-parlamt, owns-zebra  |_G865]
false.

или, если списки атрибутов "заморожены" путем фиксации их длины, а затем отсортированы,

7 ?- zebra( _, _, HS), maplist( length, HS, _), !, maplist( sort, HS, S),
     maplist( writeln, S), false.
[color-yellow, drink-water,  nation-nor,  owns-fox,    smoke-kools  ]
[color-blue,   drink-tea,    nation-ukr,  owns-horse,  smoke-chester]
[color-red,    drink-milk,   nation-eng,  owns-snails, smoke-oldgold]
[color-ivory,  drink-orange, nation-spa,  owns-dog,    smoke-lucky  ]
[color-green,  drink-coffee, nation-jpn,  owns-zebra,  smoke-parlamt]
false.

Также легко сделать так, чтобы предикат attr/2 принимал списки Name-Value пар, что позволяет более естественно плавный, высокоуровневый стиль кодирования с своего рода «расширяемыми записями» - можно даже сказать «объектами» - спецификациями, например

zebra( Z, W ,HS):-         
    length(       HS, 5), 
    member(  H1,  HS),    attr( H1,  [nation-eng,   color-red  ] ),
    member(  H2,  HS),    attr( H2,  [nation-spa,   owns-dog   ] ),
    member(  H3,  HS),    attr( H3,  [drink-coffee, color-green] ),
    ......

и т. д..