Уникальные элементы в списке (Пролог)

Я реализую вариант загадки Эйнштейна, и у меня возникли некоторые проблемы.

При попытке вычислить решение я пробую это:

solve(Street) :- Street = [_House1,_House2,_House3,_House4,_House5],
%hint one goes here
%hint two goes here
%etc.

Затем я могу спросить решение, набрав:solve(Street)

Однако это подходит как решение:

  1. дом (цветок, еда, домашнее животное, спорт)
  2. дом (цветок, еда, домашнее животное, спорт)
  3. дом(x , еда, домашнее животное, спорт)
  4. дом (цветок, еда, домашнее животное, спорт)
  5. дом(x, цветок, домашнее животное, спорт)

Как видите, 2 раза x, остальные — это все виды продуктов, цветов, домашних животных и спорта. Но каждый тип уникален: если одному человеку нравится цветок X, никому другому X не может понравиться.

Теперь легко понять причину, по которой мое решение дает 2 x: нам дано некоторое количество подсказок, но во всех подсказках упоминаются только 4 цветка. Таким образом, Пролог не знает, что есть еще один цветок, и просто дважды использует x просто потому, что это возможно, и выполняет все остальные подсказки.

Что я хочу сказать, так это то, что все типы еды, цветов и т. д. на улице уникальны, поэтому он должен оставить пустое место, когда он уже использовал все типы. 3 будет выглядеть как: house(x , food, pet ,sport), а 5 будет выглядеть как: house(_, flower, pet, sport).

Я также пытался добавить это в подсказки: (скажем, «кактус» — это один из цветов, не упомянутых в подсказках) member(house(cactus,_,_,_), Street)

Однако на этом моя программа не заканчивается...

Подсказка может выглядеть так: is_neighbour(house(_,_,_,football),house(_,_,fish,_), Street), с : is_neighbour(A,B,List) дает true, когда A и B находятся рядом друг с другом в List. Подсказку можно перевести так: человек, который любит футбол, живет рядом с человеком, у которого есть рыба.

Если нужно предоставить дополнительную информацию, я готов уточнить. :)


unique prolog zebra-puzzle
person Aerus    schedule 10.12.2010    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Чтобы указать, что ни о каком цветке не сообщается дважды, а также убедиться, что все цветы связаны, вы можете использовать предикат permutation/2: список всех цветов должен быть перестановкой списка указанных цветов. Это будет выглядеть как [непроверенный]

flowers([], []).
flowers([house(Flower,_,_,_)|Street], [Flower|Rest]) :- flowers(Street, Rest).

-- ...
   flowers(Street, Flowers), 
   permutation(Flowers, [kaktus, tulpe, nelke, rose, fingerhut]),

Изменить: для 10 цветов использование перестановок, вероятно, слишком медленно. Альтернативный подход

flower(kaktus).
flower(tulpe).
flower(nelke).
--...

       flowers(Street,[F1,F2,F3,F4,F5,F6,F7,F8,F9,F10]),
       flower(F1), flower(F2), F1\=F2,
       flower(F3), F3\=F1, F3\=F2,
       flower(F4), F4\=F1, F4\=F2, F4\=F3,
       --...
