Разгадай загадку в прологе

Question

Я хочу решить эту загадку в прологе:

Студенты Лили, Джек и Дейзи ходят в один университет. Все они из другой страны и имеют разные хобби. Все они идут в университет в США, где живет один из них. У Лили лучшие оценки, чем у итальянки. У Джека лучшие оценки, чем у тех, кто любит читать книги. Лучшие оценки имеет тот, кто любит футбол. Джек родом из Германии, а Дейзи любит готовить.

Кто есть кто (имя, страна, хобби, оценки)?

Правильное решение должно быть:

• Лили, США, чтение книг, 2 класс
• Джек, Германия, футбол, 1 класс
• Маргаритка, Италия, Кулинария, 3 класс

У меня сейчас проблема в том, что я не знаю, как мне решить эту загадку. Как мне определить факты и как лучше разгадать загадку?

Answer 1

Хитрость для ответа на эти вопросы головоломки в Прологе состоит в том, чтобы генерировать (извлекать) возможные ответы и затем проверять их на соответствие логическим ограничениям. Итак, если Лили - лицо P1, найдите любого человека P2 и проверьте, не является ли этот человек из Италии. И так далее с другими правилами.

Это означает, что, во-первых, вам нужны некоторые пункты с возможными странами, возможными увлечениями и возможными оценками. Не все возможности необходимы, потому что некоторые уже исключены этим вопросом.

Приведенное ниже решение основано на произвольном создании Лили человек 1, Джек человек 2 и Дейзи человек 3.

Загрузите в Пролог и запросите кто (P1,C1,H1,G1, P2,C2,H2,G2, P3,C3,H3,G3).

country(italy).
country(usa).
hobby(football).
hobby(reading).
grade(c:1).
grade(b:2).
grade(a:3).



who(lily,C1,H1,Grade1, jack,germany,H2,Grade2, daisy,C3,cooking,Grade3):-
    country(C1), country(C3), C1 \= C3,
    hobby(H1), hobby(H2), H1 \= H2,
    grade(G1:Grade1), grade(G2:Grade2), grade(G3:Grade3),
    G1 \= G2, G2 \= G3, G1 \= G3,
    (C3=italy, G1@>G3),
    (H1=reading, G2@>G1),
    ((H1=football, G1@>G2, G1@>G3); (H2=football, G2@>G1, G2@>G3)).

Answer 2

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

name(lily).  % (1)
name(jack).
name(daisy).
country(italy).
country(usa).
country(germany).
hobby(football).
hobby(cooking).
hobby(reading).
grade(1).
grade(2).
grade(3).

student(N,C,H,G):-  % (2)
    name(N), country(C), hobby(H), grade(G).

permute(P,X,Y,Z):- (4)
    call(P,X), call(P,Y), call(P,Z)  % (6)
    , X\=Y, Y\=Z, X\=Z.

students(A,B,C):- (3)
    permute(name,N1,N2,N3)   % (5)
    , permute(country,C1,C2,C3)
    , permute(hobby,H1,H2,H3)
    , permute(grade,G1,G2,G3)
    , A = student(N1,C1,H1,G1)  % (7)
    , B = student(N2,C2,H2,G2)
    , C = student(N3,C3,H3,G3)
    .

who(A,B,C):-  % (8)
    students(A,B,C)
    , A = student(lily,C1,H1,G1)  % (9)
    , B = student(jack,C2,H2,G2)
    , C = student(daisy,C3,H3,G3)
    , C2 = germany                % (10)
    , H3 = cooking
    , (( C2=italy -> G1 < G2)     % (11)
      ;( C3=italy -> G1 < G3))
    , (( H1=reading -> G2 < G1)
      ;( H3=reading -> G2 < G3))
    , (( H1=football -> G1 < G2, G1 < G3)
      ;( H2=football -> G2 < G1, G2 < G3)
      ;( H3=football -> G3 < G1, G3 < G2))
    .

