Игра «Ханойские башни»

Как перенести Ханойскую башню

Три стержня Ханойской башни: на левом сложены три диска разного размера

Ханойская башня представляет собой головоломку с тремя стержнями и дисками разного размера. Нужно перенести всю стопку с левого стержня A на правый C. За один ход разрешено переместить только верхний диск, а большой нельзя класть на маленький. Для трёх дисков достаточно 7 ходов, для четырёх потребуется уже 15.

Стержень B служит временной площадкой. Диски нумеруются по размеру: 1 самый маленький, затем 2, 3 и так далее. Ширина тоже показывает размер, поэтому выбирать по цвету не нужно. В начале все диски находятся на A, большой снизу, маленький сверху. Пустой стержень принимает любой верхний диск, но не всю башню целиком.

Прочитайте короткие правила, выберите количество дисков и нажмите «Начать игру». В открывшемся поле нажмите стержень, с которого хотите снять диск, затем место назначения. Нажатие выбранного стержня повторно снимает выбор, Escape делает то же самое. Перетаскивать детали не требуется: на телефоне проще попадать в три крупные области, чем ловить маленький верхний кружок пальцем. С клавиатуры работают Tab для перехода между кнопками и Enter или пробел для выбора.

Почему минимум равен 2ⁿ − 1

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

Это называется рекурсией: один способ решения применяется к более короткой версии той же задачи. Для одного диска нужен 1 ход. Для двух нужны 1 + 1 + 1 = 3. Для трёх получаем 3 + 1 + 3 = 7. Два переноса маленькой башни нельзя просто выкинуть из плана, поэтому число является нижней границей, а не удобным пожеланием.

Минимальное число ходов при переносе всей исходной башни вычисляется так:

M(n)=2^n-1

Здесь n обозначает число дисков, M(n) число перемещений. Для 3, 4, 5, 6, 7 и 8 дисков получаются 7, 15, 31, 63, 127 и 255 ходов. Каждый дополнительный диск удваивает предыдущий минимум и добавляет ещё один ход. Именно поэтому первые минуты игры могут казаться обманчиво лёгкими: фигур немного, а работы быстро становится больше.

Если хочется проверить степень для другого количества дисков, подойдёт калькулятор возведения в степень: основание 2, показатель равен количеству дисков, после расчёта отнимите 1. Число стержней при этом должно оставаться равным трём. Добавление четвёртого меняет задачу, и старая формула перестаёт описывать её минимум.

Как выбрать следующий ход

Первая короткая партия. Возьмите 3 диска и попробуйте последовательность A-C, A-B, C-B, A-C, B-A, B-C, A-C. После четвёртого хода самый большой диск уже окажется на C, а после седьмого над ним соберутся два маленьких. Это готовое решение без лишних ходов. Повторите его, стараясь понимать назначение каждого перемещения, иначе при добавлении четвёртого диска знакомые нажатия перестанут помогать.

Освободить большой диск. В партии с 4 дисками сначала перенесите верхние 3 с A на B за 7 ходов. Восьмым ходом отправьте диск 4 с A на C. Осталось перенести маленькую башню с B на C за ещё 7 ходов: итог 15. Практический ориентир здесь состоит из трёх этапов, а не списка пятнадцати команд. Следите, какой стержень временный именно сейчас: его роль меняется внутри каждого этапа.

Большой пытается обогнать маленький. Пусть на A снизу находятся диски 3 и 2, на B лежит 1, а C пуст. Перенос A-B запрещён: верхний диск 2 больше диска 1. Поле и счётчик останутся прежними. Возможный ход A-C освобождает диск 3, но перед его переносом нужно проверить будущий путь всей башни. Ошибка не означает, что партия испорчена: просто выберите другое назначение.

Возврат вместо лишнего обхода. Допустим, в партии с 3 дисками вы сделали первый ход A-B, затем решили начать с A-C. Нажмите «Отменить ход»: диск 1 вернётся на A, а счётчик станет равен 0. Перенос B-A вручную дал бы уже 2 хода, хотя поле выглядело бы точно как в начале. Отмена позволяет изучать развилки без штрафа; обычное обратное перемещение остаётся настоящим ходом.

Проверка длительности. Для 8 дисков минимум равен 255 ходам. Если условно тратить по 5 секунд на обдумывание и перемещение, получится 1275 секунд, то есть 21 минута 15 секунд. Это арифметический пример, не норматив скорости: паузы и поиск решения могут занять больше. Для короткого перерыва разумнее оставить 3 или 4 диска, чем выбрать максимум и неожиданно получить небольшую рабочую смену.

