Tuesday, 27 November 2018

Tower of Hanoi



The Tower of Hanoi is a classic mathematical puzzle consisting of three pegs and disks of different sizes. The aim of the puzzle is to move the stack of increasing size disks from one peg to the other, by moving only the upper disk of any peg at a time. On each movement, no larger disk may be placed above another smaller disk.

The problem was first described by the French mathematician Édouard Lucas in 1883 and it is a  problem where recursion can be easily used to solve the game. Along with the Fibonacci series, it is the classic exercise of a 101 programming course where students are asked to apply recursion.

Recently I built three wooden play sets of Tower of Hanoi and thought it would be interesting to increase my knowledge on the problem.






As a first approach of the problem, I wrote the classical recursive solution, which I post here. I will tackle the problem from a different perspective, probably graph theory, in the coming posts. 

The Python code can be found on my github repository. I have splitted the solution in three different Python classes, Rectangle, which deals with the graphic representation of the objects using Pyglet library, Disk, which represents a disk in the Tower of Hanoi problem, keeping track of the position of itself at any moment, and finally the Hanoi class, which solves the problem using the recursive algorithm and show a graphical representation of the step by step solution.

Following the instructions of the README.md file at the git hub repository, you can get the following solution video.



Stay tuned for upcoming post on the subject with different solution approaches.


No comments:

Post a comment