Как пользоваться решателем
Инструмент выше оптимально решает любую решаемую доску 3×3 или 4×4 — ответ, который он возвращает, это кратчайшая возможная последовательность ходов, а не просто рабочая.
- Нажмите Изменить и введите свою доску: пронумеруйте плитки так, как они должны читаться в собранном пазле (левая верхняя — 1), и расставьте их туда, где они стоят сейчас. Решаете пазл с картинкой — из игры, фотоприложения, деревянной игрушки? Сначала мысленно пронумеруйте собранную картинку слева направо, сверху вниз.
- Нажмите Решить. Список ходов появляется мгновенно для 3×3 и за считанные мгновения для 4×4.
- Повторяйте ходы на своём реальном пазле, по одному.
Если решатель говорит, что доска нерешаема, это не баг — ровно половину всех расстановок собрать невозможно, и никакая последовательность допустимых ходов их не исправит. Хотите освоить технику, а не зачитывать ходы? Метод для человека — здесь.
Как работает решатель слайдинг-пазла — сравнение шести алгоритмов
Если вы реализуете солвер слайдинг-пазла и не знаете, какой алгоритм выбрать, эта статья сравнивает шесть известных по скорости, памяти, сложности кода и удобному размеру доски. Ответы разные для 3×3, 4×4 и 5×5.
1. Breadth-first search (BFS)
Самый глупый корректный алгоритм. Исследовать состояния по уровням, пока не найдёте цель.
- Время — экспоненциально по глубине решения. Для 8-puzzle завершается за долю секунды. Для 15-головоломки не завершается до того, как у компьютера закончится ОЗУ.
- Память — держит всё посещённое в памяти. Десятки миллионов состояний для сложных 15-puzzle.
- Сложность кода — двадцать строк.
- Вердикт — нормально для 3×3, бесполезно дальше.
2. A* с манхэттенским расстоянием
Первый настоящий алгоритм. Та же структура, что у BFS, но состояния достаются из приоритетной очереди, упорядоченной по f = g + h, где h — это манхэттенская эвристика.
- Время — миллисекунды для 8-puzzle, секунды-минуты для 15-головоломки.
- Память — всё ещё держит исследованное в памяти; терпимо для 8, болезненно для 15.
- Сложность кода — пятьдесят строк, в основном инфраструктура очереди.
- Вердикт — правильный инструмент для 8-puzzle. Пограничный для 15.
3. A* с Manhattan + linear conflict
Добавьте 2 хода в эвристику за каждую пару плиток в одной строке, обе принадлежащих этой строке, но в неправильном порядке (аналогично для столбцов). Им придётся разойтись, что Manhattan не видит.
- Время — обычно на 5–15% быстрее plain Manhattan A*.
- Память — без изменений.
- Сложность кода — шестьдесят строк.
- Вердикт — строго лучше plain Manhattan A*. Всегда используйте.
4. IDA* с Manhattan + linear conflict
Iterative-deepening A*. Делает DFS с ограничением по f-стоимости, поднимая порог каждую итерацию. Меняет память на время через повторное исследование.
- Время — чуть медленнее на узел, чем A*, из-за повторов, но меньшее давление на память обычно побеждает на сложных 15-puzzle.
- Память — O(глубина), не O(исследованных состояний). Это и есть выигрыш.
- Сложность кода — восемьдесят строк (рекурсивный DFS, управление порогом).
- Вердикт — правильный инструмент для 4×4. Стандарт со времён Корфа 1985.
5. IDA* с walking distance
Walking distance — более плотная эвристика. Предварительно посчитайте, для каждой конфигурации плиток проекции только на строки, минимальное число операций «своп-строки», чтобы поставить каждую плитку в правильную строку. То же для столбцов. Сложите.
Она ловит то, чего Manhattan не видит: плитки в одной строке, «дерущиеся» за один слот.
- Время — обычно в 2 раза быстрее Manhattan + linear conflict на сложных 15-puzzle, потому что эвристика плотнее и IDA* отсекает больше.
- Память — добавляет небольшую предрассчитанную таблицу (~500 КБ для 4×4).
- Сложность кода — 150 строк. Предрасчёт — BFS по сокращённому пространству состояний.
- Вердикт — правильный инструмент для 4×4, если есть инженерный бюджет. Первое нетривиальное улучшение.
6. IDA* с аддитивными непересекающимися базами шаблонов
Сильнейшая известная эвристика для слайдинг-пазлов. Разбейте плитки на непересекающиеся группы (распространённое разбиение 15-puzzle — 7+8 или 5+5+5). Для каждой группы предварительно посчитайте стоимость перестановки плиток группы в их целевые позиции по всем возможным конфигурациям этой группы. Во время поиска сложите вклад каждой группы.
- Время — решает самую сложную 15-puzzle за миллисекунды. Решает случайные 24-puzzle за секунды.
- Память — значительная. Разбиение 7+8 для 15-puzzle — около 1 ГБ. 5+5+5+9 для 24-puzzle — около 4 ГБ. Память доминирует в инжиниринге.
- Сложность кода — 300+ строк. Предрасчёт использует ретроградный BFS по пространству состояний группы и составляет основную часть работы.
- Вердикт — правильный инструмент для 5×5 и 6×6. Излишество для 3×3.
Сводные рекомендации
Если вы пишете солвер сегодня:
- Для 3×3 — A* с Manhattan + linear conflict. Всё остальное — переинжиниринг.
- Для 4×4 — IDA* с walking distance. Базы шаблонов дают маргинальный выигрыш на этом размере; инженерная сложность того не стоит.
- Для 5×5 — IDA* с аддитивными базами шаблонов (5+5+5+9 стандарт). Без баз вы будете уходить в таймаут на самых сложных инстансах.
- Для 6×6 (35-головоломки) те же алгоритмы могут решать случайные инстансы, но самые сложные случаи всё ещё открытые исследовательские вопросы. Большинство приложений не пытаются.
А машинное обучение?
Разумный вопрос в 2026 году. Нейросетевые эвристики изучают как минимум с 2014 года, и они могут давать быстрые эвристики для слайдинг-пазлов. Подвох в том, что они обычно не допустимы — могут переоценивать, что означает, что получившийся алгоритм больше не гарантирует оптимальность. Для разработчиков приложений, которым нужны гарантированно оптимальные решения для калибровки сложности, классические базы шаблонов остаются правильным инструментом.
Для исследовательского интереса базы шаблонов, обученные нейросетью, дают небольшое ускорение на самых сложных 15-puzzle инстансах. Полезно для академических статей, маргинально для отгружаемого ПО.
Что попадает в реальное приложение
Отгружаемое мобильное приложение, которому нужен солвер для подсказок, почти всегда приходит к:
- IDA* + walking distance для 4×4.
- IDA* + небольшая база шаблонов для 5×5.
- Один вызов на «один следующий ход» из кнопки подсказки.
- Всё работает на устройстве. Весь солвер — несколько сотен килобайт кода плюс несколько мегабайт предрассчитанных таблиц.
Это правильный прагматичный стек для спокойного телефонного приложения. Кнопка подсказки в Slide Puzzle работает именно так.