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

Как играть в Ханойскую башню

1. Выберите количество дисков (от 3 до 8). Все они лежат стопкой на стержне 1: самый большой внизу, самый маленький сверху.
2. Нажмите на стержень, чтобы выбрать его верхний диск, затем на стержень, куда хотите его перенести. Диск можно также перетащить на другой стержень.
3. Переносите только один диск за ход и никогда не кладите диск на другой, меньший, чем он.
4. Вы выигрываете, когда вся башня оказывается на другом стержне. Счётчик показывает ваши ходы и минимально возможное число; если застряли, кнопка «Решить» воспроизведёт кратчайшее решение.

Классика логики и рекурсии

Ханойская башня — математическая головоломка, придуманная французом Эдуардом Люка в 1883 году. С n дисками минимальное число ходов равно 2 в степени n минус 1: 7 для трёх дисков, 15 для четырёх, 31 для пяти и 255 для восьми. Каждый добавленный диск удваивает работу и прибавляет один ход.

Есть систематический способ решения. Чтобы перенести башню из n дисков, сначала переносите верхние n−1 дисков на оставшийся стержень, затем переносите самый большой диск на место назначения и наконец переносите n−1 дисков поверх него. Это типичный пример рекурсии. Ещё одно практическое правило: самый маленький диск двигается на каждом нечётном ходу и всегда в одном направлении (при нечётном числе дисков со стержня 1 на 3, с 3 на 2 и со 2 на 1; при чётном — с 1 на 2, со 2 на 3 и с 3 на 1); на чётных ходах между двумя другими стержнями возможен только один ход.

Легенда гласит, что монахи переносят башню из 64 золотых дисков; для этого понадобится больше 18 квинтиллионов ходов, то есть сотни миллиардов лет при одном ходе в секунду. Вся игра идёт в вашем браузере: на сервер ничего не отправляется, а на устройстве сохраняется только ваш лучший результат.

Что нужно учитывать

• Рекорд (наименьшее число ходов) сохраняется для каждого количества дисков только в этом браузере: если очистить данные сайта, он пропадёт.
• Если вы воспользовались кнопкой «Решить», партия не идёт в зачёт рекорда. Кнопка вычисляет лучшее решение из того положения, в котором вы находитесь, а не с начала.
• Для 8 дисков нужно не меньше 255 ходов; автоматическое решение воспроизводит их в хорошем темпе, и его можно остановить в любой момент.

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