What are the Towers of Hanoi?

It is known as a mathematical game invented by French Édouard Lucas in 1883. It consists of passing n disks stacked and ordered by size from one stake to another, guaranteeing that a disk of radio R never gets on top of another one of radio r (assuming that R> r)

It is also only possible to move one disk at a time and always the disk at the top of the stack.


We are going to perform its algorithm in Python using recursion.

  • First we define the function taking as parameters the number of discs and the three stakes, named as: TorreOrigen, TorreAuxiliar and TorreDestino.
def Hanoi (disks, TorreOrigen = 1, TorreAuxiliar = 2, TorreDestino = 3)

To the values ​​of the towers I put their names by default since they will always be the same.

  • The Algorithm will be recursive and the base case for this problem occurs when there is only one disk to move.

But ... what is recursive and base case?

Well, let's explain it.

Recursion is one of the most powerful and important tools in Computing. The concept is not limited only to the scope of programming but it is present in nature itself where different organizations have recursive structures. Objects whose geometric structure is fragmented or irregular is repeated at different scales.

A function is recursive when it is defined in terms of itself, as for example.

f (1) = 1

f (2) = 2

f (n) = f (n-1) + 2 * f (n-2)

For n> 0, where n is an integer

An example of recursion in Python

def sum (numbers):

if len (numbers) is 0:

return 0

return numbers [0] + sum (numbers [1: len (numbers)])

The recursion is divided into 2 cases:

  • The base case which defines the end of the recursion and represents an input to the problem for which the solution is easily known

In the example of the sum, the base case is reached when the length of the list of numbers is zero. Obviously the sum of a list that does not contain numbers is zero.

  • The recursive case where a general rule is defined to solve the problem reducing it to a problem of smaller size.

In the recursive case, we see the sum of a list of numbers as the sum of the first element + the sum of the rest. This formulation is valid and thus also the final result is reached.

Now that we know what is Recursivity and base case we continue with our algorithm to solve the Towers of Hanoi.

What will be our base case ?. Well, when we only have one disk left to go through.

if disks == 1:

print (TorreOrigen, »a», TorreDestino)

Recursively the problem is resolved by noting that by moving each disk of the Source Tower to the Target Tower, all the n-1 disks stacked on top of the main disk in TorreOrigen must first move to the Axioms Tower. Then move this major disk from TorreOrigen to TorreDestino and finally the n-1 that were stacked in TorreAuxiliar towards TorreDestino.

In this way we have already solved our algorithm for the Hanoi Towers with n disks.

But this how it is expressed in code.

else:

Hanoi (n-1, TorreOrigen, TorreDestino, TorreAuxiliar)

print (TorreOrigen, »a», TorreDestino)

Hanoi (n-1, TorreAuxiliar, TorreOrigen, TorreDestino)

Well, that's it! Let's put both parts together and we have an elegant and highly optimized program to solve this famous puzzle of the year 1883.

To make it easier for you here I leave the code on an online console so you can do your tests.