Слайд-пазл солвер — это программа, которая по любой решаемой стартовой позиции выдаёт последовательность ходов, ведущую к цели. Это инструмент с двумя аудиториями: игроки, которые застряли, и разработчики, которым нужно отгрузить слайд-пазл-приложение.
Эти две аудитории хотят очень разных вещей.
Почему игрокам солвер почти никогда не нужен
Если вы застряли на слайд-пазле, честное решение обычно не «запустить солвер». А одно из трёх:
- Выучите метод строки-и-столбца. Большинство сдающихся — это те, кто никогда не учил каноническую стратегию. (Начните с 8-puzzle, потом масштабируйтесь вверх.)
- Проверьте, что пазл решаем. Если решение никак не находится, приложение могло сгенерировать нерешаемую доску по ошибке. Быстро проверяется.
- Воспользуйтесь подсказкой, а не полным решением. Следующего одного хода обычно хватает, чтобы расстопориться. Приложения, дающие подсказки (наше — в Premium), обычно вычисляют один ход по запросу, а не целое решение.
Полное решение редко учит чему-то полезному, потому что солвер выдаёт оптимальную последовательность — обычно 52 хода для сложной 15-головоломки, — и наблюдение за 52 оптимальными ходами, проносящимися мимо на телефоне, не строит интуицию.
Подсказка — правильная единица. Если вам нужна подсказка, вам не нужен солвер.
Почему разработчикам он всегда нужен
Построить слайд-пазл-приложение — это взять на себя несколько обещаний:
- Каждый пазл решаем.
- Каждый пазл занимает примерно заданное число ходов (калибровка сложности).
- Каждый пазл может выдать подсказку по требованию.
Ни одно из этих обещаний не выполнить без работающего на фоне солвера.
Генерация «решаемо-по-построению» позволяет избежать запуска солвера на этапе генерации: идите назад от целевого состояния, применяя случайные допустимые ходы, и стартовая позиция гарантированно решаема. Большинство приложений, включая наше, делают именно так.
Калибровка сложности хочет, чтобы пазл был «интересным» — ни тривиальным (доска уже почти решена), ни истощающим (доска требует 60 ходов на 3×3). Стандартный приём — применить достаточно обратных ходов, чтобы оказаться около оптимального расстояния от цели — обычно 20–30 для 3×3, 40–60 для 4×4. Солвер проверяет расстояние после генерации.
Подсказки требуют солвера, который может выдать один хороший следующий ход за несколько сотен миллисекунд. Это быстрее, чем полное оптимальное решение, но всё равно требует реальной алгоритмической работы.
Какой солвер
Выбор зависит от размера доски:
| Доска | Рекомендуемый алгоритм | Время на решение |
|---|---|---|
| 3×3 | A* + Manhattan | < 1 мс |
| 4×4 | IDA* + walking distance | 10 мс – 1 с |
| 5×5 | IDA* + база шаблонов 5+5+5+9 | 100 мс – минуты |
| 6×6 | IDA* + большая база шаблонов | секунды – часы |
Для 3×3 даже brute-force BFS работает. К 4×4 нужна реальная эвристика, и манхэттенское расстояние — стандарт с 1980-х. К 5×5 нужны базы шаблонов. К 6×6 вы делаете исследовательскую работу.
Детали алгоритмов — в статье про солвер 15-головоломки и статье про солвер 8-puzzle. Сравнение алгоритмов — на странице слайдинг-пазл солвер.
На устройстве vs на сервере
У мобильных приложений со встроенным солвером есть два варианта реализации: выполнять локально или ходить на сервер.
Локальное выполнение — более честный выбор для уважающего приватность приложения. Солвер — это несколько сотен строк кода, базы шаблонов для 4×4 умещаются в несколько мегабайт, и современный телефон решает любую 15-головоломку заметно меньше чем за секунду. Нет причины отправлять состояние пазла на сервер — и отсутствие этой отправки — одна из вещей, отличающих спокойную игру для телефона от той, которой телеметрия нужна для работы.
Серверное — это когда разработчик хочет отслеживать, на каких пазлах люди застряли, или A/B-тестировать кривую сложности. Это реальные продуктовые причины, но они идут с ценой приватности и сетевой зависимостью. Приложения, которые не могут решить пазл оффлайн, — это приложения, которые не работают в самолёте.
Slide Puzzle решает полностью на устройстве. База шаблонов для 4×4 весит около 6 МБ и живёт внутри бандла приложения. Кнопка подсказки использует её напрямую. С телефона ни один запрос не уходит.
Прагматическая заметка
Если вы пришли сюда в поисках «сайта-солвера, куда я вставляю свою доску, и он говорит ответ» — такие есть, и обычно это веб-солверы для 8-puzzle. Они нормальны для 3×3. Для 4×4 и выше пользовательский опыт неуклюжий: ввести 16 чисел, посмотреть последовательность из 50 ходов, попытаться выполнить 50 конкретных ходов на физической доске. Никто не получает от этого удовольствия.
Реальные применения слайд-пазл солвера:
- Проверка собственной реализации в коде.
- Генерация корпуса тестовых досок.
- Вычисление подсказки внутри приложения.
Вне этого изучить метод строки-и-столбца быстрее.