У пятнашек 3×3 крошечный размер и непропорционально большая репутация. Восемь квадратных плиток с номерами от 1 до 8 на доске 3×3. Одна клетка пустая. Задача — задвигать плитки в пустую клетку по одному ходу за раз, пока номера не выстроятся по порядку: обычно 1‑2‑3 в верхней строке, 4‑5‑6 в средней, 7‑8‑пусто в нижней.
Это самый маленький член семейства N-пазлов. 15-головоломка известнее, но именно с 3×3 начинают все — дети, студенты и исследователи алгоритмов поиска.
Как работает один ход
Пустая клетка — единственное, чем вы реально управляете. Можно сдвинуть только ту плитку, которая находится прямо над, под, слева или справа от пустой клетки. Диагональные ходы запрещены. Поднимать плитки и переставлять их нельзя. Каждый ход — это одна соседняя плитка, сдвигающаяся на одну клетку в пустоту, и теперь пустая клетка там, где была эта плитка.
Это маленькое правило и делает пазл интересным. Всё время кажется, что у вас есть один-два полезных хода, но при этом на доске 3×3 прячется 181 440 решаемых конфигураций. (Вторая половина — нерешаемые — описана в отдельной статье о чётности.)
Стандартная стратегия для решения вручную
Приём, на который большинство наталкивается само, и который масштабируется до 4×4, 5×5 и дальше, такой:
- Сначала собирайте верхнюю строку — поставьте 1, 2, 3 на свои места и больше их не трогайте.
- Затем — левый столбец — поставьте 4 и 7. Теперь верхняя строка и левый столбец зафиксированы.
- Оставшийся квадрат 2×2 с тремя плитками и пустой клеткой имеет всего два состояния: решённое или одна плитка не на месте. Если не на месте — внутри 2×2 это уже не починить из решаемого исходного положения, нужно вернуться к остальной части пазла. (Поэтому чётность и важна.)
Сложность — поставить последнюю плитку строки или столбца. Чтобы убрать 3 в правый верхний угол, обычно нужно сначала сдвинуть 2 в правый верхний, потом подвести 3 под неё, потом провернуть пару на место. Этот маленький Г-образный манёвр — тот же приём, который вы будете использовать на 15-головоломке, 24-головоломке и на доске любого размера.
Оптимальные решения короткие
Самый сложный 8-puzzle решается за 31 ход. Это по всем 181 440 стартовым позициям — худшая отдалена от цели не больше чем на 31 одиночный сдвиг.
Средняя позиция требует около 22 ходов. Компьютер с алгоритмом A* и хорошей эвристикой находит оптимальный ответ за миллисекунды. Вручную человек, знающий приём «сначала верхняя строка», решает любые пятнашки 3×3 меньше чем за минуту, как только усвоит паттерн.
Почему за это любят учёные
Пятнашки 3×3 — стандартный вводный бенчмарк для эвристического поиска. Доска достаточно мала, чтобы перебрать целиком, достаточно велика, чтобы грубая сила была расточительна, и достаточно богата, чтобы показать разницу между двумя классическими эвристиками:
- Misplaced tiles — сосчитать, сколько плиток не на своём месте. Дёшево вычисляется, слабый ориентир.
- Манхэттенское расстояние — для каждой плитки сложить разницу строк и столбцов до цели. Более сильный ориентир, всё ещё дешёвый.
Учебная реализация A* с манхэттенским расстоянием решает любые пятнашки 3×3 за микросекунды. Поднимитесь к 15-головоломке — и понадобятся аддитивные базы шаблонов, чтобы оставаться быстрым: это уже другой разговор, и он в статье про солвер 15-головоломки.
Когда играть в пятнашки 3×3
Доска 3×3 — это тихое удовольствие. Думать особо не о чем, условие победы очевидно, и партия занимает минуту-две. Это правильный размер для:
- Ребёнка, который учится «планировать на ход вперёд».
- Взрослого, который едет в автобусе и не хочет долгого пазла в руках.
- Тренировочного раунда перед переходом к 15-головоломке.
Это также размер, который почти всегда бесплатен в слайд-приложениях, включая наше, — большие доски обычно за пэйволом, потому что занимают дольше и создают больше сессий, а 3×3 — это онбординг для всех.
Что меняется на 4×4
В стратегии — ничего. Соберите верхнюю строку, затем левый столбец, рекурсивно перейдите к оставшемуся 3×3. Меняется время: пятнашки 3×3 за 30 секунд становятся 15-головоломкой за 5–10 минут. Дальше числа только хуже — 5×5 и 6×6 требуют серьёзного терпения.
Если 3×3 через неделю наскучили — это сигнал переходить выше.