C# - Tower Of Hanoi Demo Application Source Code
You can find the complete C# source code for Tower of Hanoi algorithm and demo application. Given the number of discs as input, you can visually see how the algorithm works with C# graphics.
This program is developed in C# windows application and takes the number of discs as input. It uses recursive logic to find the number of steps required to solve the problem. Initially the discs are getting added into the stack. I have 3 stacks A, B and C for 3 towers A, B and C. The function SolveTOH is used to compute all possible steps to solve the problem and the output is written on algorithm_steps list.
The demo application will use the algorithm_steps to find the next demo and graphically demonstrate how it will work.
The Big O notation for this problem is: 2^n - 1.
Click the following image to play the game online.
The complete source code, project file and executable can be found at the end of the page.
Source Code
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace Tower_of_Hanoi_Demo
{
public partial class Form1 : Form
{
static int movecount = 0;
static public void Solve2DiscsTOH(Stack<int> source, Stack<int> temp, Stack<int> dest)
{
temp.Push(source.Pop());
movecount++;
PrintStacks();
dest.Push(source.Pop());
movecount++;
PrintStacks();
dest.Push(temp.Pop());
movecount++;
PrintStacks();
}
static public bool SolveTOH(int nDiscs, Stack<int> source, Stack<int> temp, Stack<int> dest)
{
if (nDiscs <= 4)
{
if ((nDiscs % 2) == 0)
{
Solve2DiscsTOH(source, temp, dest);
nDiscs = nDiscs - 1;
if (nDiscs == 1)
return true;
temp.Push(source.Pop());
movecount++;
PrintStacks();
//new source is dest, new temp is source, new dest is temp;
Solve2DiscsTOH(dest, source, temp);
dest.Push(source.Pop());
movecount++;
PrintStacks();
//new source is temp, new temp is source, new dest is dest;
SolveTOH(nDiscs, temp, source, dest);
}
else
{
if (nDiscs == 1)
return false;
Solve2DiscsTOH(source, dest, temp);
nDiscs = nDiscs - 1;
dest.Push(source.Pop());
movecount++;
PrintStacks();
Solve2DiscsTOH(temp, source, dest);
}
return true;
}
else if (nDiscs >= 5)
{
SolveTOH(nDiscs - 2, source, temp, dest);
temp.Push(source.Pop());
movecount++;
PrintStacks();
SolveTOH(nDiscs - 2, dest, source, temp);
dest.Push(source.Pop());
movecount++;
PrintStacks();
SolveTOH(nDiscs - 1, temp, source, dest);
}
return true;
}
static public Stack<int> A = new Stack<int>();
static public Stack<int> B = new Stack<int>();
static public Stack<int> C = new Stack<int>();
public class MoveInfo
{
public string src;
public string dest;
public int number;
public MoveInfo(string s, string d, int n)
{
src = s;
dest = d;
number = n;
}
}
static public List<MoveInfo> algorithm_steps = new List<MoveInfo>();
static int currentStep = 0;
static int countA = 0;
static int countB = 0;
static int countC = 0;
static public void PrintStacks()
{
if (countA != A.Count ||
countB != B.Count ||
countC != C.Count)
{
int diffA = A.Count - countA;
int diffB = B.Count - countB;
int diffC = C.Count - countC;
if (diffA == 1)
{
if (diffB == -1)
algorithm_steps.Add(new MoveInfo("B", "A", A.Peek()));
else
algorithm_steps.Add(new MoveInfo("C", "A", A.Peek()));
}
else if (diffB == 1)
{
if (diffA == -1)
algorithm_steps.Add(new MoveInfo("A", "B", B.Peek()));
else
algorithm_steps.Add(new MoveInfo("C", "B", B.Peek()));
}
else //if (diffC == 1)
{
if (diffA == -1)
algorithm_steps.Add(new MoveInfo("A", "C", C.Peek()));
else
algorithm_steps.Add(new MoveInfo("B", "C", C.Peek()));
}
countA = A.Count;
countB = B.Count;
countC = C.Count;
Console.WriteLine();
}
}
public Form1()
{
InitializeComponent();
}
private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
{
int maxdisc = Convert.ToInt32(comboBox1.Text);
movecount = 0;
algorithm_steps.Clear();
for (int i = maxdisc; i >= 1; i--)
A.Push(i);
countA = A.Count;
countB = B.Count;
countC = C.Count;
PrintStacks();
SolveTOH(maxdisc, A, B, C);
DiscInfo d1 = new DiscInfo(40, 25, Color.Green, 1);
DiscInfo d2 = new DiscInfo(60, 30, Color.Blue, 2);
DiscInfo d3 = new DiscInfo(80, 35, Color.YellowGreen, 3);
DiscInfo d4 = new DiscInfo(100, 40, Color.Red, 4);
DiscInfo d5 = new DiscInfo(120, 45, Color.Violet, 5);
DiscInfo d6 = new DiscInfo(140, 50, Color.Purple, 6);
DiscInfo d7 = new DiscInfo(160, 55, Color.OrangeRed, 7);
DiscInfo d8 = new DiscInfo(180, 60, Color.Khaki, 8);
DiscInfo d9 = new DiscInfo(200, 65, Color.IndianRed, 9);
DiscInfo[] arrDiscs = { d1, d2, d3, d4, d5, d6, d7, d8, d9 };
towerA.Clear();
towerB.Clear();
towerC.Clear();
for (int i = maxdisc - 1; i >= 0; i--)
{
towerA.Push(arrDiscs[i]);
}
currentStep = 0;
textBox1.Text = currentStep.ToString() + " Out of " + algorithm_steps.Count.ToString();
Invalidate();
}
private void Form1_Load(object sender, EventArgs e)
{
comboBox1.Text = "6";
}
private void button1_Click(object sender, EventArgs e)
{
if (currentStep == algorithm_steps.Count)
return; // no more steps
MoveInfo info = algorithm_steps[currentStep++];
textBox1.Text = currentStep.ToString() + " Out of " + algorithm_steps.Count.ToString();
if (info.src == "A")
{
if (info.dest == "B")
towerB.Push(towerA.Pop());
else
towerC.Push(towerA.Pop());
}
else if (info.src == "B")
{
if (info.dest == "C")
towerC.Push(towerB.Pop());
else
towerA.Push(towerB.Pop());
}
else if (info.src == "C")
{
if (info.dest == "A")
towerA.Push(towerC.Pop());
else
towerB.Push(towerC.Pop());
}
Invalidate();
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
Graphics myGraphics = e.Graphics;
//myGraphics.Clear(Color.White);
int maxdisc = Convert.ToInt32(comboBox1.Text);
DrawTower(towerA, maxdisc, 120, 100, e.Graphics);
DrawTower(towerB, maxdisc, 320, 100, e.Graphics);
DrawTower(towerC, maxdisc, 520, 100, e.Graphics);
myGraphics.Dispose();
}
public class DiscInfo
{
public int width;
public int height;
public Color color;
public int number;
public Brush brush;
public DiscInfo(int w, int h, Color c, int n)
{
width = w;
height = h;
color = c;
number = n;
brush = new SolidBrush(color);
}
}
public Stack<DiscInfo> towerA = new Stack<DiscInfo>();
public Stack<DiscInfo> towerB = new Stack<DiscInfo>();
public Stack<DiscInfo> towerC = new Stack<DiscInfo>();
public void DrawTower(Stack<DiscInfo> tower, int maxDiscs, int xbeg, int ybeg, Graphics graphics)
{
Stack<DiscInfo>.Enumerator et = tower.GetEnumerator();
List<DiscInfo> drList = new List<DiscInfo>();
int yoffset = maxDiscs - tower.Count; // 6 = max disc number
while (true)
{
if (et.MoveNext() == false)
break;
drList.Add(et.Current);
}
for (int i = drList.Count - 1; i >= 0; i--)
{
Rectangle r = new Rectangle(xbeg - drList[i].number * 10, ybeg + (i + yoffset) * 10, drList[i].width, drList[i].height);
Pen p = new Pen(Color.White);
r.Y += 5;
graphics.FillEllipse(drList[i].brush, r);
graphics.DrawEllipse(p, r);
r.Y -= 5;
graphics.FillEllipse(drList[i].brush, r);
graphics.DrawEllipse(p, r);
}
}
}
}
namespace Tower_of_Hanoi_Demo
{
partial class Form1
{
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.IContainer components = null;
/// <summary>
/// Clean up any resources being used.
/// </summary>
/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.textBox1 = new System.Windows.Forms.TextBox();
this.label1 = new System.Windows.Forms.Label();
this.button1 = new System.Windows.Forms.Button();
this.label2 = new System.Windows.Forms.Label();
this.comboBox1 = new System.Windows.Forms.ComboBox();
this.SuspendLayout();
//
// textBox1
//
this.textBox1.Location = new System.Drawing.Point(108, 35);
this.textBox1.Name = "textBox1";
this.textBox1.ReadOnly = true;
this.textBox1.Size = new System.Drawing.Size(100, 20);
this.textBox1.TabIndex = 5;
//
// label1
//
this.label1.AutoSize = true;
this.label1.Location = new System.Drawing.Point(12, 38);
this.label1.Name = "label1";
this.label1.Size = new System.Drawing.Size(74, 13);
this.label1.TabIndex = 4;
this.label1.Text = "Current Move:";
//
// button1
//
this.button1.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
this.button1.Location = new System.Drawing.Point(230, 8);
this.button1.Name = "button1";
this.button1.Size = new System.Drawing.Size(103, 43);
this.button1.TabIndex = 3;
this.button1.Text = "Next Move";
this.button1.UseVisualStyleBackColor = true;
this.button1.Click += new System.EventHandler(this.button1_Click);
//
// label2
//
this.label2.AutoSize = true;
this.label2.Location = new System.Drawing.Point(12, 9);
this.label2.Name = "label2";
this.label2.Size = new System.Drawing.Size(62, 13);
this.label2.TabIndex = 6;
this.label2.Text = "Disc Count:";
//
// comboBox1
//
this.comboBox1.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
this.comboBox1.FormattingEnabled = true;
this.comboBox1.Items.AddRange(new object[] {
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9",
""});
this.comboBox1.Location = new System.Drawing.Point(108, 6);
this.comboBox1.Name = "comboBox1";
this.comboBox1.Size = new System.Drawing.Size(100, 21);
this.comboBox1.TabIndex = 7;
this.comboBox1.SelectedIndexChanged += new System.EventHandler(this.comboBox1_SelectedIndexChanged);
//
// Form1
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(621, 273);
this.Controls.Add(this.comboBox1);
this.Controls.Add(this.label2);
this.Controls.Add(this.textBox1);
this.Controls.Add(this.label1);
this.Controls.Add(this.button1);
this.Name = "Form1";
this.Text = "Tower Of Hanoi Demo Application by softwareandfinance.com";
this.Load += new System.EventHandler(this.Form1_Load);
this.Paint += new System.Windows.Forms.PaintEventHandler(this.Form1_Paint);
this.ResumeLayout(false);
this.PerformLayout();
}
#endregion
private System.Windows.Forms.TextBox textBox1;
private System.Windows.Forms.Label label1;
private System.Windows.Forms.Button button1;
private System.Windows.Forms.Label label2;
private System.Windows.Forms.ComboBox comboBox1;
}
}
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace Tower_of_Hanoi_Demo
{
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new Form1());
}
}
}
Click here to download the demo application executable
Click here to download the demo application source code and executable
Output
|
|