Изменить: эта головоломка также известна как «Загадка Эйнштейна».
Кто владеет Зебра (вы можете попробовать онлайн - версию здесь ) является примером классического набора головоломок , и я держал пари , что большинство людей на переполнение стека может решить с ручкой и бумагой. Но как могло бы выглядеть программное решение?
Основываясь на уликах, перечисленных ниже ...
- Всего пять домов.
- Каждый дом имеет свой неповторимый цвет.
- Все домовладельцы разных национальностей.
- У всех разные домашние животные.
- Все пьют разные напитки.
- Все они курят разные сигареты.
- Англичанин живет в красном доме.
- У шведа есть собака.
- Датчанин пьет чай.
- Зеленый дом находится слева от белого дома.
- Пьют кофе в зеленом доме.
- У человека, который курит Pall Mall, есть птицы.
- В желтом доме курят «Данхилл».
- В среднем доме пьют молоко.
- Норвежец живет в первом доме.
- Мужчина, который курит Blend, живет в доме рядом с домом с кошками.
- В доме рядом с домом, где у них есть лошадь, курят Данхилл.
- Мужчина, который курит Blue Master, пьет пиво.
- Немец курит принца.
- Норвежец живет рядом с синим домом.
- Пьют воду в доме рядом с домом, где курят Blend.
... кому принадлежит зебра?
language-agnostic
logic
constraint-programming
zebra-puzzle
activout.se
источник
источник
Ответы:
Вот решение на Python, основанное на программировании ограничений:
Вывод:
На поиск решения требуется 0,6 секунды (ЦП 1,5 ГГц).
Ответ: «Немец владеет зеброй».
Чтобы установить
constraint
модуль черезpip
: pip install python-constraintЧтобы установить вручную:
скачать:
$ wget https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45
извлечь (Linux / Mac / BSD):
$ bzip2 -cd python-constraint-1.2.tar.bz2 | tar xvf -
извлечь (Windows, с 7zip ):
> 7z e python-constraint-1.2.tar.bz2
> 7z e python-constraint-1.2.tar
установить:
$ cd python-constraint-1.2
$ установка python setup.py
источник
pip install python-constraint
? Я сделал это всего лишь мгновение назад, и, похоже, он дает ожидаемый результат.В Prolog мы можем создать экземпляр домена, просто выбирая из него элементы :) ( для эффективности делая взаимоисключающие варианты ). Используя SWI-Prolog,
Работает довольно мгновенно:
источник
Один плакат уже упоминал, что Prolog - это потенциальное решение. Это правда, и я бы использовал это решение. В более общем плане это идеальная проблема для автоматизированной системы вывода. Пролог - это язык логического программирования (и связанный с ним интерпретатор), образующий такую систему. Это в основном позволяет делать выводы из утверждений, сделанных с использованием логики первого порядка . FOL - это, по сути, более продвинутая форма логики высказываний. Если вы решите, что не хотите использовать Prolog, вы можете использовать аналогичную систему, созданную вами, используя такую технику, как modus ponens, чтобы делать выводы.
Вы, конечно, должны будете добавить некоторые правила о зебрах, так как они нигде не упоминаются ... Я считаю, что цель состоит в том, чтобы вы могли вычислить других 4 домашних животных и, таким образом, сделать вывод, что последнее из них - зебра? Вы захотите добавить правила, согласно которым зебра является одним из домашних животных, и в каждом доме может быть только одно домашнее животное. Внедрение такого рода «здравого смысла» в систему логических выводов является основным препятствием на пути использования этой техники в качестве настоящего ИИ. Есть некоторые исследовательские проекты, такие как Cyc, которые пытаются передать такие общие знания с помощью грубой силы. Они добились интересного успеха.
источник
Совместимость с SWI-Prolog:
У переводчика:
источник
Вот как я бы это сделал. Сначала я сгенерирую все упорядоченные n-кортежи
5 ^ 6 из них, 15625, легко управляемы. Затем я бы отфильтровал простые логические условия. их десять, и каждый из них, как вы ожидаете, отфильтрует 8/25 условий (1/25 условий содержит шведа с собакой, 16/25 содержат не шведа с не собакой) , Конечно, они не независимы, но после фильтрации их не должно быть много.
После этого у вас есть хорошая задача с графиком. Создайте граф с каждым узлом, представляющим один из оставшихся n-кортежей. Добавьте ребра к графу, если два конца содержат дубликаты в некоторой позиции из n кортежей или нарушают любые «позиционные» ограничения (их пять). Оттуда вы почти дома, найдите на графе независимый набор из пяти узлов (ни один из узлов не соединен ребрами). Если их не слишком много, вы могли бы просто полностью сгенерировать все 5 кортежей из n кортежей и просто отфильтровать их снова.
Это может быть хорошим кандидатом для кодового гольфа. Кто-то наверняка сможет решить ее в одну строчку чем-то вроде haskell :)
запоздалая мысль: начальный проход фильтра также может исключить информацию из позиционных ограничений. Немного (1/25), но все же значимо.
источник
Еще одно решение Python, на этот раз с использованием Python PyKE (Python Knowledge Engine). Конечно, он более подробен, чем использование модуля Python "constraint" в решении от @JFSebastian, но он обеспечивает интересное сравнение для всех, кто ищет механизм необработанных знаний для этого типа проблем.
clues.kfb
relations.krb
driver.py (на самом деле побольше, но в этом суть)
Пример вывода:
Источник: https://github.com/DreadPirateShawn/pyke-who-owns-zebra
источник
Вот отрывок из полного решения с использованием NSolver , размещенного в Einstein's Riddle на C # :
источник
Вот простое решение в CLP (FD) (см. Также clpfd):
Запустив его, выдает:
источник
neighbor(X,Y) :- abs(X-Y) #= 1.
В PAIP (глава 11) Норвиг решает загадку зебры, используя Пролог, встроенный в Лисп .
источник
Решение ES6 (Javascript)
С множеством генераторов ES6 и небольшим количеством lodash . Вам понадобится Babel, чтобы запустить это.
Результат:
Для меня время выполнения составляет около 2,5 с, но это можно значительно улучшить, изменив порядок правил. Для ясности я решил сохранить исходный порядок.
Спасибо, это был классный вызов!
источник
Это действительно проблема решения ограничений. Вы можете сделать это с помощью обобщенного типа распространения ограничений в языках программирования логики. У нас есть демонстрация специально для задачи Zebra в системе ALE (attribute logic engine):
http://www.cs.toronto.edu/~gpenn/ale.html
Вот ссылка на код упрощенной головоломки Zebra:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl
Другое дело - сделать это качественно.
источник
Самый простой способ решить такие проблемы программно - использовать вложенные циклы для всех перестановок и проверить, удовлетворяет ли результат предикатам в вопросе. Многие из предикатов могут быть перенесены из внутреннего цикла во внешние циклы, чтобы резко снизить вычислительную сложность до тех пор, пока ответ не будет вычислен за разумное время.
Вот простое решение F #, взятое из статьи в F # Journal :
Результат за 9 мс:
источник
Пример Microsoft Solver Foundation из: https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396
источник
Это решение MiniZinc для загадки зебры, как это определено в Википедии:
Решение:
источник