ChromaOracle находит кратчайшее возможное решение для любой головоломки с сортировкой по цветам с помощью алгоритма под названием BFS (поиск в ширину). Вместо того чтобы гадать или использовать эвристику, решатель систематически исследует каждую возможную последовательность ходов, начиная с самых коротких, пока не найдет ту, которая решает головоломку. Это гарантирует, что возвращаемое решение содержит минимально возможное количество ходов. Ниже описано, как это работает, — как для любознательных игроков, так и для технически подкованных читателей.
Головоломка как задача поиска
Каждую головоломку с сортировкой по цветам — будь то Water Sort, Ball Sort или любой другой вариант — можно описать как задачу поиска. Игровое поле в любой момент времени представляет собой «состояние»: определенное расположение цветов во всех пробирках. Каждое допустимое переливание или ход переводит одно состояние в другое. Решить головоломку — значит найти последовательность ходов, которая переводит начальное состояние в целевое состояние, где каждая пробирка содержит только один цвет или пуста.
Представьте это в виде карты. Каждый перекресток — это состояние. Каждая дорога между перекрестками — это ход. Начальное состояние — это место, где вы находитесь сейчас. Целевое состояние — пункт вашего назначения. Задача решателя — найти кратчайший путь.
Что такое BFS (поиск в ширину)?
BFS (поиск в ширину) — это метод исследования этой карты состояний в строго определенном порядке: он проверяет все состояния, находящиеся в одном ходе от старта, затем все состояния в двух ходах, затем в трех и так далее. Алгоритм равномерно расходится во всех направлениях, слой за слоем.
Именно такой послойный подход гарантирует оптимальность. Поскольку BFS исследует все решения из пяти ходов перед любым решением из шести ходов, при первом достижении целевого состояния он гарантированно находит кратчайший путь. Не существует более короткого пути, который он мог бы пропустить, так как все более короткие варианты уже были проверены.
Процесс устроен следующим образом:
- Начать с начального состояния игрового поля.
- Сгенерировать каждый возможный ход из этого состояния. Каждый ход создает новое состояние поля.
- Проверить, является ли какое-либо из этих новых состояний решенным состоянием. Если да, вернуть последовательность ходов.
- Если нет, добавить все новые состояния в очередь и повторить шаг 2 для следующего состояния в очереди.
- Продолжать до тех пор, пока не будет найдена цель или не будут исследованы все достижимые состояния.
Если очередь становится пустой до того, как решение найдено, головоломка является нерешаемой, и решатель немедленно сообщает об этом.
Представление пространства состояний
Чтобы BFS работал эффективно, решателю необходим способ компактного представления каждого состояния игрового поля, а также обнаружения того, что состояние уже было посещено. ChromaOracle представляет каждую пробирку как стек цветов, а все поле целиком — как коллекцию этих стеков.
Чтобы не исследовать одно и то же состояние дважды (что привело бы к пустой трате времени и памяти), решатель создает канонический ключ для каждого состояния. Этот ключ представляет собой нормализованное строковое представление игрового поля, которое считает одинаковые конфигурации одним и тем же состоянием независимо от порядка пробирок. Если на двух полях находятся одинаковые пробирки с одинаковым содержимым, но расположенные в разном порядке слева направо, они создают один и тот же ключ и распознаются как дубликаты.
Такая дедупликация критически важна. Без нее решатель посещал бы одни и те же позиции миллионы раз, что сделало бы его работу непрактично медленной. С ней же решатель обрабатывает каждое уникальное состояние только один раз.
Почему BFS гарантирует кратчайшее решение
Эта гарантия обеспечивается порядком исследования. BFS обрабатывает состояния строго по их расстоянию от старта, измеряемому в количестве ходов. Каждое состояние на расстоянии N обрабатывается перед любым состоянием на расстоянии N+1. Таким образом, в первый раз, когда решатель достигает целевого состояния, он делает это по пути длины N, и пути меньшей длины не существует, так как все более короткие пути уже были полностью исследованы.
Это математическое свойство алгоритма, а не эвристика или приближение. Решение, возвращаемое BFS, является доказуемо оптимальным.
Сравнение BFS и DFS
ChromaOracle также поддерживает DFS (поиск в глубину) в качестве альтернативного алгоритма. DFS работает по-другому: вместо исследования слой за слоем он следует по одному пути как можно глубже перед тем, как вернуться назад.
Компромиссы заключаются в следующем:
- BFS находит кратчайшее решение, но использует больше памяти, поскольку должен одновременно хранить все состояния на текущем уровне глубины.
- DFS во многих случаях находит решение быстрее и использует меньше памяти, но это решение может не быть кратчайшим. Он возвращает первый попавшийся подходящий путь, который может быть гораздо длиннее, чем необходимо.
Для большинства игроков лучшим выбором будет BFS — ведь вам нужно минимальное количество ходов. DFS полезен, когда вам нужно быстро получить любое решение или когда головоломка настолько велика, что BFS не хватает памяти.
Как работает Загадочный режим
Одной из самых отличительных особенностей ChromaOracle является Загадочный режим, разработанный для головоломок со скрытыми или неизвестными цветами. Во многих играх-головоломках на некоторых позициях в пробирке вместо цвета отображается вопросительный знак, а настоящий цвет раскрывается только тогда, когда этот слой оказывается на самом верху пробирки.
ChromaOracle справляется с этим с помощью анализа перестановок:
- Решатель определяет все позиции, отмеченные как неизвестные.
- Он генерирует каждое возможное распределение цветов по этим позициям, которое соответствует правилам головоломки — каждый цвет должен встречаться правильное количество раз.
- Он решает каждую полученную головоломку независимо с помощью BFS.
- Он анализирует все наборы решений, чтобы найти ходы, которые безопасны независимо от того, какими окажутся скрытые цвета.
Это называется поиском «общего префикса» — самой длинной последовательности ходов, которая присутствует в начале каждого решения для всех возможных вариантов распределения цветов. Гарантируется, что эти ходы будут правильными независимо от того, какие цвета скрываются под неизвестными.
Этот подход превращает проблему неопределенности в задачу исчерпывающего анализа. Вместо того чтобы гадать, решатель рассматривает все возможности и сообщает вам, какие именно ходы не несут в себе риска.
Производительность и практические ограничения
Пространство состояний головоломки с сортировкой по цветам растет экспоненциально с увеличением количества пробирок и цветов. Простая головоломка с пятью цветами может иметь несколько тысяч достижимых состояний. Сложная головоломка с двенадцатью цветами может иметь миллионы.
ChromaOracle работает полностью в вашем браузере с использованием TypeScript. Для большинства головоломок (примерно до десяти цветов) работа BFS завершается менее чем за секунду. Решение более крупных головоломок может занять несколько секунд. Чрезвычайно крупные конфигурации могут превысить лимиты памяти браузера, и в этом случае лучшим вариантом становится DFS.
Решатель выполняет исключительно вычисления без сетевых запросов. Данные вашей головоломки никогда не покидают ваше устройство, а скорость решения зависит только от вычислительной мощности устройства.
Архитектура движка
Для читателей, интересующихся технической реализацией, движок решателя ChromaOracle организован в виде специализированных модулей:
- Container — представляет отдельную пробирку как стек цветов, обрабатывая запросы на добавление (push), извлечение (pop) и получение верхнего цвета.
- Collection — представляет все игровое поле целиком, генерирует все возможные ходы из текущего состояния и создает канонические ключи для дедупликации.
- Search — реализует алгоритмы BFS и DFS, управляя очередью или стеком, а также множеством посещенных состояний.
- Strategy — координирует анализ нескольких решений, находя все решения и вычисляя общие префиксы для Загадочного режима.
- Validation — проверяет корректность конфигурации головоломки перед началом решения.
Движок не зависит от каких-либо фреймворков. Это чистый TypeScript, который можно полностью протестировать изолированно и перенести в любую среду выполнения JavaScript.
Часто задаваемые вопросы
Почему решение некоторых головоломок в ChromaOracle иногда занимает больше времени?
Время решения зависит от размера пространства состояний, который определяется количеством цветов, пробирок и пустых слотов. Большее количество цветов и меньшее количество пустых пробирок означает большее число возможных состояний для исследования. Головоломка с двенадцатью цветами и одной пустой пробиркой имеет значительно большее пространство состояний, чем головоломка с четырьмя цветами и тремя пустыми пробирками.
Может ли решатель не найти решение?
Если решение существует, BFS всегда его найдет. Если работа BFS завершается без нахождения решения, это означает, что головоломка математически нерешаема — никакая последовательность допустимых ходов не может привести к целевому состоянию. ChromaOracle четко сообщает об этом, чтобы вы знали, что головоломка именно невыполнима, а не просто сложна.
Всегда ли решение BFS является наилучшим из возможных?
Да. BFS гарантирует кратчайшее решение с точки зрения количества ходов. Не существует допустимого решения с меньшим количеством ходов, чем то, которое возвращает BFS. Это математическое свойство алгоритма.
Как Загадочный режим определяет, какие ходы безопасны?
Загадочный режим решает головоломку для каждого возможного варианта распределения скрытых цветов, а затем сравнивает все полученные решения. Ход помечается как безопасный только в том случае, если он присутствует в оптимальном решении для абсолютно каждой возможности. Это означает, что ход будет правильным независимо от того, какими окажутся скрытые цвета.