The Towers of Hanoi in VB.NET

• Download demo project - 16.8 Kb

Introduction

The purpose of this article is to demonstrate a very clean, recursive algorithm for solving the Towers of Hanoi problem, coded in VB.NET.

Background

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.

Algorithm Overview

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:

1. only one disc can be moved at a time, and
2. 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):

1. Move n-1 discs from the source post to the temporary post.
2. Move the last disc to the destination post.
3. 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 Hanoi class:

''' <summary>
''' Author: Shannon M. Neumann
''' Written: September 29, 2005
'''
''' Title: Hanoi.vb
'''
''' Notes: I wrote this after a discussion between
'''        myself and my boss about how little code
'''        it would really be.
'''
''' You are free to use this code, but please give me credit for it.
''' </summary>

Public Class Hanoi

    Private discCounts(2) As Integer
    Private moves(,) As Integer
    Private movesIndex As Integer

    ''' <summary>
    ''' Constructor simply sets up the local variables that we need.
    ''' </summary>
    Public Sub New(ByVal numDiscs As Integer)

        discCounts(0) = numDiscs
        discCounts(1) = 0
        discCounts(2) = 0

        ReDim moves(2 ^ numDiscs - 2, 1)
        movesIndex = 0
    End Sub

    ''' <summary>
    ''' GetMoves is the public method that kicks off the recursive process.
    ''' </summary>
    Public Function GetMoves() As Integer(,)
        DoMoves(0, 1, 2, discCounts(0))

        Return moves
    End Function

    ''' <summary>
    ''' Recursive Method to get all disc moves
    ''' to solve the Towers of Hanoi problem.
    ''' </summary>
    Private Sub DoMoves(ByVal sourceSpindle As Integer, _
                        ByVal destSpindle As Integer, _
                        ByVal tempSpindle As Integer, _
                        ByVal discsToMove As Integer)

        ' A recursive method needs a case where
        ' you simply return back (the base case),
        ' and one or more cases
        ' where you recursively call the method
        ' again (the recursive cases). In this
        ' situation, if there are discs to
        ' be moved, then we do some work,
        ' otherwise we simply do nothing.
        If discsToMove > 0 Then
            ' This next line is a recursive call
            ' that moves n-1 discs from the source
            ' spindle to the temp spindle.
            DoMoves(sourceSpindle, tempSpindle, _
                    destSpindle, discsToMove - 1)

            ' These next two lines move the last
            ' disc from the source spindle to the n spindle.
            discCounts(sourceSpindle) -= 1
            discCounts(destSpindle) += 1

            ' The next three lines record this
            ' move in the moves array for use later.
            moves(movesIndex, 0) = sourceSpindle
            moves(movesIndex, 1) = destSpindle
            movesIndex += 1

            ' This recursive call moves the n-1
            ' discs back from the temp spindle to the
            ' destination spindle.
            DoMoves(tempSpindle, destSpindle, _
                    sourceSpindle, discsToMove - 1)
        End If
    End Sub
End Class

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!