Алгоритмически генерировать загадку Зебра / Эйнштейна
Во-первых, я не обязательно ищу полный алгоритм, я могу просто скопировать и вставить, а затем назвать его день. Любые решения "общего подхода" были бы хороши для меня!
Весь этот пост был спровоцирован медленным днем на работе, и он наткнулся на этот сайт и не смог понять, как они реализовали свой генератор.
Эта проблема
Для тех из вас, кто не знает, "Головоломка Зебры" или "Головоломка Эйнштейна" - это знаменитая логическая головоломка, с которой вы, вероятно, сталкивались раньше.
Полная статья вики здесь, но я опубликую соответствующие фрагменты.
There are five 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 Chesterfields lives in the house next to the man with the fox.
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.
Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be
added that each of the five houses is painted a different color, and their inhabitants
are of different national extractions, own different pets, drink different beverages
and smoke different brands of American cigarets [sic]. One other thing: in statement
6, right means your right.
Это все хорошо. Я нашел несколько кратких и опрятных способов решить эту проблему в Интернете, особенно с помощью программирования с ограничениями. Однако, что меня интересует, так это создание множества головоломок такого типа.
Делать больше
Очевидно, что матричное представление - логичный способ думать об этом. С каждой колонкой, содержащей человека, дом, что они пьют, какую машину они водят и т. Д.
Моя первоначальная мысль состояла в том, чтобы начать со случайно сгенерированной сетки, которая является полной (то есть решенной), а затем (каким-то образом) создать подсказки из решенной версии, которые однозначно идентифицируют ее. Каждый раз, когда что-то может быть определено, оно удаляется из сетки.
Срывая сайт, который я перечислил в начале, следующие "подсказки", которые можно использовать для решения сетки, могут быть следующего типа:
Человек / животное / растение живет / растет в данном доме.
Человек / животное / растение не живут / не растут в данном доме.
Человек / животное / растение живет в том же доме, что и другой человек / животное / растение.
Человек / животное / растение является прямым соседом другого человека / животного / растения.
Человек / животное / растение является левым или правым соседом другого человека / животного / растения.
Существует один дом между человеком / животным / растением и другим человеком / животным / растением.
Существует один дом между человеком / животным / планом и другим человеком / животным / растением слева или справа.
Есть два дома между человеком / животным / растением и другим человеком / животным / растением.
Есть два дома между человеком / животным / планом и другим человеком / животным / растением слева или справа.
Человек / животное / растение живет слева или справа от другого человека / животного / растения.
Вы можете увидеть, как они могут быть обобщены, расширены и т. Д.;
Сложность в том, что, используя мой подход (начиная с полной сетки и генерируя эти подсказки), я не уверен, как убедиться, что созданный мной набор подсказок обязательно приведет к целевой сетке.
Например, если вы говорите "Англичанин не владеет сосной", вы не можете решительно соединить две вещи в любой момент времени в загадке. И все же, если бы осталось только два дерева, которые можно было бы найти, это могло бы стать решающим доказательством.
Думаю ли я об этом совершенно неправильно? Лучшим подходом было бы создать сетку с некоторыми рандомизированными, заранее определенными известными элементами (т. Е. Красный дом посередине), а затем построить сетку, используя эти подсказки в качестве правил для построения?
Буду очень признателен за любые советы, статьи для чтения, методы программирования и т.д.!
6 ответов
Вот простой алгоритм, использующий ваш решатель:
Создайте случайный экземпляр головоломки.
Постройте набор C из всех возможных улик, которые относятся к этому экземпляру головоломки. (Существует конечное и на самом деле довольно небольшое количество возможных улик: например, если есть 5 домов, есть 5 возможных подсказок формы "Человек А живет в доме Б", 8 возможных подсказок формы "Человек А живет" рядом с домом "и т. д.)
Выберите случайную перестановку c1, c2,..., cn ключей в C.
Установите i = 1.
Если я > п, мы сделали. Множество C улик минимально.
Пусть D = C - { ci }. Запустите свой решатель на множестве D улик и подсчитайте количество возможных решений.
Если есть только одно решение, установите C = D.
Установите i = i + 1 и вернитесь к шагу 5.
(Вы можете ускорить это, удаляя ключи в пакетах, а не по одному, но это усложняет описание алгоритма.)
Я не совсем уверен в этом решении, но вот как я бы подошел к нему:
Начиная со случайного решения (т.е. зеленый дом содержит лак, который курит LM, красный дом содержит ирландец, который курит гвоздику и т. Д.). Вы можете посмотреть на это решение как на график отношений между утверждениями. где каждый элемент (полироль, красный дом и т. д.) связан со всеми остальными элементами либо "да", либо "нет края" (в нашем случае полироль подключается к теплице с "да" и к гвоздика с "без ребра" (среди многих других ребер этот начальный граф является полным, направленным графом)).
Теперь, если вы случайным образом убираете ребра, пока у вас не останется минимальный связный граф, у вас должен быть граф, представляющий разрешимую головоломку. переведите каждое ребро "да" в строку "foo is/do bar", а каждое отсутствие ребра в "foo is / not bar".
интуитивно это звучит как раз для меня. но опять же, это никоим образом не является формальным или общепризнанным способом сделать это и может быть совершенно неверным.
Вы также можете сделать это наоборот (что также поможет вам решить проблему):
- Генерация S, список всех возможных решений (т.е. таблиц).
- Создайте случайный факт f (например, у норвежца есть кот).
- Установить T = S
- Отфильтруйте из T все решения, которые нарушают f.
- Если |T| = 0, тогда переходите к 2 (факт противоречит предыдущему)
- Если |T| <| S | затем установите S = T и F.append (f) (факт еще не отражен в предыдущих фактах)
- IF | S | > 1, затем перейти к 2
После этого F будет список фактов, которые ведут к единственной таблице, оставшейся в S.
По общему признанию, это очень грубая сила, и, вероятно, не будет хорошо работать с таблицей 5X5 или более.
Интересно, что головоломка "Эйнштейн" (предполагаемые цитаты, все, что "умнее", как правило, присваивается Эйнштейну, возможно, имеет больше гламура), связана с алгоритмом генерации судоку (путем правильного перевода терминов), а также с кубиком Рубика (3x3x3) Алгоритм решения
В случае с судоку подсказки соответствуют уже назначенным номерам в сетке, а недостающая информация - пустым слотам.
В случае кубика Рубика (который я нахожу более интересным), ключи соответствуют симметриям куба (например, зеленый цвет находится рядом с красным цветом, вот так), а недостающие данные находят путем повторного выравнивания (решения) куб
Это грубый набросок, спасибо
Я думаю, что основа ответа Гарета Риса здравая, но я думаю, что аддитивный подход, а не субтрактивный, будет работать лучше.
Вы начинаете с полного набора потенциальных улик (C), пустого набора принятых улик (D) и пустого решения головоломки (S).
Затем вы выполняете следующий процесс до тех пор, пока S не станет жизнеспособным:
- Возьмите следующую подсказку (Ci ) у C.
- Обновите S, попытавшись решить головоломку с помощью Ci.
- С изменился? Если да, добавьте Ci к D; в противном случае откажитесь от него.
- Является ли S полным? Если да, вы можете остановиться и использовать D в качестве списка подсказок; в противном случае повторите с шага 1.
Это будет абсолютной гарантией отсутствия ненужных улик, потому что вы сохраните только те подсказки, которые помогут вам решить головоломку. И это, вероятно, будет намного быстрее, чем начинать с десятков (или сотен) улик и сокращать их до нескольких. (Также обратите внимание: с некоторыми изменениями вы можете легко изменить этот процесс, чтобы уменьшить сложность головоломки, добавив дополнительные подсказки даже после того, как S разрешима.)
Вот еще одна мысль - как только вы сгенерируете свою полную сетку, сфотографируйте ее на свой телефон (или продублируйте дизайн), прежде чем удалять элементы, пока вы предоставляете подсказки. Вы можете пройти половину задания и забыть, как выглядит оригинальная / окончательная схема, и можете избежать дезинформации ваших испытуемых / тестируемых.
Думая о создании одного на Пасху, похожий рисунок, 5 человек, 5 видов шоколада, 5 возрастов, 5 разных пасхальных шапок, 5 разных любимых напитков, мороженое и т. Д.