The Towers of Hanoi

I decided yesterday to put in some practice by tackling the Tower of Hanoi problem. The problem is a very common one that I’ve seen all over the web but until now I hadn’t taken the time to work it out.

The problem begins as three pegs on which discs can be placed. The discs are placed in decreasing order of size to create a pyramid of n height on peg 1 and the task is to move the discs from peg 1 to peg 3. The constraint of the problem is that a larger sized disc cannot be placed on top of a smaller disc.

Creating an array for each of the three pegs and notating each disc as an integer from 1 – n depending on size gave me a representation of the problem. The beginning of the problem looked like so:

tower1 = [n,n-1,…,4,3,2,1]
tower2 = []
tower3 = []

I then began to map out the base cases for the problem:

N = 1, 1n move from tower 1 to tower 3:
1 disc from tower 1 to tower 3

N = 2, 2n move from tower 1 to tower 3:
1n move from tower 1 to tower 2
1 disc from tower 1 to tower 3
1n move from tower 2 to tower 3

N = 3, 3n move from tower 1 to tower 3:
2n move from tower 1 to tower 2
1 disc from tower 1 to tower 3
2n move from tower 2 to tower 3

If we notate the towers as origin, destination, and buffer, we begin to see the pattern:

origin to buffer
origin to destination
buffer to destination

Also we see that the problem lends itself to recursion easily because for a 3 height tower there are just two 2 height tower sub-problems, for a 4 there are two 3 height tower sub-problems, etc.

Given this fact, we can work together a recursive solution using normal arrays:

# Define a move
def move(origin, dest)
  if dest.empty? || origin[-1] < dest[-1]
    dest.push(origin.pop)
 end
end

# The recursive solution
def move_tower(n, origin, dest, buffer)
  if n == 1
    move(origin, dest)
  else
    move_tower(n-1, origin, buffer, dest)
    move_tower(1, origin, dest, buffer)
    move_tower(n-1, buffer, dest, origin)
  end
end

tower1 = [6,5,4,3,2,1]
tower2 = []
tower3 = []

move_tower(6, tower1, tower3, tower2)
# Result is tower3 = [6,5,4,3,2,1]

The move ensures we don't make an illegal move by making sure the target stack is either empty or has a larger disc than what we are moving. The solution takes in the height, and the three towers that we create and solves the problem recursively.

The solution is was quite fun to puzzle through by finding the pattern in the cases and modeling a solution to reflect that pattern. There is also an iterative solution that takes into account the fact that odd and even numbered towers have different solutions with set repeating moves. I will try to tackle that one in the future!

Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: