24-головоломка — это то, что получается, если у 15-головоломки добавить строку и столбец. Двадцать четыре нумерованных плитки на доске 5×5, одна пустая клетка, та же механика: задвигать соседние плитки в пустоту, пока числа не выстроятся по порядку.
Это очевидный следующий шаг после 4×4 — и это действительно другая игра.
Арифметика «одна доска побольше»
Пространство состояний взрывается:
| Доска | Клеток | Плиток | Достижимых состояний | Худшее решение |
|---|---|---|---|---|
| 3×3 (8-puzzle) | 9 | 8 | 181 440 | 31 ход |
| 4×4 (15-puzzle) | 16 | 15 | ~10,46 × 10¹² | 80 ходов |
| 5×5 (24-puzzle) | 25 | 24 | ~7,76 × 10²⁴ | 152 хода |
| 6×6 (35-puzzle) | 36 | 35 | ~1,86 × 10⁴¹ | ~245 ходов |
Каждый шаг примерно возводит пространство состояний в квадрат. Самая сложная 24-головоломка требует почти вдвое больше ходов, чем самая сложная 15-головоломка — и это оптимальное число ходов. Человек, решающий методом строки-и-столбца, обычно делает 200–300 ходов.
Время решения вручную
Уверенный игрок, освоивший 15-головоломку, обычно тратит на 24-головоломку 10–20 минут в первых попытках. К десятой партии тот же человек укладывается в 6–10 минут.
Стратегия та же, что на меньших досках: собрать верхнюю строку, левый столбец, рекурсивно перейти к меньшему подпазлу. Только теперь это делается дважды: собираете строку 1 и столбец 1, потом строку 2 и столбец 2 оставшегося 4×4, потом вложенный 3×3. Каждый слой снимаемой шелухи использует Г-образный угловой манёвр.
Что становится сложнее
Две конкретные вещи плохо масштабируются:
Нагрузка на рабочую память. На 3×3 одновременно держится одна стратегическая цель. На 5×5 вы жонглируете «я ставлю 5 в правый верхний угол», одновременно не задевая плитки 1–4 и не загоняя себя в угол. Когнитивная нагрузка растёт.
Г-образный манёвр удлиняется. На 3×3 поставить последнюю плитку строки в угол — это примерно 5 субходов. На 5×5 тот же приём занимает 10–12 субходов и уходит на две клетки в глубину. Новички часто роняют уже зафиксированную строку, потому что не учли, как далеко простирается манёвр.
Что остаётся прежним
На удивление много. Структура стратегии в точности та же, что на 3×3. Эндшпиль — рекурсивный 3×3 — идентичный. Если вы знаете меньшие доски, 5×5 — это длинная версия знакомого, а не другая игра.
Эта рекурсивная согласованность — одна из причин, почему математикам нравится семейство слайд-пазлов: метод «строка-и-столбец» работает на любом размере.
Почему солверы здесь спотыкаются
Для оптимального решения компьютером 24-головоломка — это размер, на котором манхэттенского расстояния перестаёт хватать. A* и IDA* с манхэттенской эвристикой решают любую 15-головоломку за секунды, но уходят в часовой таймаут на самых сложных 24-головоломках.
Решение, найденное Корфом и Фелнером в начале 2000-х, — аддитивные базы шаблонов: предварительно рассчитать оптимальную стоимость перестановки подмножеств плиток (например, разбиение 5+5+5+9), потом на этапе поиска складывать стоимости подмножеств. С удачным разбиением любая 24-головоломка решается за секунды даже оптимально. Подробности — в статье про солвер 15-головоломки.
Премиум-территория
В большинстве приложений 5×5 живёт за пэйволом. Причина простая: эта доска создаёт намного более длинные сессии, чем 3×3 или 4×4, поэтому приложения относятся к ней как к «дополнительной ценности», а не к функции бесплатного слоя. Slide Puzzle устроен так же — 5×5 входит в Premium вместе с 6×6 и неограниченным импортом фотографий.
Это огораживание не злонамеренное. 5×5 — это другой опыт, длинный тихий вечер с одной доской, и он дороже в производстве (артворк должен быть резче, алгоритмы аккуратнее с решаемостью).
Когда играть в 24-головоломку
Доска 5×5 — для тех вечеров, когда хочется неподвижно посидеть пятнадцать минут и больше ни о чём не думать. Не для автобуса, не для очереди, не для чайника. Для после чайника.
Это также размер, на котором фото-пазлы становятся требовательными: фотография должна читаться при нарезке в 25 кусков, и многие в остальном хорошие фото разваливаются. 24-головоломка научила меня тому, какие фото работают, а какие нет.
Если 15-головоломки кажутся быстрыми, это следующий шаг. Если 5×5 кажется долгим — следующий шаг после неё это 35-головоломка, 6×6.