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