Подсказка после отступления. Сделайте A-B и B-A в партии с 3 дисками. Счётчик покажет 2, башня вернётся на старт, а кратчайший путь до цели снова будет состоять из 7 ходов. Итог при дальнейшем идеальном прохождении составит 9. Поэтому нельзя брать «минимум со старта» и вычитать сделанные ходы, чтобы узнать остаток. Подсказка выбирает ход из текущего расположения, даже если предыдущие перемещения были лишними.

Что означает счётчик и когда башня собрана

Счётчик увеличивается только после разрешённого переноса. Выбор источника, снятие выбора, запрещённая попытка и просьба подсказать ничего к нему не добавляют. Число рядом с «Можно решить за» показывает минимум для всей исходной башни. Оно не уменьшается во время игры и не утверждает, что из любой промежуточной позиции осталось столько же действий.

Победа наступает, когда все диски находятся на правом стержне C. Собранная на B башня ещё не выполняет условие этой партии. После победы поле прекращает принимать новые перемещения, но отменить последний ход можно: это возвращает предыдущую позицию и позволяет посмотреть другой конец решения. Новая партия с тем же количеством дисков возвращает башню на A и обнуляет счёт.

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

Кнопка «Правила и настройки» возвращает к инструкции и выбору от 3 до 8 дисков. Дробь, пустое поле и число за границами вызывают сообщение об ошибке, а существующая башня сохраняется. Другое допустимое число начнёт новую задачу только после нажатия «Начать игру». Если количество прежнее, можно продолжить партию. После перезагрузки тоже нажмите «Продолжить игру»: расположение, выбор и история отмены сохраняются на время браузерной сессии, если разрешено локальное хранение.

Вопросы о правилах и решении

Три стержня допускают много легальных промежуточных расположений, но цель у партии одна. Разобраться в исключениях полезнее, чем бездумно повторять первый найденный список ходов.

Можно ли временно положить большой диск на маленький?

Нет, даже на один ход. Это основное ограничение задачи. Вместо такого переноса нужно освободить нужный стержень или положить большой диск на пустой. Если разрешить нарушение, привычный минимум перестанет быть ориентиром: получится другая головоломка.

Есть ли положение, из которого уже нельзя закончить игру?

Из любого законного расположения всех дисков на трёх стержнях можно добраться до цели. Каждый разрешённый перенос обратим. Значит, при необходимости можно вернуться по собственным ходам на старт, а затем решить исходную задачу. Однако такой маршрут обычно длиннее кратчайшего.

Обязательно ли начинать самым маленьким диском?

В исходной позиции да: только диск 1 лежит сверху и доступен для переноса. Но место назначения зависит от количества дисков и выбранного плана. Для оптимального переноса трёх дисков с A на C первый ход ведёт на C, а для четырёх на B.

Считаются ли два одинаковых нажатия двумя ходами?

Два нажатия одного стержня сначала выбирают источник, затем снимают выбор. Диск не перемещается, поэтому счётчик не меняется. Ход состоит из переноса между разными стержнями, причём новое положение должно соблюдать порядок размеров.

Почему переставлять диски можно только сверху?

Так устроена классическая задача: диск должен быть верхним и в исходной, и в новой стопке. Если разрешить вытаскивать нижние, необходимость освобождать самый большой исчезнет. Поэтому переносить диск 3 из-под дисков 2 и 1 нельзя, даже если для него есть свободный стержень.

Почему для четырёх стержней не подходит та же формула?

Дополнительный стержень даёт ещё одно место для временного хранения. Маленькую башню уже не обязательно целиком складывать на единственном промежуточном стержне. Формула 2ⁿ − 1 относится к классическим трём стержням; этот инструмент намеренно не смешивает её с другими вариантами.

Что делать, если пропала сохранённая партия?

Хранение может быть недоступно в приватном режиме, после очистки данных сайта или закрытия браузерной сессии. Тогда открывается стартовое поле с тремя дисками. Сохранение служит удобством внутри браузера, а не аккаунтом или резервной копией: между устройствами партия не переносится.

Можно ли оценивать по этой игре интеллект?

Количество ходов показывает, насколько экономно решена конкретная задача при данном числе дисков. На прохождение влияют знакомство с алгоритмом и использование подсказок или отмены. Это не шкала интеллекта и не диагностический тест. Для сравнения собственных попыток сохраняйте одинаковые условия.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.