C# - Tower Of Hanoi Algorithm Source Code
You can find the complete C# source code for Tower of Hanoi algorithm. Given the number of discs as input, you can get the print out of the list of steps you need to solve the problem.
This program is developed in C# console application and takes the number of discs as input. It uses recursive logic to find the number of steps required to solve thr 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. Note that it uses the recursive logic and the output after each move is written on the screen.
The Big O notation for this problem is: 2^n - 1.
The other related links are given below:
- Tower Of Hanoi Algorithm Source Code in Java
- Tower Of Hanoi Algorithm Source Code in C#
- Tower Of Hanoi Algorithm Source Code in Visual C++
- Tower Of Hanoi Algorithm Source Code in Turbo C++
- Tower Of Hanoi Algorithm Source Code in Turbo C
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.Text;
namespace Tower
{
class Program
{
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);
}
/***
// For your understanding purpose
if (nDiscs == 5)
{
SolveTOH(3, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(3, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(4, temp, source, dest);
}
else if(nDiscs == 6)
{
SolveTOH(4, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(4, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(5, temp, source, dest);
}
else if (nDiscs == 7)
{
SolveTOH(5, source, temp, dest);
temp.Push(source.Pop());
SolveTOH(5, dest, source, temp);
dest.Push(source.Pop());
SolveTOH(6, 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>();
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)
Console.Write("Move Disc " + A.Peek() + " From B To A");
else
Console.Write("Move Disc " + A.Peek() + " From C To A");
}
else if (diffB == 1)
{
if (diffA == -1)
Console.Write("Move Disc " + B.Peek() + " From A To B");
else
Console.Write("Move Disc " + B.Peek() + " From C To B");
}
else //if (diffC == 1)
{
if (diffA == -1)
Console.Write("Move Disc " + C.Peek() + " From A To C");
else
Console.Write("Move Disc " + C.Peek() + " From B To C");
}
countA = A.Count;
countB = B.Count;
countC = C.Count;
Console.WriteLine();
}
PrintStack(A);
Console.Write(" , ");
PrintStack(B);
Console.Write(" , ");
PrintStack(C);
Console.Write(" , ");
}
static int countA = 0;
static int countB = 0;
static int countC = 0;
static public void PrintStack(Stack<int> s)
{
Stack<int>.Enumerator et = s.GetEnumerator();
Console.Write("[");
string str = "";
while(true)
{
if(et.MoveNext() == false)
break;
str += et.Current.ToString();
}
for (int i = str.Length - 1; i >= 0; i--)
Console.Write(str[i]);
Console.Write("]");
}
static void Main(string[] args)
{
while (true)
{
Console.Write("\nEnter the number of discs (-1 to exit): ");
string s = Console.ReadLine();
movecount = 0;
int maxdisc = Convert.ToInt32(s);
if (maxdisc == -1)
{
Console.WriteLine("Good Bye!");
return;
}
if (maxdisc <= 1 || maxdisc >= 10)
{
Console.WriteLine("Enter between 2 - 9");
continue;
}
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);
Console.WriteLine("Total Moves = " + movecount);
while (C.Count > 0)
C.Pop();
}
}
}
}
Click here to download the VS2005 - C# project and executable
Output
Enter the number of discs (-1 to exit): 0
Enter between 2 - 9
Enter the number of discs (-1 to exit): 1
Enter between 2 - 9
Enter the number of discs (-1 to exit): 2
[21] , [] , [] , Move Disc 1 From A To B
[2] , [1] , [] , Move Disc 2 From A To C
[] , [1] , [2] , Move Disc 1 From B To C
[] , [] , [21] , Total Moves = 3
Enter the number of discs (-1 to exit): 3
[321] , [] , [] , Move Disc 1 From A To C
[32] , [] , [1] , Move Disc 2 From A To B
[3] , [2] , [1] , Move Disc 1 From C To B
[3] , [21] , [] , Move Disc 3 From A To C
[] , [21] , [3] , Move Disc 1 From B To A
[1] , [2] , [3] , Move Disc 2 From B To C
[1] , [] , [32] , Move Disc 1 From A To C
[] , [] , [321] , Total Moves = 7
Enter the number of discs (-1 to exit): 4
[4321] , [] , [] , Move Disc 1 From A To B
[432] , [1] , [] , Move Disc 2 From A To C
[43] , [1] , [2] , Move Disc 1 From B To C
[43] , [] , [21] , Move Disc 3 From A To B
[4] , [3] , [21] , Move Disc 1 From C To A
[41] , [3] , [2] , Move Disc 2 From C To B
[41] , [32] , [] , Move Disc 1 From A To B
[4] , [321] , [] , Move Disc 4 From A To C
[] , [321] , [4] , Move Disc 1 From B To C
[] , [32] , [41] , Move Disc 2 From B To A
[2] , [3] , [41] , Move Disc 1 From C To A
[21] , [3] , [4] , Move Disc 3 From B To C
[21] , [] , [43] , Move Disc 1 From A To B
[2] , [1] , [43] , Move Disc 2 From A To C
[] , [1] , [432] , Move Disc 1 From B To C
[] , [] , [4321] , Total Moves = 15
Enter the number of discs (-1 to exit): 5
[54321] , [] , [] , Move Disc 1 From A To C
[5432] , [] , [1] , Move Disc 2 From A To B
[543] , [2] , [1] , Move Disc 1 From C To B
[543] , [21] , [] , Move Disc 3 From A To C
[54] , [21] , [3] , Move Disc 1 From B To A
[541] , [2] , [3] , Move Disc 2 From B To C
[541] , [] , [32] , Move Disc 1 From A To C
[54] , [] , [321] , Move Disc 4 From A To B
[5] , [4] , [321] , Move Disc 1 From C To B
[5] , [41] , [32] , Move Disc 2 From C To A
[52] , [41] , [3] , Move Disc 1 From B To A
[521] , [4] , [3] , Move Disc 3 From C To B
[521] , [43] , [] , Move Disc 1 From A To C
[52] , [43] , [1] , Move Disc 2 From A To B
[5] , [432] , [1] , Move Disc 1 From C To B
[5] , [4321] , [] , Move Disc 5 From A To C
[] , [4321] , [5] , Move Disc 1 From B To A
[1] , [432] , [5] , Move Disc 2 From B To C
[1] , [43] , [52] , Move Disc 1 From A To C
[] , [43] , [521] , Move Disc 3 From B To A
[3] , [4] , [521] , Move Disc 1 From C To B
[3] , [41] , [52] , Move Disc 2 From C To A
[32] , [41] , [5] , Move Disc 1 From B To A
[321] , [4] , [5] , Move Disc 4 From B To C
[321] , [] , [54] , Move Disc 1 From A To C
[32] , [] , [541] , Move Disc 2 From A To B
[3] , [2] , [541] , Move Disc 1 From C To B
[3] , [21] , [54] , Move Disc 3 From A To C
[] , [21] , [543] , Move Disc 1 From B To A
[1] , [2] , [543] , Move Disc 2 From B To C
[1] , [] , [5432] , Move Disc 1 From A To C
[] , [] , [54321] , Total Moves = 31
Enter the number of discs (-1 to exit): 6
[654321] , [] , [] , Move Disc 1 From A To B
[65432] , [1] , [] , Move Disc 2 From A To C
[6543] , [1] , [2] , Move Disc 1 From B To C
[6543] , [] , [21] , Move Disc 3 From A To B
[654] , [3] , [21] , Move Disc 1 From C To A
[6541] , [3] , [2] , Move Disc 2 From C To B
[6541] , [32] , [] , Move Disc 1 From A To B
[654] , [321] , [] , Move Disc 4 From A To C
[65] , [321] , [4] , Move Disc 1 From B To C
[65] , [32] , [41] , Move Disc 2 From B To A
[652] , [3] , [41] , Move Disc 1 From C To A
[6521] , [3] , [4] , Move Disc 3 From B To C
[6521] , [] , [43] , Move Disc 1 From A To B
[652] , [1] , [43] , Move Disc 2 From A To C
[65] , [1] , [432] , Move Disc 1 From B To C
[65] , [] , [4321] , Move Disc 5 From A To B
[6] , [5] , [4321] , Move Disc 1 From C To A
[61] , [5] , [432] , Move Disc 2 From C To B
[61] , [52] , [43] , Move Disc 1 From A To B
[6] , [521] , [43] , Move Disc 3 From C To A
[63] , [521] , [4] , Move Disc 1 From B To C
[63] , [52] , [41] , Move Disc 2 From B To A
[632] , [5] , [41] , Move Disc 1 From C To A
[6321] , [5] , [4] , Move Disc 4 From C To B
[6321] , [54] , [] , Move Disc 1 From A To B
[632] , [541] , [] , Move Disc 2 From A To C
[63] , [541] , [2] , Move Disc 1 From B To C
[63] , [54] , [21] , Move Disc 3 From A To B
[6] , [543] , [21] , Move Disc 1 From C To A
[61] , [543] , [2] , Move Disc 2 From C To B
[61] , [5432] , [] , Move Disc 1 From A To B
[6] , [54321] , [] , Move Disc 6 From A To C
[] , [54321] , [6] , Move Disc 1 From B To C
[] , [5432] , [61] , Move Disc 2 From B To A
[2] , [543] , [61] , Move Disc 1 From C To A
[21] , [543] , [6] , Move Disc 3 From B To C
[21] , [54] , [63] , Move Disc 1 From A To B
[2] , [541] , [63] , Move Disc 2 From A To C
[] , [541] , [632] , Move Disc 1 From B To C
[] , [54] , [6321] , Move Disc 4 From B To A
[4] , [5] , [6321] , Move Disc 1 From C To A
[41] , [5] , [632] , Move Disc 2 From C To B
[41] , [52] , [63] , Move Disc 1 From A To B
[4] , [521] , [63] , Move Disc 3 From C To A
[43] , [521] , [6] , Move Disc 1 From B To C
[43] , [52] , [61] , Move Disc 2 From B To A
[432] , [5] , [61] , Move Disc 1 From C To A
[4321] , [5] , [6] , Move Disc 5 From B To C
[4321] , [] , [65] , Move Disc 1 From A To B
[432] , [1] , [65] , Move Disc 2 From A To C
[43] , [1] , [652] , Move Disc 1 From B To C
[43] , [] , [6521] , Move Disc 3 From A To B
[4] , [3] , [6521] , Move Disc 1 From C To A
[41] , [3] , [652] , Move Disc 2 From C To B
[41] , [32] , [65] , Move Disc 1 From A To B
[4] , [321] , [65] , Move Disc 4 From A To C
[] , [321] , [654] , Move Disc 1 From B To C
[] , [32] , [6541] , Move Disc 2 From B To A
[2] , [3] , [6541] , Move Disc 1 From C To A
[21] , [3] , [654] , Move Disc 3 From B To C
[21] , [] , [6543] , Move Disc 1 From A To B
[2] , [1] , [6543] , Move Disc 2 From A To C
[] , [1] , [65432] , Move Disc 1 From B To C
[] , [] , [654321] , Total Moves = 63
Enter the number of discs (-1 to exit): -1
Good Bye!
|
|