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

Question

[Gleb Igumnov]

Многие наверное знают в той или иной форме загадку Эйнштейна, про улицу, на которой дома шести разных цветов, где живут жильцы шести разных национальностей, пьющие разные напитки и т.д. Возник вопрос - а как сгенерировать такую задачу, в варианте, когда надо восстановить все поля? То есть сделать набор подсказок, достаточный для описания всего состояния поля, и близкий к минимальному. Хотя бы с какой области математики начать курить?

Answer 1

[Армянское Радио]

Комбинаторику вместе с теорией графов. И немножко математической логики.

Answer 2

[Mrrl]

Математика здесь не нужна, достаточно программирования.
Посмотрите на игрушку Sherlock: www.kaser.com/sherwin.html
Там алгоритм решения полностью открыт: есть трёхмерный битовый массив "может ли в доме A признак B иметь значение C", и в каждый момент решения найдётся подсказка, исключающая один из вариантов. Так что вам нужно сначала сгенерировать любой набор подсказок, приводящий к решению по этому алгоритму ("если зашли в тупик - добавим ещё подсказку"), а потом исключать из полученного набора те подсказки, без которых задачу можно решить (исключаете по одной и пытаетесь решить). Учтите, что подсказки есть разной силы, и чтобы не получилось огромного набора из "A не сосед B", надо соблюдать баланс, добавив (лучше, сначала, но не обязательно) несколько более сильных подсказок.
Лучше сгенерировать сотню-другую наборов заранее, а потом применять их, перемешивая признаки и значения в случайном порядке.