The purpose of this article is to demonstrate a very clean, recursive algorithm for solving the Towers of Hanoi problem, coded in VB.NET.
The Towers of Hanoi problem is a classic exercise meant to torture, discourage, and otherwise torment all new computer science students (or, at least that’s what they think). Really, it is perhaps the best example of a clean, simple problem to demonstrate the power of recursion. I was told back in school that there was a way to write a non-recursive algorithm to solve the Towers of Hanoi problem, but after a little thought (and exposure to the recursive approach), I gave up trying to figure out what it is.
In case you’re not familiar with the Towers of Hanoi problem, I’ll describe it briefly here. Basically, you have three posts, one of which contains a stack of discs that get smaller as you go up, like this:
The goal is to get the stack of discs from one post to a different post. There are two rules governing how discs can be moved:
- only one disc can be moved at a time, and
- you can never place a larger disc on top of a smaller one.
The algorithm that I have implemented starts with an assumption; we are assuming that we already have the ability to move a stack of discs. I realize that this is counterintuitive at this point, but bear with me. So, since we already know how to move a stack of discs, the process looks like this (where n is the total number of discs in the initial stack):
- Move n-1 discs from the source post to the temporary post.
- Move the last disc to the destination post.
- Move n-1 discs back from the temporary post to the destination post.
That's all there is to it (more or less)! All of this will be done inside a single method in our class, and steps 1 and 3 are recursive calls back to that same method. I imagine that many who might be reading this are scratching their heads right about now asking, "How (Why) does that work?" Let me say that I fully understand, and hopefully, seeing the code to make this work will help somewhat.
Show Me The Code!
A quick note about the code files included with this article. The project is a Visual Studio 2005 Beta 2 Project and will not open in earlier versions of Visual Studio. However, it will open and run correctly in Visual Basic 2005 Express Edition Beta2, which is freely available from Microsoft. You should also be able to simply copy and paste the code from here into Visual Studio 2003 and compile it.
OK, here is the code for the
Public Class Hanoi
Private discCounts(2) As Integer
Private moves(,) As Integer
Private movesIndex As Integer
Public Sub New(ByVal numDiscs As Integer)
discCounts(0) = numDiscs
discCounts(1) = 0
discCounts(2) = 0
ReDim moves(2 ^ numDiscs - 2, 1)
movesIndex = 0
Public Function GetMoves() As Integer(,)
DoMoves(0, 1, 2, discCounts(0))
Private Sub DoMoves(ByVal sourceSpindle As Integer, _
ByVal destSpindle As Integer, _
ByVal tempSpindle As Integer, _
ByVal discsToMove As Integer)
If discsToMove > 0 Then
DoMoves(sourceSpindle, tempSpindle, _
destSpindle, discsToMove - 1)
discCounts(sourceSpindle) -= 1
discCounts(destSpindle) += 1
moves(movesIndex, 0) = sourceSpindle
moves(movesIndex, 1) = destSpindle
movesIndex += 1
DoMoves(tempSpindle, destSpindle, _
sourceSpindle, discsToMove - 1)
A Little Math
There is a point worth noting with regards to how big the results of this can get. The total number of moves required to move the stack of discs from one spindle to another is equal to 2^n - 1, where n is the number of discs. So, for 3 discs, the number of moves is 2^3 - 1, or 7. For 5, it jumps to 31. For 10, it is 1023. My point here is that the size of the array required to hold the results becomes unmanageable very quickly. I would suggest keeping the number of discs down under 15, as by the time you get to 20, the number of moves is over 1 million!