Ханойские башни 2024

Эта игра головоломка была изобретена французским математиком Эдуардом Лукасом в 1883 году. Она продавалась с 8 дисками и с описанием легенды о том, что в храме в Бенаресе, Индия, есть "Башня Брахмы", где жрецы храма перемещают 64 золотых диска по одному диску каждую секунду. Когда они выполнят свою работу, миру придет конец.

Имеется три стержня X, Y и Z. На стержень источник X (source) нанизаны пирамидкой несколько колец разного диаметра. Задача состоит в том, чтобы за наименьшее число ходов перенести пирамиду на целевой стержень Y (target), используя стержень Z (storage), как промежуточный.

За один раз разрешается переносить только одно кольцо, причём, нельзя класть большее кольцо на меньшее.

Рис. 1.

Решить головоломку Ханойская башня можно несколькими методами.

Рекурсивный метод

Предположим, что нам известен алгоритм перемещения n-1 дисков с одного стержня на второй. Дадим функции, реализующей алгоритм этих перемещений имя play. Тогда функция play() для перемещения n дисков со стержня источник на стержень цель должна будет:

переместить верхние n-1 дисков со стержня источник на промежуточный стержень,
последний диск n переместить со стержня источник на стержень цель,
переместить все n-1 диск со стержня промежуточный на стержень цель.

Напишем программу вывода на печать способа перемещения n-го (нижнего) диска, это сделать проще всего.

def play(n, источник, цель, промежуточный):
    '''
    Функция перемещения n дисков со стержня источник на
    стержень цель, с использованием промежуточного стержня.
    По правилам игры ханойские башни.
    n количество дисков
    X стержень источник
    Y целевой стержень
    Z промежуточный стержень
    '''
    # 1. переместить верхние n-1 дисков со стержня источник на промежуточный стержень
    pass

    # 2. последний диск n переместить со стержня источник на стержень цель
    print("Диск ", n, " : ", источник, " --> ", цель)
    
    # 3. переместить все n-1 дисков со стержня промежуточный на стержень цель.    
    pass


n = 4      # Количество дисков
board = (' стержень X', ' стержень Y', ' стержень Z')
play(n, *board)

Лист. 1. Программа перемещения последнего, n-го диска.

В программе, листинг 1, в функции play(), в комментариях, описан весь алгоритм перемещения n дисков со стержня источник на стержень цель. Но, некоторые части функции play() не дописаны. В этих местах вставлены заглушки - функция pass (ничего не делать).

Диск  4  :   стержень X  -->   стержень Y

Лист. 2. Вывод программы листинг 1.

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

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

def play(n, источник, цель, промежуточный):
    '''
    Функция перемещения n дисков со стержня источник на
    стержень цель, с использованием промежуточного стержня.
    По правилам игры ханойские башни.
    n количество дисков
    X стержень источник
    Y целевой стержень
    Z промежуточный стержень
    '''
    
    if n == 0: return
    
    # 1. переместить верхние n-1 дисков со стержня источник на промежуточный стержень
    play(n-1, источник, промежуточный, цель)

    # 2. последний диск n переместить со стержня источник на стержень цель
    print("Диск ", n, " : ", источник, " --> ", цель)
    
    # 3. переместить все n-1 дисков со стержня промежуточный на стержень цель.    
    play(n-1, промежуточный, цель, источник)


n = 4      # Количество дисков
board = (' стержень X', ' стержень Y', ' стержень Z')
play(n, *board)

Лист. 3. Программа для игры Ханойские башни.

Диск  1  :   стержень X  -->   стержень Z
Диск  2  :   стержень X  -->   стержень Y
Диск  1  :   стержень Z  -->   стержень Y
Диск  3  :   стержень X  -->   стержень Z
Диск  1  :   стержень Y  -->   стержень X
Диск  2  :   стержень Y  -->   стержень Z
Диск  1  :   стержень X  -->   стержень Z
Диск  4  :   стержень X  -->   стержень Y
Диск  1  :   стержень Z  -->   стержень Y
Диск  2  :   стержень Z  -->   стержень X
Диск  1  :   стержень Y  -->   стержень X
Диск  3  :   стержень Z  -->   стержень Y
Диск  1  :   стержень X  -->   стержень Z
Диск  2  :   стержень X  -->   стержень Y
Диск  1  :   стержень Z  -->   стержень Y

Лист. 4. Вывод программы листинг 3.

def play(n, источник = 1, цель = 2):
    board = (None, 'X', 'Y', 'Z')
    if n == 0: return
    временный = 6 - источник - цель
    play(n-1, источник, временный)
    print('Перемещаем диск {} со стержня {} на стержень {}'.format(n, board[источник], board[цель]))
    play(n-1, временный, цель)


n = 4      # Количество дисков
play(n)

Лист. 5. Программа для игры Ханойские башни.

Перемещаем диск 1 со стержня X на стержень Z
Перемещаем диск 2 со стержня X на стержень Y
Перемещаем диск 1 со стержня Z на стержень Y
Перемещаем диск 3 со стержня X на стержень Z
Перемещаем диск 1 со стержня Y на стержень X
Перемещаем диск 2 со стержня Y на стержень Z
Перемещаем диск 1 со стержня X на стержень Z
Перемещаем диск 4 со стержня X на стержень Y
Перемещаем диск 1 со стержня Z на стержень Y
Перемещаем диск 2 со стержня Z на стержень X
Перемещаем диск 1 со стержня Y на стержень X
Перемещаем диск 3 со стержня Z на стержень Y
Перемещаем диск 1 со стержня X на стержень Z
Перемещаем диск 2 со стержня X на стержень Y
Перемещаем диск 1 со стержня Z на стержень Y

Лист. 6. Вывод программы листинг 5.

Тимофей Хирьянов, МФТИ.

Python