Любые пятнашки собираются одним способом: верхний ряд, второй ряд, левый столбец, потом последние шесть клеток — и один приём для двух последних фишек каждого ряда. На случайной решаемой позиции он требует в среднем 96 ходов против примерно 53 у кратчайшего решения (это опубликованное число), а компьютер на этой странице каждый раз находит именно кратчайшее. Если ставить фишки по одной, способ выигрывает здесь 46% партий на «Простом», 10% на «Сложном» и меньше 1% на «Эксперте»; если продумывать целый ряд сразу — 88%, 54% и 13%.
Смысл в том, чтобы ставить фишки в таком порядке, при котором уже поставленное не приходится надолго разрушать. После каждого шага коробка как бы становится меньше, а последняя достаточно мала, чтобы собрать её, гоняя пустую клетку по кругу.
| a | b | c | d |
|---|---|---|---|
| 1 | 1 | 2 | 2 |
| 3 | 3 | 3 | 3 |
| 4 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
Какая клетка на каком шаге занимает своё место. Два верхних ряда после шага 3 больше не трогаются, левый столбец — после шага 4.
Застрять с этим способом нельзя. Мы перебрали все расположения фишек, с которыми работает каждый шаг при уже выполненных предыдущих: любое доводится до конца, не сдвигая поставленные фишки. В худших случаях это 21 ход на единицу, 32 на пару 3 и 4, 29 на 7 и 8, 24 на 9 и 13 и 21 на последние шесть клеток.
Последнюю фишку ряда нельзя просто довести до места: когда 1, 2 и 3 уже стоят, в угол можно попасть только снизу, и всё, что идёт в обход, выталкивает тройку. Поэтому 3 и 4 заходят вместе. Поставьте тройку в угол, на место четвёрки, четвёрку — прямо под неё, а пустую клетку приведите на место тройки:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | □ | 3 |
| · | · | · | 4 |
| · | · | · | · |
| · | · | · | · |
□ — пустая клетка, точка — любая фишка. Отсюда ряд заканчивается в два хода: тройка сдвигается влево, четвёрка — вверх.
Зеркальная расстановка ничуть не хуже: четвёрка на клетке тройки, тройка прямо под ней, угол пуст — тогда четвёрка идёт вправо, тройка вверх. Берите ту, до которой ближе.
Дорогая ошибка — сначала поставить тройку на место и надеяться, что четвёрка подтянется следом. Если четвёрка после этого окажется под тройкой, а угол пуст, кажется, что до конца один шаг, а на самом деле — пятнадцать ходов:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | □ |
| · | · | 4 | · |
| · | · | · | · |
| · | · | · | · |
Самый короткий путь закончить этот ряд, не трогая 1 и 2, — 15 ходов. Если же 4 и 3 стоят рядом в обратном порядке (1, 2, 4, 3), а пустая клетка под тройкой, — 17.
Эта пара — самая дорогая часть всей сборки. На случайных позициях верхний ряд стоит в среднем 38,5 хода — 10,4 на единицу, 9,4 на двойку и 18,7 на 3 и 4, — а второй 31,5, из них 15,8 уходит на 7 и 8. Две концовки рядов вместе — больше трети всех ходов, так что аккуратность окупается именно здесь.
Когда два ряда и левый столбец собраны, пять фишек и пустая клетка остаются в коробке высотой в две клетки и шириной в три. Заполнить её можно 720 способами, и ровно половина из них, 360, получается сдвигами — только такие и может оставить вам способ. Самая далёкая из них в 21 ходе от собранной, в среднем — 12,6: мы решили все 360.
Инструмент для этой коробки — круг. Проведите пустую клетку один раз вокруг любого квадрата из четырёх клеток — это четыре хода, — и три фишки в нём сдвинутся по кругу на одно место. Три таких круга возвращают всё как было. Вся концовка сводится к выбору, какой квадрат крутить и в какую сторону.
Если хочется и дальше действовать по правилам, соберите ещё один столбец — 10 и 14 парой, точно как 9 и 13, — и в последних четырёх клетках останутся три фишки. Приведите пустую клетку в её угол и посмотрите: либо 11, 12 и 15 уже на местах, либо до этого ровно четыре хода, один круг в одну из сторон. Третьего не бывает: из 24 способов заполнить эти четыре клетки встретиться могут только 12.
Собирать шесть клеток как одну коробку, а не как столбец и угол, почти ничего не даёт: в среднем 12,7 хода против 13,0. Ходы теряются раньше, в рядах.
Компьютер здесь никаким способом не пользуется. Он ищет кратчайшее решение и всегда его находит, а ваш предел — это его длина, умноженная на запас уровня. Значит, вопрос в том, во сколько раз способ длиннее кратчайшего решения:
| «Простой» | «Сложный» | «Эксперт» | Случайная позиция | |
|---|---|---|---|---|
| Кратчайшее решение, типичное | 22 | 36 | 46 | около 53* |
| Ваш предел, типичный | 44 | 54 | 58 | – |
| Способ, в среднем | 47,6 | 70,7 | 88,4 | 95,8 |
| Способ, во сколько раз длиннее кратчайшего | 2,2 | 2,0 | 1,9 | около 1,8 |
| Разрешено, во сколько раз длиннее | 2 | 1,5 | 1,25 | – |
| Партий выигрывает способ | 46% | 10% | 0,9% | – |
«Типичное» — медиана. 5000 раскладов на «Простом», 2000 на «Сложном», 1050 на «Эксперте», 10 000 случайных решаемых позиций. За способ играла программа, которая каждый шаг выполняет кратчайшим путём, так что это его лучшие показатели; человеку, который водит фишки не так чисто, понадобится больше. * Средняя длина кратчайшего решения случайной позиции, около 53 ходов, — опубликованный результат (Корф, 1985, и более поздние большие выборки), мы его не считали.
На случайной позиции способу в восьми случаях из десяти нужно от 79 до 112 ходов, а в худшем из 10 000 — 139. На «Простом» он балансирует на грани: предел вдвое длиннее кратчайшего решения, способ в среднем длиннее в 2,2 раза и укладывается в предел чуть реже чем в половине партий.
Вот настоящий расклад «Простого», на котором видно, куда уходят ходы. Кратчайшее решение — 22 хода, значит, предел — 44.
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| 9 | 5 | 12 | 11 |
| 13 | 6 | 15 | 8 |
| 10 | □ | 14 | 7 |
Верхний ряд уже на месте. Дальше способ тратит 4 хода на пятёрку, 7 на шестёрку, 13 на пару 7 и 8, 14 на 9 и 13 и 10 на последние шесть клеток: 48 ходов, на четыре больше предела. 22 хода компьютера, по номерам сдвигаемых фишек: 10, 13, 9, 5, 6, 10, 14, 15, 8, 11, 12, 8, 11, 7, 15, 11, 7, 12, 8, 7, 11, 15.
Способ теряет ходы потому, что каждая фишка едет в одиночку: пустая клетка идёт к фишке, провожает её домой и возвращается за следующей. Чем больше фишек вы продумываете как одну группу, тем меньше этой ходьбы. Мы дали программе находить кратчайший путь, которым целая группа встаёт на места сразу, и посчитали результат:
| Сколько фишек продумывать сразу | «Простой» | «Сложный» | «Эксперт» |
|---|---|---|---|
| По одной фишке (способ как описан) | 47,6 хода, побед 46% | 70,7, побед 10% | 88,4, побед 0,9% |
| По две: 1 и 2, затем 3 и 4, 5 и 6, 7 и 8 | 43,2, побед 55% | 65,5, побед 17% | 82,9, побед 1,4% |
| Целый ряд сразу | 32,4, побед 88% | 52,8, побед 54% | 67,0, побед 13% |
| Целые ряды, затем два нижних ряда как одна коробка | 31,4, побед 92% | 50,5, побед 65% | 63,9, побед 20% |
Первые две строки — по всем 5000, 2000 и 1050 раскладам, строки с целыми рядами — по 1000, 600 и 300 из них. Группа ставится на места кратчайшим путём, не разрушающим готовые ряды, то есть это потолок того, что может дать продумывание такой группы.
Продумать ряд целиком — значит посмотреть на все четыре его фишки до первого хода и собирать их по пути: фишку, мимо которой всё равно идёте, подтолкнуть к её клетке, а 3 и 4 с самого начала вести в расстановку для приёма, а не ходить за ними потом. Идеальный маршрут для четырёх фишек с ходу не находит никто, но таблица показывает, что на кону: порядок работы тот же, а ходов меньше на четверть, а то и на треть.
Порядок работы тоже важен, причём непредсказуемо. Способ можно положить набок: сначала левый столбец, потом второй, потом верх того, что осталось. Расклад, показанный выше, собирается так за 22 хода — короче не бывает, — а по рядам вышло 48. На 5000 раскладах «Простого» лучший из двух порядков дал в среднем 41 ход и выиграл бы 62% партий вместо 46%. Но очевидные приметы не подсказывают, какой порядок лучше: выбор по тому, где больше фишек уже на местах или какие фишки ближе к дому, угадывал более короткий порядок в 43–54% случаев — не лучше монетки.
А вот жадность не окупается. Игрок, который смотрит на четыре хода вперёд, выбирает последовательность, после которой фишки в сумме ближе всего к своим местам, а когда улучшить нечего, переходит к способу, выигрывает 49% на «Простом», где способ сам по себе берёт 46%, и 7% на «Сложном», где способ берёт 10%. Фишки, стоящие рядом со своими клетками, но в неправильном порядке, — это хуже, чем кажется.
Шестнадцать клеток можно заполнить 16! = 20 922 789 888 000 способами. Ровно половина, 10 461 394 944 000, получается из собранной коробки сдвигами; другую половину не соберёт никто, включая компьютер. Это общая теория, доказанная в 1879 году, и причина короткая.
Каждый ход меняет местами одну фишку и пустую клетку. Раскрасьте клетки как шахматную доску: каждый ход меняет ещё и цвет под пустой клеткой, поэтому вернуть её в угол можно только за чётное число ходов. А чётное число обменов никогда не сводится к перестановке всего двух фишек. Поэтому у коробки ниже — той самой, за которую когда-то обещали тысячу долларов, — решения нет:
| a | b | c | d |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 15 | 14 | □ |
Фишки 14 и 15 переставлены. Получив такую коробку, решатель страницы просматривает все отведённые ему три миллиона позиций и возвращается без ответа.
То же самое видно целиком на маленькой коробке. Из 720 способов заполнить два ряда по три клетки сдвигами получаются ровно 360; из 24 способов заполнить коробку два на два — ровно 12. Мы выписали их все.
Чтобы проверить коробку вручную, прочитайте фишки ряд за рядом и сосчитайте пары, стоящие в неправильном порядке, — большее число раньше меньшего. Прибавьте номер ряда, в котором стоит пустая клетка, считая снизу. Сумма нечётная — коробка собирается, чётная — нет. Для собранной коробки это 0 + 1.
Здесь нерешаемая коробка вам не попадётся. Страница не раскладывает фишки наугад: она начинает с собранной коробки и делает случайные ходы, никогда не отменяя только что сделанный, — 24 хода на «Простом», 50 на «Сложном», 150 на «Эксперте». Коробка, которая вышла почти собранной, раздаётся заново. Отсюда два следствия. Кратчайшее решение не бывает длиннее перемешивания, а на «Простом» обычно близко к нему: от 20 до 24 ходов в 82% раскладов. И оно всегда чётное, на любом уровне, потому что чётны сами перемешивания: у всех 8050 раскладов, которые мы получили, кратчайшее решение было чётной длины.
Прежде чем вы сможете тронуть доску, компьютер решает коробку. Он использует IDA* — алгоритм, который Ричард Корф предложил в 1985 году как раз на этой головоломке: поиск в глубину, которому на каждом проходе разрешают чуть большую глубину и который не идёт по ветке, если доказуемо не успеет по ней закончить. Доказательством служит оценка, которая никогда не завышает: сумма расстояний всех фишек до их клеток плюс два хода за каждую пару фишек, стоящих в своём ряду или столбце, но в обратном порядке. Раз оценка не завышает, первое найденное решение — кратчайшее.
| «Простой» | «Сложный» | «Эксперт» | |
|---|---|---|---|
| Перемешивание, ходов | 24 | 50 | 150 |
| Позиций просматривает поиск, типично | 153 | около 17 000 | около 464 000 |
| Кратчайшее решение: типичное и разброс в наших раскладах | 22 (8–24) | 36 (18–48) | 46 (28–60) |
| Ваш предел | 2 × кратчайшее | 1,5 × кратчайшее | 1,25 × кратчайшее, с округлением вверх |
| Запас ходов сверх кратчайшего, типичный | 22 | 18 | 12 |
Поиск ограничен тремя миллионами позиций — это примерно полсекунды. Коробка, которой нужно больше, выбрасывается и раздаётся заново ещё до того, как вы её увидите. На «Простом» за 5000 раскладов такого не случилось ни разу, на «Сложном» — 7 раз из 2007, а на «Эксперте» так отсеивается треть всех перемешиваний (529 из 1579) — те, что труднее всего даются поиску. Поэтому коробка «Эксперта» трудная, но не самая трудная из возможных: её кратчайшее решение в среднем 46,7 хода против примерно 53 у по-настоящему случайной, а из 300 по-настоящему случайных решаемых коробок, которые мы попробовали, поиск страницы уложился в своё ограничение только на 157.
Счёт строгий. Каждая сдвинутая фишка — один ход, так что щелчок по фишке через две-три клетки от пустой сдвигает весь ряд и стоит два-три хода. Предел виден на экране до вашего первого хода, рядом с длиной кратчайшего решения. Вы побеждаете, если собрали коробку не больше чем за предел ходов; результат записывается только тогда, когда коробка собрана, так что брошенная партия вам в минус не идёт. После партии меню «Игра → Решение компьютера» проигрывает его кратчайшее решение с начальной позиции — это самый быстрый способ увидеть, что видел он и не увидели вы.
Самым трудным позициям пятнашек нужно 80 ходов, если считать по одной фишке за ход. Это опубликованный результат 1999 года (общеизвестный факт), и до него здешним раскладам далеко: самое длинное кратчайшее решение в наших 1050 раскладах «Эксперта» — 60 ходов.
Поставьте фишки 1 и 2, затем заведите 3 и 4 парой: тройка в углу, четвёрка под ней, пустая клетка на месте тройки — и тройку влево, четвёрку вверх. Второй ряд собирается так же, потом 9 и 13 парой уходят в левый столбец, а последние шесть клеток доводятся кругами пустой клетки. На случайных позициях это в среднем 96 ходов.
Нет. Из 20 922 789 888 000 способов заполнить коробку из собранной позиции получается ровно половина. Сосчитайте пары фишек в неправильном порядке и прибавьте номер ряда пустой клетки, считая снизу: нечётная сумма — коробка решаема. На этой странице коробки перемешиваются настоящими ходами, поэтому решаемы всегда.
Каждый ход меняет местами одну фишку и пустую клетку, а вернуть пустую клетку в угол можно только за чётное число ходов. Чётное число обменов не может дать перестановку ровно двух фишек, поэтому коробка, где переставлены только 14 и 15, недостижима.
Зависит от позиции. Случайной решаемой коробке в лучшем случае нужно около 53 ходов, самым трудным — 80; оба числа — опубликованные результаты. На этой странице кратчайшее решение обычно 22 хода на «Простом», 36 на «Сложном» и 46 на «Эксперте», и оно показано над доской до начала игры.
При сборке по рядам — около 96 на случайной позиции, чуть меньше чем вдвое больше кратчайшего решения. Если продумывать целый ряд сразу, а не по одной фишке, уходит на четверть, а то и на треть меньше: на здешних раскладах «Простого» среднее упало с 47,6 хода до 32,4.
Он выполняет поиск IDA* с оценкой, которая никогда не завышает число оставшихся ходов: расстояния фишек до их клеток плюс штраф за фишки, стоящие в нужном ряду, но в обратном порядке. Это отсекает почти всё: на коробку «Простого» обычно уходит 153 позиции, на коробку «Эксперта» — около 464 000, меньше секунды.
Собрать быстрее него нельзя: его решение — кратчайшее из возможных. Побеждает тот, кто уложился в предел. Простой способ по одной фишке укладывается в 46% партий на «Простом», в 10% на «Сложном» и меньше чем в 1% на «Эксперте», а с продумыванием целых рядов — в 88%, 54% и 13%.