Стратегия Ханойской башни: решение за 2^n − 1 ходов (2026)

Последнее обновление: 17 октября 2026 · Проверено на сборке Tower of Hanoi от Playnesta (математическая головоломка из общественного достояния Эдуарда Люка, 1883; модуль правил, оболочка, таблица стилей, мост и сенсорный шим — собственные разработки Playnesta, MIT; раскладка интерфейса навеяна AJLoveChina/Hanoi @ 917b8d6, MIT, только как справочник по механике) · 3 стержня · от 3 до 8 дисков, по умолчанию 4 · оптимум 2^n − 1 ходов (3 диска → 7, 4 → 15, 5 → 31, 6 → 63, 7 → 127, 8 → 255)

Метод: каждое число ниже — константа из поставляемого модуля правил js/hanoi.js (собственная разработка Playnesta, MIT), прочитанная и проверенная в этой сессии, а не цитата из третьих источников. Головоломка полностью детерминирована, поэтому ?disks=5 воспроизводит одну и ту же стартовую позицию для всех, и наблюдаемого апстрим-билда нет. Проверенные константы: 3 стержня (стержень 0 начинает со всех дисков, самый большой внизу и самый маленький сверху; стержни 1 и 2 начинают пустыми); число дисков от 3 до 8, по умолчанию 4; оптимум — 2^n − 1 ходов; ход легален только если целевой стержень пуст или его верхний диск больше перемещаемого, а нелегальный ход (больший диск на меньший) отклоняется мгновенно и ничего не меняет; победа срабатывает только тогда, когда полная башня приземляется на стержень, отличный от стартового; Отмена откатывает один ход и сбрасывает состояние победы; счётчик ходов сравнивается с оптимумом и переходит в Идеально!, когда решаешь за минимальное число. Управление: перетащи диск на другой стержень или коснись стержня, чтобы поднять верхний диск, и коснись другого, чтобы опустить; меню числа дисков (3–8), кнопки Отмена, Правила и Новая игра; баннер «Решено!» с «Играть снова» в конце. Таймера нет, играй в своём темпе. Ниже — стратегия: страница игры уже объясняет, как работать с доской; здесь — как решить за минимум ходов.

1. Вся игра — одно число: 2^n − 1

Для n дисков минимально возможное число ходов — 2^n − 1, и этот билд показывает его и оценивает тебя по нему. Три диска требуют 7, четыре — 15, пять — 31, шесть — 63, семь — 127, восемь — 255. Это не произвольная цель — это математический пол, и ни один человек не может лучше.

Большинство тех, кто «решает» Ханойскую башню, делают это за два-три оптимума, потому что двигают диски opportunistично и замечают потраченные ходы только в конце. Счётчик и баннер Идеально! этого билда делают эту потерю видимой: он переходит в «Идеально!» только когда число твоих ходов при победе равно 2^n − 1. Пока ты не увидел этот баннер, ты не решил головоломку — ты её просто закончил. Значит, первая цель не «перенести башню», а «перенести башню за 2^n − 1 ходов», и всё ниже — путь.

2. Рекурсивный рецепт, бьющий в пол

Оптимальное решение имеет рекурсивную форму, и как только её видишь, головоломка перестаёт быть поиском и становится чек-листом. Чтобы перенести башню из n дисков со стержня A на стержень C, используя стержень B как резерв:

Перенеси верхние n − 1 дисков с A на B (используя C как резерв).
Перенеси самый большой диск с A на C.
Перенеси башню из n − 1 с B на C (используя A как резерв).

Вот и весь алгоритм. Шаг 2 — единственное движение самого большого диска; шаги 1 и 3 — та же задача на размер меньше. Поскольку самый большой диск может двигаться только когда на нём ничего нет и цель пуста, ты вынужден сначала его освободить — а освободить его значит решить меньшую башню, которая в свою очередь должна освободить свой самый большой диск, и так далее до одного диска.

Практическое следствие: самый большой диск двигается ровно один раз, и только в середине решения. Если твой самый большой диск двигался больше одного раза, ты не на оптимальном пути — ты снова его закопал и придётся освобождать заново. Следи за этим: сессия, в которой нижний диск всё время поднимают, — это сессия, которая закончится далеко за 2^n − 1.

3. Три ошибки, которые стоят ходов

Двигать самый большой диск слишком рано. Его нельзя двигать, пока на его стержне есть что-то сверху, поэтому каждый ход до того, как башня из n − 1 полностью припаркована на резервном стержне, — это ход, откладывающий единственный ход, который важен. Новички часто тасуют верхние диски «чтобы начать» и только потом замечают, что нижний всё ещё пригвождён.

Считать пустой стержень декорацией. Пустой стержень — не резерв, который используешь время от времени; это монтажная площадка, делающая рекурсию возможной. В игре на трёх стержнях в любой момент один стержень держит башню, которую ты строишь, другой — ту, которую разбираешь, а третий свободен. Если ты сознательно не используешь все три роли, ты делаешь лишнюю работу, чтобы обойти ту, которую проигнорировал.

