Towers of Hanoi

• Download source
• Download compiled version - 1.6 MB

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:

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);
        moves.Add(new Move(fromPole, toPole));
        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.

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;
        }
        return ToPole.AllowDisk(FromPole.getTopDisk());
    }    
    ...
}

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.

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);
    }

    public void AddDisk(Disk disk)
    {

        if (AllowDisk(disk))
        {
            disk.MoveToPole(this);
            Disks.Add(disk.Number, disk);
        }
    }
    ...
}

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.

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()
        {
            LoadImagesFromFile();
            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();
                Poles[move.ToPole.Number].AddDisk(disk);
                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

[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.

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.