12,697,178 members (24,037 online)
alternative version

76.9K views
23 bookmarked
Posted

# The Towers of Hanoi in VB.NET

, 4 Oct 2005
 Rate this:
An algorithm for solving the Towers of Hanoi problem, written 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!

A list of licenses authors might use can be found here

## Share

 Software Developer Aptera Software United States
No Biography provided

## You may also be interested in...

 First Prev Next
 thanks balanjingot15-Sep-09 15:37 balanjingot 15-Sep-09 15:37
 1000 000 thanks Arak_usa12-Jun-07 3:19 Arak_usa 12-Jun-07 3:19
 Nice noobvb26-Feb-07 0:59 noobvb 26-Feb-07 0:59
 an new project for an starter like me in >NET,any suggestions r ideas abt which project to make darsc28-Jan-07 21:09 darsc 28-Jan-07 21:09
 Real World Usage Example? Coder9821-Nov-05 12:20 Coder98 21-Nov-05 12:20
 Re: Real World Usage Example? computerguru923821-Mar-06 17:33 computerguru92382 1-Mar-06 17:33
 Maybe I'm Crazy! mcofsg12-Oct-05 6:37 mcofsg 12-Oct-05 6:37
 Re: Maybe I'm Crazy! mcofsg12-Oct-05 6:42 mcofsg 12-Oct-05 6:42
 Correct....but... Matt Dowden12-Oct-05 6:21 Matt Dowden 12-Oct-05 6:21
 Re: Correct....but... BabyEmperor26-Dec-05 2:26 BabyEmperor 26-Dec-05 2:26
 Version Wouter Devinck6-Oct-05 8:44 Wouter Devinck 6-Oct-05 8:44
 Re: Version Shannon Neumann6-Oct-05 9:35 Shannon Neumann 6-Oct-05 9:35
 Re: Version Anonymous11-Oct-05 12:40 Anonymous 11-Oct-05 12:40
 Last Visit: 31-Dec-99 19:00     Last Update: 20-Jan-17 10:53 Refresh 1