В чем моя проблема:
У Раймонда Смалляна есть загадка, которая работает примерно так: вы находитесь в комнате с множеством дверей. За некоторыми из этих дверей есть женщины; за остальными стоят тигры. Ваша цель состоит в том, чтобы выбрать одну из правильных дверей (те, что с дамами). На каждой двери есть признак того, что говорит что - то вроде Там есть дама за этой дверью или Eсть льва за двери II и VI и так далее. Теперь у вас также есть некоторая дополнительная информация, например, Только один из знаков говорит правду или Знак на двери правдив, только если за этой дверью есть дама и так далее. Например, первая головоломка выглядит так:
Есть две двери с одним знаком каждый. Один из признаков верен, другой ложен:
--------------------- --------------------- | DOOR I | | DOOR II | | There's a lady in | | In one of those | | this room and a | | rooms, there's a | | a tiger in the | | lady, in the other | | other one | | one there's a tiger | --------------------- ---------------------За какой дверью женщина?
Теперь перейдем к теме этого вопроса: я ищу возможные способы автоматического создания таких головоломок. (Далеко) цель состоит в том, чтобы создать алгоритм, который требует в качестве параметров количество дверей (и, возможно, сложность получившейся головоломки) и создает соответствующие тексты для дверей.
Что я уже пробовал:
Не так много, так как я не знаю, с чего начать. Легко создать шаблон для текста на знаках, а также легко произвольно назначить истинные и ложные утверждения тем знакам, которые соответствуют правилу истинного-ложного, которое вы используете (например, только один знак говорит правду ). Но это та часть, где это становится сложным: как создать головоломку, которая разрешима и имеет уникальное решение ? Моя первая идея состояла в том, чтобы создать случайную головоломку и использовать обратный поиск для поиска решений. Но в этом случае может пройти очень много времени, пока алгоритм наконец не найдет рабочий набор признаков. Кроме того, таким образом, вы не можете легко определить, насколько сложна данная головоломка.
Итак, подведем итог: есть ли у вас какие-либо идеи, полезные ссылки и т. Д.? Любая помощь приветствуется, я не ожидаю, что кто-нибудь опубликует идеальное и полное решение для моей проблемы.
(Примечание: я изначально задавал следующий вопрос о stackoverflow, но там мне сказали, что я с большей вероятностью получу ответ здесь!)
Ответы:
Генерация текста - это отдельная проблема, но для небольшого количества дверей можно использовать карту Карно. Выберите случайную ячейку, которая будет истинной, все остальные будут ложными, затем используйте соответствующий алгоритм, чтобы найти наиболее эффективное логическое выражение, которое соответствует этой карте, например
http://www.codeproject.com/Articles/37031/Karnaugh-Map-Minimizer-3-Variables
источник