% Running it:
% ?- who(A,B,C).
% A = student(lily, usa, reading, 2),
% B = student(jack, germany, football, 1),
% C = student(daisy, italy, cooking, 3) ;
% false.

обсуждение

Так что здесь происходит довольно много (что меня заинтриговало) и несколько вариантов, которые можно сделать по-другому (следовательно, это, вероятно, хороший контраст с решением @ RdR).

• Как отмечали другие, один аспект заключается в том, как кодировать информацию, которая приводится в описании проблемы. Вы можете выразить это очень конкретно (решая только этот случай), или быть более общим (например, чтобы разрешить распространение проблемы более чем на 3 ученика).
• Что отличает эту проблему от аналогичных других, так это то, что у вас есть набор ограничений, которые влияют либо на одного студента ("Джек из Германии"), либо на двух студентов ("оценки Лили лучше, чем у итальянского"), либо включают все они ("У того, кто любит футбол, есть лучшие оценки").
• Более того, у вас есть дизъюнктивные ограничения ("Все они из разных стран и имеют разные хобби"). Пролог очень хорошо разбирается во всех возможных случаях факта, но его сложнее выбрать один экземпляр и оставить его для следующего вызова предиката. Это вынуждает вас найти способ получить набор значений из факта, который попарно различен. (Например, когда Пролог соглашается на чтение хобби Лили, он не должен также назначать чтение хобби Джека).
• Поэтому после перечисления всех известных фактов и их возможных значений (1) я сначала определил предикат student/4 (2) просто заявить, что студент имеет эти 4 свойства. Это создает всевозможные комбинации студентов и их атрибутов, а также позволяет им всем иметь одинаковые имена из одной страны, asf.
• Это хороший пример того, как создать слишком большой набор результатов в Прологе, а затем попытаться сузить его еще больше (как написал кто-то еще). Дальнейшие предикаты могут использовать этот "генератор" и фильтровать все больше и больше решений из его набора результатов. Это также легче проверить, на каждом этапе вы можете проверить, имеет ли смысл промежуточный вывод.
• В следующем предикате students/3 (3) я стараюсь в точности то, что упомянул ранее, создавая экземпляры учеников, которые, по крайней мере, не используют один и тот же атрибут дважды (например, два ученика имеют одинаковое хобби). Чтобы достичь этого, мне нужно просмотреть все мои атрибуты (имя /1, страна /1, ...), получить три значения для каждого и убедиться, что они попарно различны.
• Чтобы не приходилось явно делать это для каждого из атрибутов, где реализация всегда была бы одинаковой, за исключением имени атрибута, я создал предикат-помощник permute/4 (4) что я могу передать имя атрибута, и он будет трижды искать атрибут как факт, и убедиться, что все связанные значения не совпадают.
• Поэтому, когда я звоню permute(name,N1,N2,N3) в students/3 (5) это приведет к поискам call(P,X), call(P,Y), call(P,Z) (6) что приводит к тому же, что и вызов name(X), name(Y), name(Z), (Поскольку я собираю 3 разных значения из всегда 3 фактов одного и того же атрибута, это практически то же самое, что делать 3 перестановки набора из 3 значений, отсюда и название предиката-помощника.)
• Когда я добираюсь до (7), я знаю, что у меня есть отдельные значения для каждого студенческого атрибута, и я просто распределяю их по трем ученикам. (На самом деле это должно работать так же без student/4 предикат, так как вы всегда можете составить структурированные термины, как это на лету в Прологе. Имея student Предикат предлагает дополнительное преимущество проверки того, что глупые ученики не могут быть построены, например, "ученик (lily, 23, asdf, -7.4)".)
• Так :- students(A,B,C). производит все возможные комбинации из 3 учеников и их атрибутов, не используя дважды ни один из задействованных атрибутов. Ницца. Это также оборачивает (более сложный) student() структуры в удобных однобуквенных переменных, что делает интерфейс намного чище.
• Но кроме этих ограничений, связанных с дизъюнктивностью, мы не реализовали никаких других ограничений. Теперь они следуют в (менее элегантно) who/3 предикат (8). В основном использует students/3 в качестве генератора и пытается отфильтровать все нежелательные решения, добавив больше ограничений (следовательно, он имеет в основном ту же сигнатуру, что и students/3.)
• Теперь начинается другая интересная часть, так как мы должны уметь не только фильтровать отдельных student экземпляры, а также ссылаться на них по отдельности ("Дейзи", "Джек", ...) и их соответствующие атрибуты ("Хобби Дейзи" и т. д.). Поэтому, связывая мои переменные результата A, B и C, я сопоставляю шаблон с определенными именами. Отсюда и буквальные имена lily, jack asf из (9). Это освобождает меня от рассмотрения случаев, когда Лили может прийти первым, вторым или третьим (как students/3 будет генерировать такие перестановки). Таким образом, все 3 группы студентов, которые не приходят в таком порядке, отбрасываются.
• Я мог бы также сделать это позже в явном ограничении, как N1 = lily АФС. Я делаю это сейчас, основываясь на простых фактах, что Джек из Германии, а Дейзи любит готовить (10). Когда те, которые терпят неудачу, Пролог возвращается к начальному вызову students/3, чтобы получить другой набор студентов, он может попробовать.
• Теперь следуйте дополнительным известным фактам о оценках Лили, оценках Джека и оценках любителя футбола (11). Это особенно уродливый код.
• Во-первых, было бы неплохо иметь предикат-помощник, который сможет вернуть ответ на запрос "студент с атрибутом X". Для этого потребуется текущий выбор студентов, A, B и C, имя атрибута ("страна") и значение ("Италия"), и будет возвращен соответствующий студент. Таким образом, вы можете просто запросить студента из Италии, а не предполагать, что это должен быть второй ИЛИ третий студент (поскольку описание проблемы предполагает, что сама Лили не из Италии).
• Итак, этот гипотетический предикат помощника, давайте назовем его student_from_attribute понадобится другой помощник, который найдет значение в структуре студента по имени и вернет соответствующее значение. Легко во всех языках, которые поддерживают некоторый объект / названный кортеж / запись, где вы можете получить доступ к полям в нем по имени. Но ванильного Пролога нет. Так что нужно было бы поднять, что-то, что я не могу снять с макушки головы.
• Так же who/3 Предикат может воспользоваться этим другим помощником, так как вам потребуется атрибут, отличный от студента, возвращенного из student_from_attribute как "оценка", и сравните это с оценкой Лили. Это сделало бы все эти ограничения намного приятнее, например, student_from_attribute([A,B,C], country, italy, S), attrib_by_name(S, grade, G), G1 < G, Это может быть применено таким же образом к ограничениям чтения и футбола. Это было бы не короче, а чище и более общим.

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

Answer 3

Во-первых, из заполнения того, что мы получаем из первого утверждения, мы получаем следующее.

(Lily, _, _, _)
(Jack,Germany, _, _)
(Daisy, _, Cooking, _)

Где _ заявить, что мы чего-то не знаем Я должен также сказать, что это не обязательно пролог, это скорее здравый смысл, чем что-либо еще.

Мы получаем фразу "У Лили лучшие оценки, чем у итальянки", это означает, что Дейзи из Германии, а Лили из США - начиная с Джека из Германии.

(Lily, USA, _, Grade>Daisy)
(Jack,Germany, _, _)
(Daisy, Italy, Cooking, Grade<Lily)

Затем у нас есть "у Джека более высокие оценки, чем у того, кто любит читать книги", что говорит о том, что он будет футболистом, а следующая строка говорит нам, что у него лучшая оценка. Затем мы можем оперативно пополнить оставшиеся и получаем:

(Lily, USA, Reading, Grade2)
(Jack,Germany, Football, Grade1)
(Daisy, Italy, Cooking, Grade3)

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