Hanoi Towers nostalgia

This is a game invented in 1883 by Edouard Lucas d’Amiens, a french mathematician. He loved anagrams, and he used the pseudonim Professor N. Claus (de Siam), which is an anagram of his name, to publish about the game.

The rules are very simple:

Only one disc can be moved at a time

A larger disc can’t be moved on top of a smaller disc

The goal is to move all the discs from one pin to the other one.

I wrote a Z80 basic program to solve it back in 1984, but I don’t have the code anymore. Recently, Salvat Editores launched here in Brazil a bi-weekly publication where they sell a nicely crafted wooden puzzle every week.

The first one is Hanoi Towers, and I just wrote a quick Python program to solve the puzzle:

#!/usr/bin/python
# This program solves the puzzle "Hanoi Towers"
# We'll have 3 sticks, named A,B,C.  The discs will be numbered 1..n and the
# smaller number means smaller radius disc.  The program will start with all
# the discs in the center stick and will move them to the left stick

numDiscs = 7
A=[]
B=[numDiscs-x for x in range(numDiscs)]
C=[]

def moveStack(orig,dest,temp,depth):
  # moveStack will move a (sorted) sub-stack of the top discs from the stick
  # orig to the stick dest, using the stick temp as a temporary holder.  The
  # number of discs moved is given by depth

  assert (len(orig)>=depth)
  assert (len(dest)==0) or (orig[-depth] < dest[-1])
  assert (len(temp)==0) or (orig[-depth] < temp[-1])

  if (depth == 1):
    dest.append(orig.pop())
    print A,B,C
  else:
    moveStack(orig,temp,dest,depth-1)
    dest.append(orig.pop())
    print A,B,C
    moveStack(temp,dest,orig,depth-1)

print A,B,C
moveStack(B,A,C,numDiscs)

No related posts.