Ханойская башня

Главная › Головоломки › Ханойская башня

Ханойская башня — старая головоломка: три стержня и стопка дисков разного размера, сложенная пирамидой. Нужно перенести всю башню на другой стержень, двигая по одному диску и не кладя больший на меньший. Здесь можно играть онлайн бесплатно и без регистрации, на компьютере и на телефоне. Рядом со счётчиком виден минимум ходов, ходы отменяются сколько угодно раз, а если застряли, подсказка покажет следующий ход.

Как играть у нас

Число дисков — от 3 до 8 — выбирается кнопками над полем. Сначала их четыре, а потом игра запоминает ваш выбор. Цель всегда одна: соберите башню на правом стержне.

Нажмите на стержень — его верхний диск приподнимется. Нажмите на другой — диск ляжет туда. Можно и тянуть диск от стержня к стержню. На клавиатуре стержни выбираются клавишами 1, 2 и 3, а Esc снимает выбор. Если попробовать положить больший диск на меньший, диск вздрогнет и вернётся, появится строка «Больший диск нельзя класть на меньший», и такой ход не засчитается.

Над полем видно, сколько сделано ходов и какой минимум, например «Ходов: 12 · минимум 15». Отмена работает без ограничений, партия сохраняется сама.

Правила

Начало. Все диски надеты на левый стержень: самый большой внизу, самый маленький наверху.
Ход. За один ход переносится один диск — верхний с любого стержня на другой стержень.
Запрет. Больший диск нельзя класть на меньший. На пустой стержень можно класть любой.
Цель. Собрать всю башню в том же порядке на правом стержне.

Сколько ходов нужно

Минимальное количество ходов для башни из n дисков — 2ⁿ − 1.:

Дисков	Минимум ходов
3	7
4	15
5	31
6	63
7	127
8	255
9	511
10	1023

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

Как решить головоломку

Главная мысль: чтобы перенести самый большой диск, всё, что над ним, должно лежать на третьем стержне. Отсюда решение в три шага:

Перенести все диски, кроме нижнего, на средний стержень.
Переложить нижний диск на правый стержень.
Перенести те же диски со среднего стержня на правый, поверх большого.

Шаги 1 и 3 — та же задача на один диск меньше: пять колец сводятся к четырём, четыре — к трём и так до одного.

Есть и правило, по которому любая башня проходится без раздумий:

Нечётные ходы (1-й, 3-й, 5-й…) делает самый маленький диск, и всегда по кругу в одну сторону. Если дисков чётное число, первый раз он идёт на средний стержень, дальше по кругу: левый → средний → правый → левый. Если нечётное — сначала на правый: левый → правый → средний → левый.
Чётные ходы делает другой диск. Такой ход, не трогающий маленький диск, всегда ровно один — его и делайте.

Проверим на трёх дисках: маленький на правый, средний на средний стержень, маленький на средний, большой на правый, маленький на левый, средний на правый, маленький на правый. Семь ходов — ровно минимум.

Алгоритм решения

Те же три шага, записанные коротко: «перенести» собирает n верхних дисков на нужном стержне, пользуясь третьим как запасным.

перенести(n, откуда, куда, запасной):
  если n = 0 — ничего не делать
  перенести(n − 1, откуда, запасной, куда)
  переложить диск n: откуда → куда
  перенести(n − 1, запасной, куда, откуда)

начать: перенести(n, левый, правый, средний)

Такой приём называют рекурсией: задача решается через себя же, только поменьше.

Подсказка и показ решения

Кнопка «Подсказка» показывает следующий ход лучшего решения от той позиции, что сейчас на поле, — даже если вы уже сделали лишние ходы. Нужный диск светится, над стержнем, куда его положить, появляется стрелка, а в строке написано, например: «Диск 2 — на правый стержень. Осталось минимум 9 ходов». Ход делаете вы сами.

Кнопка «Решение» собирает башню сама, начиная с текущей позиции. Скорость — ×1, ×2 или ×4, есть «Пауза» и «Стоп»: остановили — и дальше можно играть самому. Партия, в которой включали показ решения, в рекорды не идёт.

История

Головоломку придумал французский математик Эдуард Люка и выпустил её в 1883 году. К игрушке прилагалась легенда: в храме монахи день и ночь переносят 64 золотых диска по тем же правилам, и когда закончат, наступит конец света. Но на это нужно 2⁶⁴ − 1 ходов, и даже по ходу в секунду без перерывов работа заняла бы около 585 миллиардов лет.

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

Частые вопросы

Можно ли собрать башню быстрее, чем за 2ⁿ − 1 ходов?

Нет. Самый большой диск придётся переложить хотя бы раз, а перед этим все остальные должны стоять башней на третьем стержне — это задача на один диск меньше. После переноса их снова нужно собрать сверху. Выходит, каждый новый диск как минимум удваивает число ходов и добавляет один, а это и есть 2ⁿ − 1.

Что значит «ханойская башня на 5 колец»?

То же, что пять дисков: кольцами их называют по виду деревянной игрушки. Минимум для пяти колец — 31 ход. Выберите 5 кнопкой над полем.

Зачем подсказка, если хочется решить самому?

Её можно не нажимать вовсе. Но на 7–8 дисках легко сбиться, и одна подсказка помогает понять, где ошибка, а дальше идти самому. Звёзды и рекорд при этом сохраняются — в рекорды не идут только партии с показом решения.