Einsteins Riddle Prolog

Мне нужна помощь с домашней работой пролога для моего класса AI. Вопрос заключается в написании прологового кода для загадки эйнштейнов. Я знаю, как записать его самостоятельно, но есть некоторые ограничения в домашней работе.

 there are 5 houses
 the Englishman lives in the red house
 the Spaniard owns the dog
 coffee is drunk in the green house
 the Ukrainian drinks tea
 the green house is immediately to the right of the ivory house
 the Old Gold smoker owns snails
 Kools are smoked in the yellow house
 milk is drunk in the middle house
 the Norwegian lives in the first house
 the man who smokes Chesterelds lives in the house next to the man with the fox
 3 Kools are smoked in the house next to the house where the horse is kept
 the Lucky Strike smoker drinks orange juice
 the Japanese smokes Parliaments
 the Norwegian lives next to the blue house

Я знаю, что мне нужно использовать список для домов, потому что они заказаны. Я тоже хотел использовать список характеристик дома, но у меня проблема.

Я собирался использовать анонимные переменные house (англичанин, красный, _, _, _). но я не знаю, как интерпретировать это для домашней работы.

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

owns(N,Pet)
smokes(N, Cigarette).
drinks(N, Drink).

Кроме того, вы можете использовать любое количество предикатов.

вот как я инициализировал факты, но я не знаю, как сделать правила в этом случае

next_to(X,Y) :- right_of(X,Y); right_of(Y,X).

owns(spaniard, dog).
drinks(ukrainian, tea).
smokes(japanese, parliaments).
right_of(ivory, green).
lives(englishman, red).
owns(X, snail) :- smokes(X, old_gold).
smokes(X, kools) :- owns(X, yellow).
smokes(X, lucky_strike) :- drinks(X, orange_juice).
drinks(X, coffee) :- owns(X, green_house).

это имеет смысл немного, но в то же время он выглядит совершенно неправильно. Я не думаю, что смогу пойти с этим.:/

Ответы

Ответ 1

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

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

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

Также 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 это более простой встроенный Prologin, но в этом случае достаточно решить проблему: когда все ограничения были опубликованы, переменные будут привязаны к соответствующим значениям. Ключом является способность члена не детерминистически выбирать элемент (duh) решения.

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

Другими словами, разница в обозначениях: сложная нотация уже набирает нас наполовину, но это был человек, который изобрел ее и последовал за ней (как программист должен записать norwegian в первой спецификации дома), а не компьютер. Здесь мы стараемся вставить как можно меньше человеческих знаний в код, следуя домашним ограничениям. <Суб > (хотя ничего спорно, конечно, и в конечном итоге в сторонясь вмешательство человека было бы компьютерную программу, которая принимает английский текст в качестве входных данных... что бы снова быть открытым для критики о том, как конкретно с учетом, что программа для поиска решения этой конкретной головоломки или типа головоломок)

По-видимому, вопрос отсутствует. Это должно быть "кто пьет воду", кто владеет зеброй? "

zebra(Z,W,HS):-         
    length( HS, 5),      % nation?  color?  what 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(B,A,HS).
middle(A, [_,_,A,_,_]).
first(A, [A|_]).

attr(House, Attr-Value):- 
    memberchk( Attr-X, House),           % unique attribute names
    X = Value.
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
color( H, V):-  attr( H, color-V).       %   of house attributes
drink( H, V):-  attr( H, drink-V).       %   which *is* a house

Тестирование

3 ?- time((zebra(Z,W,_),maplist(nation,[Z,W],R),writeln(R),false ; true)).
[jpn,nor]
% 181,101 inferences, 0.070 CPU in 0.080 seconds (88% CPU, 2567888 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.