person Martin v. Löwis    schedule 10.12.2010
comment
Звучит как логичный и понятный ответ, однако я, должно быть, делаю что-то не так.. Я добавил все цветы во второй список перестановок. Я также поставил flowers(Street, Flowers) и перестановку в solve(Street). Но сейчас, похоже, это не конец. (обычно это заканчивалось в течение 5 минут, но теперь это было более 15 минут.) Имеет ли значение, где я поставил permutation ? - person Aerus; 11.12.2010
comment
Перестановка должна быть симметричной для обоих аргументов, поэтому замена аргументов не должна помочь. Однако размещение вызова перестановки в другом месте должно очень помочь: вы должны сначала поставить те условия, которые больше всего ограничивают пространство решения. Поместите в него вызовы записи, чтобы он отслеживал, что он делает. - person Martin v. Löwis; 11.12.2010
comment
Когда я помещаю вызов (write()) вокруг перестановки в конце подсказок, он дает: перестановка ([герань, гиацинт, лели, георгин, лели], [кактус, лели, герань, гиацинт, георгин]). Когда я помещаю его перед всеми подсказками, он дает мне: перестановка ([_46,_53,_60,_67,_74], [кактус, лели, герань, гиацинт, георгин]). Я не уверен, что это первое означает. Вывод по-прежнему дает мне 2 x, но теперь он заканчивается. Нужно ли мне также добавлять перестановки для других типов, чтобы эта единственная перестановка работала? - person Aerus; 11.12.2010
comment
Не уверен, что вы имеете в виду, когда пишете вместо permutation(). Вы говорите, что используете перестановку как структуру, которую просто распечатываете? Вы должны оценивать его как предикат и ставить отпечаток после, а не вокруг перестановки. - person Martin v. Löwis; 11.12.2010
comment
Я почти уверен, что делаю что-то не так с записью. Вот мой код: pastebin.com/5TjJJ5nj (оно длинное, но все вещи похожи, поэтому при чтении его можно довольно быстро пропустить), не могли бы вы сказать мне, куда я могу поместить эту запись? Кроме того, что я могу указать в качестве аргумента для записи, так как это дает мне ошибку, когда я не передаю никаких аргументов... - person Aerus; 11.12.2010
comment
Не могли бы вы опубликовать ссылку на версию, где вы добавили вызов записи в коде? - person Aerus; 11.12.2010
comment
Спасибо, когда я помещаю его в начало подсказок, он делает то, для чего предназначен: он вычисляет все перестановки списка цветов, однако 10! (10 элементов) — это примерно 3,5 миллиона перестановок, поэтому, конечно, это занимает много времени. Затем я помещаю его в конец подсказок, и он ничего не печатает, возможно, потому, что это занимает слишком много времени? Добавляя его в конец подсказок, проверяет, являются ли все возможные ответы до сих пор перестановкой списка цветов, или генерирует все перестановки и проверяет, являются ли все возможные ответы перестановкой? - person Aerus; 11.12.2010
comment
Смотрите мою правку. Для десяти элементов использование перестановки действительно неуместно (в исходной публикации было только 5 домов). - person Martin v. Löwis; 11.12.2010
comment
Действительно, я хотел, чтобы мой вопрос был простым, и изменил его на 5. (хотя я должен был указать, что на самом деле у меня было 10 значений для каждого типа). Я понятия не имею, что делает код в вашем редактировании, я добавил: цветок (значение ) для всех 10 цветов и дополнен кодом до flower(F10), F10\=F1, F10\=F2,...,F10\=F8, F10\=F9.. Программа, кажется, нигде не заканчивается в течение получаса. Поскольку я действительно не понимаю, что такое код, я не могу дать этому объяснение... - person Aerus; 11.12.2010
comment
Кроме того, это: flower(F2), F1\=F2, или flower(F2), F2\=F1,? (оно заканчивается в последнем случае, но все еще с двумя крестиками) - person Aerus; 11.12.2010
comment
Опять же, вам следует писать заявления в стратегических местах, чтобы выяснить, как все связывается. AFAIK, \= симметричен. Что касается: что это делает - я не очень хочу объяснять, так как вы должны сами это интерпретировать. И имейте в виду, что лучше поставить более конкретные ограничения с меньшим количеством альтернатив в начале кода. - person Martin v. Löwis; 11.12.2010
comment
Хорошо, код оказался не таким сложным, как я думал, это просто еще один способ показать, что каждое значение должно быть уникальным. Я проверил это на нескольких более простых примерах, и я понимаю, что он делает, также, если я включу более простые подсказки (member(house(..)), [,,X,_] = Street), это показывает возможные решения со всеми уникальными значениями. Итак, теперь я начну включать подсказку для каждой подсказки и посмотрю, не пойдет ли где-то не так... Большое спасибо, я буду обновлять этот вопрос, как только узнаю больше. - person Aerus; 12.12.2010
comment
Сейчас это работает, хотя это занимает довольно много времени. Я также отсортировал предикаты по их специфичности: сначала member(), затем is_two_further, затем is_one_further и, наконец, is_neighbour. Спасибо за ваше время и терпение, я еще не могу проголосовать за ваш ответ (нужно 15 баллов), но, по крайней мере, я уже могу его принять. Спасибо. - person Aerus; 12.12.2010