15-головоломка — также «пятнашки», «mystic square» или просто «слайдер 4×4» — это каноническая скользящая головоломка. Доска 4×4, пятнадцать нумерованных квадратных плиток, одна пустая клетка. Двигаете плитки в пустую клетку по одному ходу, пока числа не выстроятся по порядку: 1‑2‑3‑4 в верхней строке, 5‑6‑7‑8, 9‑10‑11‑12, 13‑14‑15 и пустая клетка в правом нижнем углу.
Откуда взялась
Игру изобрёл в 1874 году почтмейстер из города Канастота, штат Нью-Йорк, по имени Ноес Палмер Чепмен. К 1880-му она дошла до бостонских школ, к середине 1880 года стала повальным увлечением в США, а к осени пересекла Атлантику и захватила Британию, Францию и Германию. Газеты публиковали колонки с решениями. Рабочие забрасывали работу ради пазла. В некоторых немецких городах власти, по слухам, запрещали игру в общественных местах, потому что чиновники не занимались ничем другим.
Сэм Лойд — нью-йоркский составитель головоломок, всегда готовый рассказать о себе байку — объявил, что изобрёл игру (на самом деле нет), и предложил приз $1000 тому, кто решит конкретную конфигурацию с переставленными 14 и 15. Эта конфигурация оказалась математически нерешаемой (доказательство см. в статье про чётность 15-головоломки). Никто не выиграл. Лойд был доволен.
Как играть
Три правила:
- Можно сдвинуть только ту плитку, которая рядом с пустой клеткой — прямо над, под, слева или справа от неё. Диагонали запрещены.
- Сдвиг перемещает плитку в пустую клетку. Пустая клетка теперь там, где была плитка.
- Готово, когда плитки выстроены по порядку.
Всё. Ни таймера, ни счёта, ни второй цели. Вся игра — в этих трёх предложениях.
Насколько это сложно
У 15-головоломки 16!/2 ≈ 10,46 триллиона достижимых конфигураций (половина от всех 16!, из-за правила чётности). Самое короткое решение из самой сложной стартовой позиции — 80 ходов. Медианное — около 52.
Новичок решает свою первую 15-головоломку за 15–30 минут методом проб и ошибок. Игрок, освоивший приём «строка + столбец» на 8-puzzle, решает любые пятнашки 4×4 за 3–7 минут. Спид-солвер, выбирающий оптимальные ходы, укладывается в 90 секунд.
Почему 4×4 — золотая середина
Не случайно мировым феноменом стала именно 15-головоломка, а не 8 или 24. Доска 4×4:
- Достаточно длинная, чтобы приносить удовольствие. 8-puzzle решается так быстро, что у партии нет арки. 15-головоломка тянется достаточно, чтобы дать маленькое облегчение от готовой доски.
- Достаточно короткая, чтобы не утомлять. 24-головоломка занимает у уверенного игрока 15+ минут. 35-головоломка — 30+. 4×4 укладывается в кофе-брейк.
- Достаточно сложная, чтобы было о чём подумать. Стратегия не очевидна с первой попытки. Г-образный приём в углу нужно открыть или подсказать — и как только это случилось, весь пазл раскрывается.
Эта золотая середина — причина, по которой 15-головоломка стала собирательным именем для всего семейства. Говорят «слайд-пазл» и представляют 4×4.
В информатике
Десятилетиями 15-головоломка была стандартным бенчмарком для алгоритмов эвристического поиска. Знаменитая статья Ричарда Корфа 1985 года, представившая IDA*, использовала 100 случайных 15-головоломок, чтобы показать ускорение по сравнению с A*. Современные работы про базы шаблонов до сих пор приводят результаты на 15-головоломке. Пазл достаточно мал, чтобы быть решаемым, и достаточно велик, чтобы плохие алгоритмы уходили в таймаут.
Если вы когда-нибудь проходили вводный курс по ИИ, вы решали 15-головоломку как программистское упражнение. Скорее всего — A* с эвристикой манхэттенского расстояния. (Глубже — в статье про солвер.)
Варианты в современных приложениях
У 15-головоломки в сегодняшних приложениях несколько обычных вариантов:
- Цифровые плитки — оригинал, обычные цифры на плитках.
- Картиночные плитки — фотография, нарезанная на N×N, вместо цифр. Решая, восстанавливаете изображение.
- Гибрид — картиночные плитки с маленькими цифрами поверх, для тех, кому нужна подсказка о позиции каждой плитки.
Некоторые приложения идут дальше: гексагональные сетки, большие доски (5×5 = 24-головоломка, 6×6 = 35-головоломка), ротационные пазлы, где плитки могут поворачиваться, и так далее. Но численная версия 4×4 — это лингва франка.
Где играть
На телефоне нативные приложения дают более гладкий опыт — без загрузки на сервер, без аналитики, без рекламы посреди сдвига плитки. Slide Puzzle поставляется с классической нумерованной версией плюс 300 фотографических обложек и четырьмя размерами (3×3, 4×4, 5×5, 6×6).
В вебе браузерных 15-головоломок десятки. Они удобны, но обычно загружают импортированные фото на сервер и запускают аналитику. Если вы хотите пару игр и никогда не собираетесь импортировать своё фото — этого хватит.
Если вы ещё не решали — начните с 8-puzzle на тридцать секунд, просто чтобы почувствовать ход, и потом возвращайтесь к 15. Стратегия с маленькой доски масштабируется напрямую.