Ханойская башня — перестановочная головоломка в виде трёх стержней, на один из которых в виде пирамиды нанизаны восемь колец разного диаметра. Задача состоит в том, чтобы переместить пирамиду из колец на другой стержень за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
История создания головоломки Эту игру придумал французский математик Эдуард Люка в 1883 годуМартин Гарднер, Математические головоломки и развлечения, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).
Решение
Существует несколько подходов к решению.
Рекурсивное решение Рекурсивно решаем задачу «перенести башню из n−1 диска на 2-й стержень». Затем переносим самый большой диск на 3-й стержень, и рекурсивно решаем задачу «перенеси башню из n−1 диска на 3-й стержень».
Отсюда методом математической индукции заключаем, что минимальное число ходов, необходимое для решения головоломки, равно 2n − 1, где n — число дисков.
В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к нерекурсивным.
«Треугольное» решение Расположим стержни в виде треугольника. Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем перенесём какое-нибудь из оставшихся колец (такой ход единственный), после чего снова переложим самое маленькое кольцо и т. д. (При перенумеровании «колец» по порядку чётные кольца будут перемещаться с одной вершины треугольника на другую в одном направлении, а нечётные — в противоположном направлении.)
Циклическое решение Обозначим через «1-2» такое действие: переложить диск или с 1-го стержня на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 3-2.
Применение кода Грея для решения
Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде. Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он запатентовал (за номером 2632058) и использовал этот код в своей импульсной системе связи.
Коды Грея могут быть применены в решении задачи о Ханойских башнях.
Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G0), и будем двигаться по кодам Грея (от Gi переходить к Gi+1). Поставим в соответствие каждому i-ому биту текущего кода Грея i-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита i как перемещение i-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия правильного выбора хода: для нечётного N последовательность перемещений наименьшего диска f→t→r→f→t→r→… (где f — стартовый стержень, t — финальный стержень, r -оставшийся стержень), а для чётного f→r→t→f→r→t→….
Решение для машины Тьюринга В 1992 году студент второго курса РГАТУ им. П. А. Соловьёва Иван Басов, ныне доктор философии (PhD), живущий и работающий в США, предложил запрограммировать головоломку «Ханойские башни» на машине Тьюринга. Тогда же Иван предложил удобный способ описания размещения дисков по стержням, где каждому диску соответствует своя ячейка ленты. Первоначально все диски находятся на стержне A, поэтому все ячейки ленты содержат символ A. Слева и справа от этих ячеек размещены символы «#», ограничивающие исходные данные (пример: «…#AAAA#…»). Блок управления первоначально указывает на самую левую ячейку с символом A, соответствующую диску минимального диаметра. Один из вариантов входных данных, предложенных Иваном Басовым, подразумевал кодировку дополнительного стержня-приёмника. Здесь же приведен упрощённый вариант задачи, где требуется переместить все диски со стержня A на любой другой стержень (либо B, либо C). Благодаря этому простому способу описания размещения дисков по стержням, Иван Басов, а также его научный руководитель В. Н. Пинаев написали каждый свою программу для машины Тьюринга. В основе этих решений лежал известный простой нерекурсивный алгоритм перекладывания дисков.
Основная идея этого алгоритма звучит так:
Каждый нечётный ход — это циклический ход первого диска:либо в направлении A⟶B⟶C⟶A⟶B⟶C⟶… (в случае чётного количества дисков),либо в направлении A⟶C⟶B⟶A⟶C⟶B⟶… (в случае нечётного количества дисков). Каждый чётный ход определяется однозначно (!):находим наименьший отличный от первого диск и перемещаем его на тот стержень, где нет первого диска.
В нашем случае задача упрощается, так как по условию разрешено перемещать башню на любой стержень, и поэтому нам не потребуется определять чётность количества дисков.
Окончательно имеем следующий алгоритм: Перемещаем на один шаг по кругу A⟶B⟶C⟶A первый диск. Перемещаемся по дискам вправо до тех пор, пока идентификатор стержня совпадает с идентификатором стержня, на котором лежит первый диск. Если обнаружен знак конца дисков «#», то работа закончена. Если найден диск, лежащий на стержне, отличном от стержня первого диска, то перемещаем найденный диск на допустимый стержень (это третий оставшийся стержень, если исключить стержни первого и текущего дисков). Возвращаемся к пункту 1.
Tаблица управления соответствующая описанному алгоритму № строки Текущий символ на ленте Текущее состояние Новый символ на ленте Новое состояние Движение Комментарий 1 A 1 B 2 > Ход первым диском с A на B (запоминаем этот ход через состояние 2) 2 B 1 C 3 > Ход первым диском с B на C (запоминаем этот ход через состояние 3) 3 C 1 A 4 > Ход первым диском с C на A (запоминаем этот ход через состояние 4) 4 B 2 B 2 > Пропускаем диски на стержне B (состояние 2 означает, что первый диск находится на стержне B) 5 A 2 C 5 < Если нашли диск на стержне A, то переместим его на стержень С и начинаем подъем к первому диску 6 C 2 A 5 < Если нашли диск на стержне C, то переместим его на стержень A и начинаем подъем к первому диску) 7 C 3 C 3 > Пропускаем диски на стержне C 8 B 3 A 5 < Если нашли диск на стержне B, то переместим его на стержень A 9 A 3 B 5 < Если нашли диск на стержне A, то переместим его на стержень B 10 A 4 A 4 > Пропускаем диски на стержне A 11 B 4 C 5 < Если нашли диск на стержне B, то переместим его на стержень С и начинаем подъем к первому диску 12 C 4 B 5 < Если нашли диск на стержне C, то переместим его на стержень B и начинаем подъем к первому диску 13 A 5 A 5 < Подъем к первому диску 14 B 5 B 5 < Подъем к первому диску 15 C 5 C 5 < Подъем к первому диску 16 # 5 # 1 > Переходим в начальное состояние
С этой задачей связана следующая интересная история. В 1992 году Иван Басов, будучи студентом второго курса РГАТУ им. П. А. Соловьёва, написал исследование при содействии научных руководителей В. Н. Пинаева и Б. Я. Фалевича, которое было представлено на всероссийский конкурс студенческих научных работ. Исследуя машину Тьюринга и головоломку «Ханойские башни», он провёл анализ нескольких алгоритмов, оценил число шагов машины Тьюринга, подробно описал программную реализацию и в том числе привёл таблицу управления, подобную вышеприведенной. Рецензентом этой работы оказался известный учёный сибирской школы алгебры и логики, А. С. Морозов, который сравнил Ивана с Левшой, «подковавшим» эту программистскую «блоху». В последующие десятилетия эта задача и её модификации неоднократно предлагались на российских и международных студенческих олимпиадах по программированию. Кроме того, пример решения головоломки «Ханойские башни» на машине Тьюринга признан более содержательным, чем операции над унарными числами, которыми изобилуют примеры в публикациях и методических пособиях по этой тематике, и рекомендован при изучении машины Тьюринга.
Варианты
Перемешанные Ханойские башни В 1990 году преподаватель информатики РГАТУ им. П. А. Соловьёва В. Н. Пинаев предложил рассмотреть такую задачу: все диски расположены в произвольном порядке на всех трёх стрежнях, требуется собрать их на одном. Эта задача также всегда разрешима и названа её создателем «перемешанной Ханойской башней» или «Ханойской п-башней». Заметим, что идея этой головоломки идёт от кубика Рубика: запутаем расположение частей головоломки, а потом постараемся привести её к первоначальному виду с помощью разрешенных действий.
В общем случае изначальное расположение дисков может быть совершенно произвольным, и диск большего диаметра может оказаться на диске меньшего диаметра. В таком случае «Ханойская п-башня» является «сильно перемешанной». Если же изначальное расположение дисков исключает такое положение, то она является «слабо перемешанной». «Слабо перемешанная Ханойская башня» также может быть представлена методом Басова для машины Тьюринга (пример входных данных: «…#ACABC#…»).
Сдвоенные Ханойские башни Эта головоломка также была предложена В. Н. Пинаевым и использовалась на ученических и студенческих олимпиадах по программированию под названиями «Чёрный ящик», «Кодовый замо́к» и «Светофор». Смысл головоломки состоит в том, что две случайным образом «перемешанные Ханойские башни» (или «Ханойские п-башни») закодированные методом Басова для машины Тьюринга были «соединены» общим диском минимального диаметра. Чтобы это наглядно представить, нужно абстрагироваться от физических свойств «Ханойских башен» и рассматривать их только в контексте кода Басова. В одной из разновидностей головоломки состояния элементов кодировались цветами: красный, желтый, зеленый (почему задание и называлось «Светофор»). Исходное состояние замка генерировалось с использованием равномерно распределенного датчика случайных чисел и потому являлось произвольным. Замок открывался, если все его элементы оказывались в одинаковом состоянии (любом). Воздействовать на замок можно было через его кнопки. При нажатии на кнопку были возможны два варианта: либо ничего не изменится, либо элемент перейдет в другое состояние.
В конструкции замка была предусмотрена внутренняя память из одной ячейки (недоступной пользователю). В этой ячейке хранилось состояние замка, которое определялось номером первой нажатой кнопки. Как используется и используется ли вообще эта ячейка — было неизвестно.
Фактически, в зависимости от номера первого нажатого элемента замок распадался на две части: левую и правую. Каждая часть представляла собой отдельную Ханойскую башню со своими стержнями и дисками. Но диск минимального диаметра был общим для этих частей. Цвет элемента указывал, на каком стержне находится соответствующий диск. Отличие от стандартной Ханойской башни заключалось в том, что в исходном положении диски были размещены на стержнях в произвольном порядке. Задача в такой постановке называется «перемешанной Ханойской башней» или «Ханойской п-башней».