Каждый слайдинг-блок пазл подчиняется одному закону: фигуры скользят в пустое пространство, и ничто не вращается, не прыгает, не поднимается с доски. Под этим законом живут два семейства, которые играются совершенно по-разному. Понять, какое из них у вас в руках, — половина стратегии.
Семейство первое: одинаковые плитки, отсортируй их
Семейство слайдинг-тайл пазлов. Все фигуры 1×1, одна клетка пуста, и цель — расставить плитки по порядку: цифры по возрастанию или собранная картинка.
| Пазл | Доска | Зачем |
|---|---|---|
| 8-puzzle | 3×3 | десятиминутное знакомство |
| 15-puzzle | 4×4 | каноничный |
| 24-puzzle | 5×5 | посиделки подольше |
| 35-puzzle | 6×6 | тренировка терпения |
У этого семейства есть известный, изучаемый метод — собрать верхнюю строку, потом левый столбец, рекурсивно перейти к оставшейся меньшей доске, докрутить последний блок 3×2 ротацией. Полный разбор здесь. Есть и знаменитая ловушка: ровно половина всех расстановок нерешаема — поэтому честные приложения перемешивают, идя ходами назад от цели.
Семейство второе: разные блоки, выведи один
Здесь у фигур разные размеры — 2×2, 1×2, 1×1 — и цель не порядок, а побег: провести один назначенный блок к выходу.
Klotski — классика: доска 4×5, блок-герой 2×2 и эскорт стражей и пешек, который надо распутать. Стандартный старт требует минимум 81 ход. В Китае его знают как Huarong Dao, во Франции как L'âne rouge, по-русски — «клоцки» или «Красный осёл»; вся история — в нашем гиде по Klotski.
Rush Hour — современная коммерческая звезда: легковушки (1×2) и грузовики (1×3), запертые в сетке 6×6, каждая машина скользит только вдоль своей оси, а красная машина должна добраться до выхода. Ограничение по оси меняет ощущение — меньше ротационного танца, чем в Klotski, больше логистики.
Dad's Puzzle / Pennant Puzzle — американские предки Klotski начала XX века со слегка другими наборами блоков. Теперь предметы коллекционирования, но игра та же.
Универсального рецепта для этого семейства нет — в отличие от плиток. Что переносится: следите за пустыми клетками (это и есть настоящие движущиеся фигуры), двигайте блок-героя редко и считайте повторную перетасовку мелких блоков прогрессом, а не хождением кругами — решения здесь и правда половину времени выглядят как движение назад.
Что труднее?
Для человека: пазлы с разноразмерными блоками ощущаются труднее на каждый ход, но заканчиваются раньше; плиточные пазлы — это индивидуально лёгкие ходы в куда более длинных решениях.
Для компьютера ответ точен и неожидан. Конкретная доска Klotski тривиальна — десятки тысяч позиций, поиск в ширину, оптимальный ответ за миллисекунды. Конкретная 15-головоломка тяжела — десять триллионов состояний, требующих IDA* с хорошими эвристиками. Но обобщённые слайдинг-блок пазлы — любая доска, любые блоки — PSPACE-полны: доказано (через недетерминированную констрейнт-логику Хирна и Демейна), что они трудны настолько, насколько может быть любой пазл, чьи позиции помещаются в память. Невинно выглядящее семейство — в пределе самый трудный из известных видов пазлов.
Дерево, пластик или экран
Физические слайдинг-блок пазлы переживают тихий ренессанс — деревянные наборы Klotski и Rush Hour хороши как настольный объект и ещё лучше как подарок, а тактильный щелчок хорошо сделанного скольжения по-настоящему приятен. Плата за это: нет отмены хода, нет перемешивания, и никто не мешает «решить» деревянные пятнашки, выковыряв плитки (то самое решение образца 1880 года для нерешаемой доски Сэма Лойда).
На экране вы получаете то, чего дерево не умеет: честные перемешивания с гарантией решаемости, счётчик ходов, собственное фото в качестве картинки и солвер на день, когда доска вас одолеет. Наше приложение сохраняет тишину деревянной версии — без рекламы, стриков и аккаунтов — и добавляет ровно эти четыре вещи.
С чего начать
Если вы новичок в жанре: сыграйте сначала в 8-puzzle — он учит механике за десять минут. Потом 15-головоломка — настоящее дело. Потом Klotski — чтобы открыть, насколько по-разному может ощущаться та же механика, когда блоки перестают быть равными.