Играть жадно. Легальный ход, который сейчас выглядит лучше всего, редко тот, который рекурсия хочет дальше. «Двигать самый маленький диск» ощущается продуктивным, потому что он всегда легален, но оптимальная последовательность чередует маленькие и большие диски по фиксированному шаблону (при нечётном числе дисков самый маленький циклирует A → C → B → A; при чётном — A → B → C → A). Если перестаёшь думать и всё время двигаешь самый маленький легальный диск, ты закончишь — но не за 2^n − 1.

4. Поднимайся по лестнице дисков и знай, когда остановиться

Сложность не линейна, она экспоненциальна, и числа ходов честно это показывают:

3 диска / 7 ходов — учи здесь рекурсию. Всю решение можно держать в голове.
4 диска / 15 ходов — первый размер, где нужно доверять рецепту, а не импровизировать.
5 дисков / 31 ход — настоящая головоломка; одна ошибка — и ты на 10 ходов выше.
6 дисков / 63 хода — сессия; планируй закончить за один присест, иначе потеряешь нить.
7 дисков / 127 ходов — проект; используй Отмену целенаправленно.
8 дисков / 255 ходов — марафон; игра позволяет, но большинство сессий должны жить между 4 и 6.

Честный путь тренировки — 3 → 4 → 5, и только потом 6. Прыгать к 8 «чтобы увидеть большую» ничему не учит, потому что 255 ходов импровизации — это усталость, а не практика. Меню числа дисков (3–8) и параметр ?disks=n в URL позволяют зафиксировать размер, так что зафиксируй размер на неделю и гонись за баннером «Идеально!» на нём, прежде чем подниматься.

5. Используй Отмену как учителя, а не как костыль

Отмена откатывает один ход и сбрасывает состояние победы, поэтому это самый чистый способ учить рекурсию: играй до неуверенности, вернись к последней позиции, которую понимал, и выведи следующий ход из рецепта, а не угадывай. Поскольку в игре нет таймера, нет штрафа за остановку и размышление — измеряется только число ходов.

Две привычки, которые помогают: переигрывай тот же seed с ?disks=4 (или любым), пока не попадёшь в «Идеально!» дважды подряд, и вслух называй, какой диск и почему собираешься двигать, до того как двинешь. Если не можешь сказать, какой диск и почему, ты угадываешь, а угадывание — это то, что толкает счётчик выше 2^n − 1. Игра также выдаёт ту же башню для одного и того же значения ?disks=, так что можно тренировать одну позицию вместо перезапуска с новой случайной каждый раз.

FAQ

Чем это отличается от правил на странице игры?

Страница игры объясняет, как работает доска — три стержня, только верхний диск, больший никогда не покрывает меньший, перетаскивание или касание, счётчик против оптимума, Отмена, 3–8 дисков, без таймера. Это руководство считает это известным и играет на слое выше: пол 2^n − 1, рекурсивный рецепт, три ошибки, лестница дисков и как тренироваться. Сначала прочитай правила, потом гонись за баннером «Идеально!».

2^n − 1 действительно минимально возможное?

Да. Самый большой диск должен сдвинуться хотя бы раз, а чтобы его сдвинуть, n − 1 дисков над ним должны быть сняты с его стержня и с пути; по индукции это требует как минимум 2^(n−1) − 1 ходов до и 2^(n−1) − 1 после, плюс один ход самого большого диска. Три стержня — минимум, делающий задачу нетривиальной, и с тремя стержнями пол в точности 2^n − 1. Варианты с четырьмя стержнями (головоломка Реве) имеют более низкий пол, но эта игра использует три.

Почему баннер говорит «Идеально!» только иногда?

Потому что «Идеально!» зарезервировано для решения ровно за 2^n − 1 ходов. Решение за большее число ходов всё равно выигрывает — баннер «Решено!» срабатывает, и число ходов показывается против оптимума, — но «Идеально!» активируется только когда твоё число равно полу. Если ты его никогда не видел, твоё число ходов выше пола; счётчик показывает, на сколько.

Любая позиция решаема?

Да. Стартовая позиция — всегда полная башня на одном стержне, и рецепт решает её для любого n от 3 до 8. Перемешивания и тупиков нет — нелегальный ход просто отклоняется и ничего не меняет, так что в угол себя не загонишь. Всегда можно отменить до известного хорошего состояния.

На каком числе дисков тренироваться?

Начни с 3, пока не попадёшь в «Идеально!» дважды подряд, затем 4, затем 5. Большинство игроков упираются в 5 дисков (31 ход), и это хорошее место, чтобы остаться — 6 и выше для более длинных сессий, не для обучения. Избегай 8 для тренировки; 255 ходов импровизации — это усталость, а не практика.

Где можно играть?

Прямо на странице tower-of-hanoi этого сайта. Головоломка — математическая задача из общественного достояния, опубликованная Эдуардом Люком в 1883 году, поэтому апстрим-файлов, переиспользованных байт в байт, нет; модуль правил, оболочка страницы, таблица стилей, мост аналитики и сенсорный шим — всё собственная разработка Playnesta и MIT. Раскладка интерфейса навеяна AJLoveChina/Hanoi @ 917b8d6 (MIT), который читали только как справочник по механике и не распространяют здесь. Playnesta Games — разработчик и издатель этой конкретной веб-реализации.