Эйнштейны Риддл Пролог
Мне нужна помощь с домашним заданием по прологу для моего класса ИИ. Вопрос в том, чтобы написать пролог код для головоломки Эйнштейна. Я знаю, как написать это по-своему, но в домашней работе есть некоторые ограничения.
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
Я знаю, что мне нужно использовать список для домов, потому что они заказаны. Я хотел использовать список для характеристики дома, но у меня возникла проблема здесь.
Я собирался использовать анонимные переменные дома (англичанин, красный, _, _, _). но я не знаю, как интерпретировать это для домашней работы.
Вот ограничения: вы должны использовать следующие двоичные символы предиката:
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).
это имеет смысл немного, но в то же время выглядит совершенно неправильно. Я не думаю, что я могу пойти куда-нибудь с этим.:/
3 ответа
Этот сайт посвящен решению таких головоломок с помощью CLP(FD). Но вся мощь CLP (FD) здесь избыточна: ваше задание может быть эффективно решено путем поиска во всем пространстве решений, когда вы адекватно описали ограничения.
Решение будет состоять из 5 домов, где каждый атрибут удовлетворяет всем ограничениям, налагаемым описанием.
Помните, что для каждого атрибута следует использовать один и тот же символ (т. Е. Green и 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 - это более простая встроенная часть Пролога, но в этом случае достаточно для решения проблемы: когда все ограничения введены, переменные будут привязаны к соответствующим значениям. Ключ - способность члена недетерминированно выбирать члена (дух) решения.
Поэтому, когда вам нужно выразить ограничение между 2 различными элементами, вызовите член 2 раза и поместите ограничения между соответствующими переменными:
человек, который курит Честерельдса, живет в доме рядом с человеком с лисой
будет переведен на
....,
member(house(N, _, _, _, _, chesterelds), Problem),
member(house(M, _, _, fox, _, _), Problem),
next_to(N, M),
...
При таком выражении многих ограничений следует остерегаться идентичности символов: может быть полезно кодировать каждый предикат в отдельной процедуре, чтобы избежать ненужного наложения псевдонимов. Но couterpart также верно: если один и тот же символ участвует в более чем ограничении, необходимо будет обойти символ, чтобы сузить поиск.
Я позволю вам подумать о правильном представлении "геометрических" предикатов: next_to и right_of могут быть перечислены или выражены с помощью арифметики.
Эта головоломка (также известная как Головоломка Зебры) уже много раз обсуждалась на Stackru, см., Например:
Перевод Пролога может быть простым, правило по правилу, все еще используя парадигму создания домена путем выбора из него. Здесь это дом атрибутов дома; в связанных домах ответов атрибуты фиксируются человеком-программистом, а домен - это фактические жилые дома, что обеспечивает очень сжатое кодирование.
Другими словами, разница заключается в нотации: сложная нотация уже ведет нас на полпути, но это был человек, который изобрел ее и последовал за ней (как программист, который должен был записать norwegian в спецификации первого дома), а не компьютер. Здесь мы пытаемся вставить как можно меньше человеческих знаний в код, следуя ограничениям домашней работы. (хотя ничего спорно, конечно, и в конечном итоге в сторонясь вмешательство человека было бы компьютерную программу, которая принимает английский текст в качестве входных данных... что бы снова быть открытым для критики о том, как конкретно с учетом, что программа предназначена для поиска решений этой конкретная головоломка, или тип головоломки)
Видимо, вопрос отсутствует. Должно быть "кто пьет воду? Кому принадлежит зебра?":
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(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.