CrazySage
@CrazySage
C++ developer

Как сгенерировать загадку эйнштейна?

Многие наверное знают в той или иной форме загадку Эйнштейна, про улицу, на которой дома шести разных цветов, где живут жильцы шести разных национальностей, пьющие разные напитки и т.д. Возник вопрос - а как сгенерировать такую задачу, в варианте, когда надо восстановить все поля? То есть сделать набор подсказок, достаточный для описания всего состояния поля, и близкий к минимальному. Хотя бы с какой области математики начать курить?
  • Вопрос задан
  • 950 просмотров
Пригласить эксперта
Ответы на вопрос 2
gbg
@gbg
Любые ответы на любые вопросы
Комбинаторику вместе с теорией графов. И немножко математической логики.
Ответ написан
Комментировать
Mrrl
@Mrrl
Заводчик кардиганов
Математика здесь не нужна, достаточно программирования.
Посмотрите на игрушку Sherlock: www.kaser.com/sherwin.html
Там алгоритм решения полностью открыт: есть трёхмерный битовый массив "может ли в доме A признак B иметь значение C", и в каждый момент решения найдётся подсказка, исключающая один из вариантов. Так что вам нужно сначала сгенерировать любой набор подсказок, приводящий к решению по этому алгоритму ("если зашли в тупик - добавим ещё подсказку"), а потом исключать из полученного набора те подсказки, без которых задачу можно решить (исключаете по одной и пытаетесь решить). Учтите, что подсказки есть разной силы, и чтобы не получилось огромного набора из "A не сосед B", надо соблюдать баланс, добавив (лучше, сначала, но не обязательно) несколько более сильных подсказок.
Лучше сгенерировать сотню-другую наборов заранее, а потом применять их, перемешивая признаки и значения в случайном порядке.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы