Чтобы решать Ханойскую башню, нужно запомнить всего два правила. Если чередовать их, то при любом числе дисков башню можно перенести за наименьшее число ходов. В статье мы объясняем случай, когда башню переносят с левого стержня на правый (правила игры описаны в статье Что такое Ханойская башня?). Диски называем по номерам от самого маленького: 1, 2, 3…

Решение — повторение двух правил

  1. Ход с нечётным номером (1-й, 3-й, 5-й…): самый маленький диск (1) переносят на следующий стержень в заданном направлении.
  2. Ход с чётным номером (2-й, 4-й, 6-й…): делают ход, в котором участвует не диск 1. Такой ход всегда только один.

Вот и всё. Диск 1 двигается через ход, а в промежутках по одному разу двигаются остальные диски.

Как выбрать направление движения маленького диска

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

Число дисковПорядок движения диска 1
нечётное (3, 5, 7…)левый → правый → средний → левый…
чётное (4, 6, 8…)левый → средний → правый → левый…

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

Если нужно перенести башню на средний стержень, читайте в таблице «правый» и «средний» наоборот.

Проверим на 3 дисках

Дисков 3 (нечётное число), поэтому диск 1 ходит по кругу «левый → правый → средний → левый». Золотым цветом отмечен диск, который двигали в этом ходу.

  1. 321 Начало
  2. 321 Ход 1 Диск 1 — вправо
  3. 321 Ход 2 Диск 2 — в центр
  4. 321 Ход 3 Диск 1 — в центр
  5. 213 Ход 4 Диск 3 — вправо
  6. 123 Ход 5 Диск 1 — влево
  7. 132 Ход 6 Диск 2 — вправо
  8. 321 Ход 7 Диск 1 — вправо

Видно, что на 1-м, 3-м, 5-м и 7-м ходах просто идёт диск 1, а 2-й, 4-й и 6-й ходы — это «единственный возможный ход без диска 1».

Почему ход с чётным номером определяется однозначно

На ходу с чётным номером сравнивают верхние диски двух стержней, на которых нет диска 1. Меньший диск остаётся только положить на больший (или на пустой стержень).

  • На диск 1 нельзя положить никакой диск (дисков меньше 1 нет).
  • Из двух оставшихся стержней большой диск нельзя положить на маленький.

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

Идея «убрать верхние диски и перенести большой»

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

  1. Убрать верхние n − 1 дисков на средний стержень.
  2. Перенести самый большой диск вправо.
  3. Перенести n − 1 дисков со среднего стержня вправо.

Части 1 и 3 — это задача «перенести башню на один диск меньше», поэтому ту же идею можно применить ещё раз. Для 4 дисков: «убрать 3 диска → перенести диск 4 → вернуть 3 диска», а чтобы убрать 3 диска: «убрать 2 диска → перенести диск 3 → вернуть 2 диска» — и так далее, задача делится на всё более маленькие. Из этой идеи видно и то, что ходов будет 2ⁿ − 1 (статья о формуле минимального числа ходов).

Как восстановить порядок, если запутались

Если вы забыли порядок и диски оказались разбросаны, ничего страшного. Вот как можно навести порядок из любого положения.

  1. Найдите среди дисков, которые ещё не лежат на правом стержне как надо, самый большой. Это и есть следующий диск, который нужно перенести.
  2. Чтобы перенести его вправо, все диски меньше него нужно собрать на оставшемся стержне, который не является ни текущим, ни правым.
  3. Сбор маленьких дисков — повторение той же идеи. Считайте стержень, куда собираете, «целевым» и начните сначала.

Секрет в том, чтобы решать, куда идти, начиная с больших дисков. Режим «Задачи» в приложении (где разбросанные диски нужно привести к форме образца) тоже решается по этой идее.

Советы

  • Считайте ходы: на нечётных ходах всегда двигают диск 1, поэтому, зная номер хода, вы не будете гадать, какой диск двигать.
  • Чем больше диск, тем реже он двигается: диск 1 двигается примерно на половине ходов, а самый большой диск — только один раз. Если вы много раз двигаете большой диск, вы идёте в обход.
  • Сначала берите 3 или 4 диска: пока два правила не войдут в привычку, лучше несколько раз повторить с малым числом дисков. Освоившись, переходите к 5 и 7 дискам.

Ходы для каждого числа дисков

Порядок ходов для разного числа дисков и опорные формы по дороге собраны в этих статьях.

Попробуйте на практике

Попробуйте два правила на доске ниже. Нажмите на стержень, чтобы поднять самый верхний диск, и на другой стержень, чтобы положить его туда. Сначала дисков 4 (чётное число), поэтому первым ходом диск 1 нужно перенести на средний стержень.

4321
Ходов: 0 (минимум 15)

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