How to implement the Tower of Hanoi problem using Python

Preface

The Tower of Hanoi problem is a classic problem. Hanoi Tower, also known as Hanoi Tower, originated from an ancient legend in India. When Brahma created the world, he made three diamond pillars. On one pillar, 64 gold discs were stacked in order of size from bottom to top. Brahma ordered the Brahmin to rearrange the disks on another pillar in order of size from the bottom. It is also stipulated that at any time, the disk cannot be enlarged on the small disk, and only one disk can be moved between the three pillars at a time. Ask how to operate?

1. Let’s first talk about what is recursion?

My own understanding is: continue to reduce the size of your own problems until it is reduced to the point where it cannot be reduced. (The end condition of the recursion is reached) Then start solving the small problems. After solving the small problems one by one, the big problem will be solved (the recursion returns)

2. In short:

Original The problem is reduced to a smaller original problem, and then the smaller original problem is solved, thereby solving the original big problem!

3. The process is:

Reduce the scale, solve it from a small size, recurse back, and solve the original problem! ! !

4. The key to recursion is:

(1) There is a recursive end condition.

(2) Continuously call itself to reduce the size of the problem and move closer to the end condition of the recursion.

Tower of Hanoi problem

1. Problem description

There are three pillars named A, B, and C. Initially, there are n disks on pillar A, they are from bottom to top, and the size of the disks is from large to small. During moving and placement, the small plates must be on top of the large plates. While ensuring the rules, move all the plates on pillar A to pillar C. You can use pillar B during the move, but you must ensure that the small plates must be on the big plates during the move! ! ! Please print out the moving process?

2. Problem analysis recursive process:

(1) Move the top n-1 plates from A to B## with the help of C

#(2) Move the bottom plate from A to C

(3) Move the top n-1 plates from B to C

recursively The end condition:

The problem scale becomes when the number of plates is 0, because when the number of plates is 0, there is no need to move! ! !

3. Code (Python)

# coding:utf-8

"""
    n为初始时A柱上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""


def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("盘子从%s移动到%s" % (a, c))
        hanoi(n-1, b, a, c)



hanoi(3, "A", "B", "C")

4. Result display

The above is the detailed content of How to implement the Tower of Hanoi problem using Python. For more information, please follow other related articles on the PHP Chinese website!