15,610,998 members
Articles / General Programming / Algorithms
Article
Posted 28 May 2012

104.9K views
67 bookmarked

# Towers of Hanoi

Rate me:
Solution of the Towers of Hanoi problem.

## Introduction

This article contains a recursive solution for the Towers of Hanoi problem. The application is written in C# and the UI is done using Windows Forms.

## The requirements

1. A graphical representation, using Windows forms, of the puzzle.
2. The user should be able to choose if they would like to use 3,4,5,6 disks* in the puzzle. There will always be three poles** present.
3. The application should allow only valid moves – as defined by these rules:
• You may only move one disk at a time
• You cannot place a bigger disk on a smaller disk
4. The application must have a 'Show Me' feature where the application will show the user the solution, step by step, for the selected number of disks.

For more about the puzzle see: Tower of Hanoi

* The term disk is used throughout the article to describe the movable parts of the puzzle.

** The term pole is used to describe the pegs, containing the disks.

## The design

I wanted a clear separation between the UI and the backend. I created the `MoveCalculator` class with the sole purpose of working on the solution. The `GameState` class would handle the game mechanics and the `GameForm` would drive the front end, with the help of a few controls.

I wanted the `MoveCalculator` to return something useful to the `GameState`, so the Move class was introduced. The `MoveCalculator` would return a list of moves and the `GameState` would make them.

#### UI elements

The `GameForm` contains all the graphical components and servers as the driver for the application. I wanted to use the PictureBox control as the base object for the disks and poles, but needed more, so I extended the PictureBox control. The Pole PictureBox had to keep track of the disks on itself, by maintaining a sorted list of disks. The Disk PictureBox got the responsibility to move itself around. I also added drop and drag functionality to make the game more enjoyable.

#### Solver Algorithm

The algorithm used to solve the puzzle is a very simple recursive function. In the function each move gets add to a list. This list gets used to solve the puzzle.

In the start state of the game all the disks will be on the 'start pole'. After executing all the moves in the list, all the disks should be on the 'end pole'.

## The code

Here follows five snippets from the application:

The `MoveCalculator` class takes in the amount of disks that the user wants to play with and returns a list of moves needed to solve the puzzle.

Snippet 1: The recursive `Calculate` method:

C#
```public static class MoveCalculator
{
private static void Calculate(int n, int fromPole, int toPole)
{
if (n == -1)
{
return; // We are done
}
int intermediatePole = GetIntermediatePole(fromPole, toPole);

Calculate(n - 1, fromPole, intermediatePole);
Calculate(n - 1, intermediatePole, toPole);
}
...
}   ```

Snippet 2: A `Move` contains a `FromPole` and a `ToPole`. Since we will always move the disk on the top of the `FromPole`, the two poles are all we need.

`Move` also contains information about itself like `AffectCount` and `IsValid`.

C#
```public class Move
{
public Pole FromPole { get; set; }
public Pole ToPole { get; set; }

public bool AffectCount()
{
//If the poles don't change the move should not be counted
if (ToPole.Equals(FromPole))
{
return false;
}
return IsValid();
}

public bool IsValid()
{
//Allow a move where the pole dont change
if (ToPole.Equals(FromPole))
{
return true;
}
}
...
}```

Snippet 3: The UI makes use of two custom PictureBox controls: `Pole` and `Disk`.

Where a `Disk` is movable from one `Pole` to the next. And a `Pole` contains a list of Disks.

C#
```public class Disk : PictureBox
{
public int Number { get; set; }

public Disk(int Number) : base()
{ ... }

public void MoveToPole(Pole DestinationPole)
{ ... }
}

public class Pole : PictureBox
{
public SortedList<int, Disk> Disks { get; set; }
public int Number { get; set; }

public Pole(int number)
{
...
}

public bool IsEmpty()
{
return Disks.Count == 0;
}

public bool AllowDisk(Disk disk)
{
if (disk == null)
{
return false;
}
if (Disks.Count == 0)
{
return true;
}
return getTopDisk().Number > disk.Number;
}

public Disk getTopDisk()
{
if (Disks.Count > 0)
{
return Disks.First().Value;
}
return null;
}

public void RemoveDisk()
{
Disks.Remove(Disks.First().Key);
}

{

if (AllowDisk(disk))
{
disk.MoveToPole(this);
}
}
...
}```

Snippet 4: To keep information regarding the state of the game, the `GameState` class was added.

The `GameState` should start a game, execute moves and checks for completion.

C#
```public static class GameState
{
public static List<Pole> Poles = new List<Pole>();
public static List<Bitmap> ImageList = new List<Bitmap>();
public static int MoveCount { get; set; }
public static int NumberOfDisks { get; set; }

// Start the game
static GameState()
{
RestartGame(3);
}

public static int Move(Move move)
{
if (move.AffectCount())
{
MoveCount++;
}

if (move.IsValid())
{
Disk disk = move.FromPole.getTopDisk();
Poles[move.FromPole.Number].RemoveDisk();
return MoveCount;
}

else //Invalid move
{
return -1;
}
}

public static bool IsSolved()
{
return (Poles[Properties.Settings.Default.EndPole].Disks.Count == NumberOfDisks);
}
}```

