Я создаю игру-головоломку, в которую можно играть вручную для простых уровней, но чтобы их решать с помощью компьютерных программ, для более сложных. Головоломка представляет собой заливку на шестиугольной доске. Вы можете попробовать прототип здесь.
(источник: hacker.org)
Вот как работает головоломка: выбирая цвет сверху, вы выполняете заливку, начиная с верхней левой плитки. Это постепенно превращает доску в сплошной цвет. Задача состоит в том, чтобы сделать это за определенное количество ходов.
Я создал несколько головоломок, похожих на эту, и ключевым моментом является использование алгоритма, который генерирует доски, которые сложно решить, не зная, как они были созданы. Например, здесь мы могли бы создать доску, изменив заливку заливкой: работая в обратном направлении от твердой доски, пока она не будет разгружена. Мы знаем, сколько шагов для этого потребовалось, и можем установить это как нижнюю границу решения.
Проблема, с которой я столкнулся, заключается в том, что когда я пробую этот подход, моя верхняя граница слишком высока. Решить загадку за такое количество ходов становится тривиально, даже если передвигаться случайным образом.
Подход, который не является решением, заключается в создании случайной доски, а затем ее оптимальном решении и установке ее в качестве цели. Дело в том, чтобы создать головоломку, решение которой оптимальным образом занимает время NP или, по крайней мере, сложное P.
Так что я ищу алгоритм, который может генерировать чрезвычайно жесткие доски, решение которых по мере их увеличения становится серьезной проблемой.
