Thoughts on Programming

July 24, 2011

Towers of Hanoi

Filed under: Python — shadiyya @ 3:23 pm

In 1883 the French mathematician Edouard Lucas, the number theory scholar who became famous for the analysis on the Fibonacci sequence invented the Towers of Hanoi puzzle.

He was inspired by an Indian legend that tells of  the temple of Brahma in Benares. The legend tells that in the Temple with a dome which marked the center of the world, a brass plate is located on which 64  golden disk threaded on a needle are placed. Monks move one at a time disks on another needle according to the rule that a large disk can never be put on a smaller disk. When all disks are moved, recreating a Tower on another needle, then comes the end of the world.

It would take at least 264 -1 moves to complete the task. Assuming one move per second, and no wrong moves, it would take almost 585,000,000,000 years to complete. So we are safe even if the legend is true.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the pegs and sliding it onto another rod.
  • No disk may be placed on top of a smaller disk.

The number of moves necessary to move a tower with n disks can be calculated as: 2n – 1

There is a general rule for moving a tower of size n (n > 1) from the position A to the position C using the extra position B:

  • move a tower of n – 1 discs from A to B. Disk n is left alone at A
  • Move disk n from A to C
  • move the tower of n – 1 discs from B to C, i.e. this tower will be put on top of Disk n

The algorithm, which we have just defined, is a recursive algorithm to move a tower of size n. It actually is the one, which we will use in our Python implementation to solve the Towers of Hanoi. Step 2 is a simple move of a disk. But to accomplish the steps 1 and 3, we apply the same algorithm again on a tower of n-1. The calculation will finish with a finite number of steps, because very time the recursion will be started with a tower which is 1 smaller than the one in the calling function. So finally we will end up with a tower of size n = 1, i.e. a simple move.

The following Python program contains a recursive function “hanoi”, which implements a recusive solution for Towers of Hanoi. Here A is renamed as “source”, B as “helper” and C as “target”.

The Pygame implementation of each step of the algorithm is given here:


The complete code is available at:

https://bitbucket.org/fathimashadiyya/exercises/changeset/9cb1a9f7d823

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: