tower of hanoi Algorithm
The Tower of Hanoi Algorithm is a classic puzzle-solving algorithm that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, following a set of rules: only one disk can be moved at a time, a disk can only be placed on top of a larger disk, and no disk may be placed on top of a smaller disk. This algorithm is widely used to teach recursive problem-solving techniques in computer science and mathematics.
The Tower of Hanoi Algorithm is solved using a recursive approach. The algorithm can be broken down into three main steps: move the top n-1 disks from the source rod to an auxiliary rod, move the largest disk (nth disk) from the source rod to the target rod, and finally move the n-1 disks from the auxiliary rod to the target rod. The base case for the recursion occurs when there is only one disk to move, in which case it is simply moved from the source rod to the target rod. Recursively applying these steps, the Tower of Hanoi puzzle can be efficiently solved in 2^n - 1 moves, where n is the number of disks.
def moveTower(height, fromPole, toPole, withPole):
"""
>>> moveTower(3, 'A', 'B', 'C')
moving disk from A to B
moving disk from A to C
moving disk from B to C
moving disk from A to B
moving disk from C to A
moving disk from C to B
moving disk from A to B
"""
if height >= 1:
moveTower(height - 1, fromPole, withPole, toPole)
moveDisk(fromPole, toPole)
moveTower(height - 1, withPole, toPole, fromPole)
def moveDisk(fp, tp):
print("moving disk from", fp, "to", tp)
def main():
height = int(input("Height of hanoi: ").strip())
moveTower(height, "A", "B", "C")
if __name__ == "__main__":
main()