Snippet 5: Unit tests for the two classes containing the most logic: `MoveCalculator` & `GameState`

C#
```[TestClass()]
public class MoveCalculatorTest {
...
[TestMethod()]
public void GetMoveCountTest()
{
int actualMoveCount = MoveCalculator.GetMoveCount(3);
int expectedMoveCount = 7;
Assert.AreEqual(expectedMoveCount, actualMoveCount);

actualMoveCount = MoveCalculator.GetMoveCount(4);
expectedMoveCount = 15;
Assert.AreEqual(expectedMoveCount, actualMoveCount);

actualMoveCount = MoveCalculator.GetMoveCount(5);
expectedMoveCount = 31;
Assert.AreEqual(expectedMoveCount, actualMoveCount);
}
}

[TestClass()]
public class GameStateTest  {
...
[TestMethod()]
public void IsSolvedTest()
{
GameState.RestartGame(numberOfDisks);

bool expectedBefore = false;
bool actualBefore = GameState.IsSolved();
solveGame();
bool expectedAfter = true;
bool actualAfter = GameState.IsSolved();

//Assert
Assert.AreEqual(expectedBefore, actualBefore);
Assert.AreEqual(expectedAfter, actualAfter);
}
}```

## Notes

I wanted to encapsulate information like the position of each disk, in the `Disk` class itself.

C#
```public void MoveToPole(Pole DestinationPole)
{
int numberOfRungsOnSelectedPole = DestinationPole.Disks.Count;

int x = (DestinationPole.Location.X + DestinationPole.Width) -
(DestinationPole.Width / 2)  - (this.Size.Width / 2);
int y = DestinationPole.Location.Y + DestinationPole.Size.Height -
((numberOfRungsOnSelectedPole + 1) * this.Size.Height) -
toh.Properties.Resources._base.Size.Height;
this.Location = new Point(x, y);
}   ```

I added the `MoveToPole` method which basically moves the disk to a pole, by simply setting its location. To get the correct point for the disk to move to, I needed to know to which pole its moving and where on the pole it should sit. Since each Pole contains the information about the number of disks it contains, I simply took in the `DestinationPole`. The code assumes that all the disks have the same height; the same as the current disk.

Written By
Code Rain
South Africa
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 Framework problem Theios D Coder26-Feb-23 15:06 Theios D Coder 26-Feb-23 15:06
 this is great kaijia mouledoux25-Apr-16 4:17 kaijia mouledoux 25-Apr-16 4:17
 Good Article PANKAJMAURYA4-Nov-15 19:56 PANKAJMAURYA 4-Nov-15 19:56
 My vote 5 SOHAM_GANDHI6-Apr-14 20:25 SOHAM_GANDHI 6-Apr-14 20:25
 My vote of 5 Champion Chen24-Sep-13 15:49 Champion Chen 24-Sep-13 15:49
 My vote of 5 Er. Abhinav Kumar Singh23-Sep-13 20:47 Er. Abhinav Kumar Singh 23-Sep-13 20:47
 My vote of 5 Carsten V2.023-Sep-13 3:51 Carsten V2.0 23-Sep-13 3:51
 Source code cannot be downloaded Member 1029165023-Sep-13 1:09 Member 10291650 23-Sep-13 1:09
 My vote of 5 Florian Rosmann22-Sep-13 0:43 Florian Rosmann 22-Sep-13 0:43
 Re: My vote of 5 Atalia Beukes23-Sep-13 7:12 Atalia Beukes 23-Sep-13 7:12
 Hi Florian, I added a compiled version of the demo. If you download and unzip it, you should be able to run the exe. Thanks
 Re: My vote of 5 Florian Rosmann23-Sep-13 10:59 Florian Rosmann 23-Sep-13 10:59
 My vote of 5 Farhan Ghumra11-Jul-12 2:49 Farhan Ghumra 11-Jul-12 2:49
 nice BillW331-Jun-12 5:49 BillW33 1-Jun-12 5:49
 How about other numbers of towers supercat929-May-12 7:40 supercat9 29-May-12 7:40
 Re: How about other numbers of towers Atalia Beukes31-May-12 4:21 Atalia Beukes 31-May-12 4:21
 My vote of 5 sravani.v29-May-12 1:35 sravani.v 29-May-12 1:35
 My vote of 5 micky_bird8628-May-12 15:19 micky_bird86 28-May-12 15:19
 My vote of 5 Filip D'haene28-May-12 7:53 Filip D'haene 28-May-12 7:53
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Mar-23 7:56 Refresh 1