«Слайдинг-тайл пазл» — это зонтичное имя. Под ним сидит полдюжины именованных пазлов, все разделяют одно правило (плитка может ехать только в соседнюю пустую клетку) и варьируют всё остальное: форму доски, число плиток, число пустых клеток, способны ли плитки вращаться. Эта статья — экскурсия по семейному древу.
Ветка квадратной сетки: N-пазлы
Основная линия семейства. Квадратная доска с N² − 1 нумерованными (или картиночными) плитками и одной пустой клеткой.
| Название | Доска | Плиток | Худшее оптимальное решение |
|---|---|---|---|
| 8-puzzle | 3×3 | 8 | 31 ход |
| 15-puzzle | 4×4 | 15 | 80 ходов |
| 24-puzzle | 5×5 | 24 | 152 хода |
| 35-puzzle | 6×6 | 35 | ~245 ходов |
| 48-puzzle | 7×7 | 48 | неизвестно (исследование) |
| 80-puzzle | 9×9 | 80 | неизвестно |
Одна и та же стратегия — собрать верхнюю строку, левый столбец, рекурсивно — работает на каждом размере в этом столбце. Большие доски — это просто более длительные партии, а не другие пазлы.
Именно эти пазлы имеет в виду большинство, когда говорит «слайд-пазл». Это и те, на которых бенчмаркируют свои алгоритмы специалисты по информатике.
Неквадратные сетки
Реже, но интересно:
Прямоугольные — доски 3×4, 4×5, 5×6. Некоторые коммерческие версии, включая деревянные XIX века, были прямоугольными. Та же стратегия работает; Г-образный угловой манёвр немного отличается на асимметричном краю.
Гексагональные — плитки на гексагональной сетке, шесть возможных соседей у каждой клетки вместо четырёх. Математически более позволительно (больше вариантов хода на состояние), психологически сбивает с толку. Ниша.
Треугольные — плитки на треугольной сетке. Ещё реже. Математика в порядке; геймплей неуклюжий.
Больше одной пустой клетки
Версия с одной пустой клеткой — стандарт. Существуют коммерческие пазлы с двумя и более пустыми клетками — самый знаменитый это Klotski и его родственники, где плитки разных размеров (1×1, 1×2, 2×2) скользят по доске с несколькими пустыми клетками. Klotski — стратегически другая игра: вы не пытаетесь выстроить плитки по порядку, а маневрируете конкретную плитку к выходу.
Klotski иногда относят к «слайдинг-тайл пазлам». На самом деле он не вполне часть семейства — другая цель, другая стратегия, другая математическая структура.
Скольжение плюс вращение
Соедините правило скольжения с механикой вращения и получите широкий ассортимент физических пазлов: венгерские кольца, некоторые продукты, родственные кубику Рубика, и так называемые пазлы «loopover». Они скрещиваются со слайд-пазлами, но стратегически снова другие.
Для игрока, пришедшего из 15-головоломки, ближайший такой родственник — Rubik's 15, маленькая физическая игрушка с раскладкой 15-головоломки, но с ограничением, что соседние пары можно ещё и менять местами.
Что связывает семейство
Два математических факта делают семейство слайд-пазлов когерентным:
-
Структура графа состояний. Каждый вариант моделируется как граф: узлы — состояния доски, рёбра — допустимые ходы. Оптимальное решение — поиск кратчайшего пути в этом графе. Граф огромен, но «хорошо себя ведёт», поэтому эвристический поиск так успешен.
-
Инварианты чётности. У большинства вариантов — включая все стандартные N-пазлы — есть правило чётности, которое разделяет достижимые состояния пополам. Половина достижима из цели; половина — нет. Приложения, генерирующие случайные стартовые позиции, либо предварительно проверяют чётность, либо генерируют, идя назад от цели.
Во что играть, по настроению
Если вы ничего из этого ещё не пробовали:
- Начните с 8-puzzle на десять минут. Достаточно быстро, чтобы впитать правило и попробовать стратегию.
- Перейдите к 15-головоломке, когда 8 наскучит. Это канонический опыт.
- Попробуйте 24-головоломку, когда захочется долгого посиделочного.
- Попробуйте Klotski, если хочется другого слайд-пазла — та же механика, другая цель.
- Попробуйте гексагональные сетки, если хочется снова почувствовать себя новичком. Они умерят пыл.
Большинство современных приложений, наше включительно, везут 8, 15, 24 и 35-пазлы в одном месте. Это центральный ствол семейства, и именно на центральном стволе играют почти все.