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