Tower Of Hanoi
Hello all, this is my first post. Hope you find it useful ...
Implement
non-recursive Towers of Hanoi. Given the number n of disks as input, maintain appropriate pegs/rods to simulate the movement of the disks among the three pegs: Source, Auxilary & Destination.
Output the sequence of moves of the disks. Following is an example of the output expected by your program.
No. of disks: 3
Sequence of Moves
1. Source → Destination
2. Source → Auxilary
3. Destination → Auxilary
4. Source → Destination
5. Auxilary → Source
6. Auxilary → Destination
7. Source → Destination
Note: Remember that towers of hanoi can be solved in (2^n - 1) at the best for given n disks.
Algorithm:
While size of Destination is less not equal to n
do
{
If num of disks is even then
Make legal move between Source and Auxilary
Make the legal move between pegs Source and Destination
else
Make the legal move between pegs Source and Destination
Make the legal move between pegs Source and Auxilary
endif
Make legal move between pegs Auxilary and Destination
}
end While
Note that a legal move is one which abides by the rules of the puzzle. Only a smaller disk can be moved onto a larger disk.
Running Time Complexity :
The runtime complexity of this algorithm is O((2^n - 1)/3)
which is equivalent to O(2^n). Clearly the stack operations (push, pop and peek) have a runtime equal to O(1).
The code is given in Java.
Source Code :
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package tower.of.hanoi;
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
/**
*
* @author Shaik
*/
public class TowerOfHanoi {
public static int legalMove(Stack A, Stack B)
{
int a,b;
try {
a = Integer.parseInt(A.peek().toString());
}
catch(EmptyStackException e){
a = 0;
}
try {
b = Integer.parseInt(B.peek().toString());
}
catch(EmptyStackException e){
b = 0;
}
if(a==b) return 0;
if(a == 0) // If peg A is empty, then pop from B and push the disk onto A
{
A.push(B.pop());
return 2; // Return 2 as move occurred from B to A
}
else if(b == 0) // If peg B is empty, then pop from A and push the disk onto B
{
B.push(A.pop());
return 1; // Return 1 since move occurred from A to B
}
if(a<b)
{
B.push(A.pop());
return 1; // Return 1 since move occurred from A to B
}
else if(a > b) // value of top disk of peg A is greater than the value of topmost disk of peg B
{
A.push(B.pop());
return 2; // Return 2 since move occurred from B to A
}
return -1;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int stepNumber = 0;
int status = 0;
try {
Stack Source = new Stack();
Stack Auxilary = new Stack();
Stack Destination = new Stack();
System.out.println("Enter the number of disks : ");
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine());
if(n<=0)
{
System.out.println("Sorry wrong input, negative numbers not allowed.");
System.exit(1);
}
for(int i=n; i>0; i--)
Source.push(i);
int m = n%2;
do {
if(m==1)
{
if((status = legalMove(Source,Destination)) == 1)
System.out.println((++stepNumber) + ". Source --> Destination");
else if (status == 2)
System.out.println((++stepNumber) + ". Destination --> Source");
if((status = legalMove(Source,Auxilary)) == 1)
System.out.println((++stepNumber) + ". Source --> Auxilary");
else if(status == 2)
System.out.println((++stepNumber) + ". Auxilary --> Source");
else
break;
}
else
{
if((status = legalMove(Source,Auxilary)) == 1)
System.out.println((++stepNumber) + ". Source --> Auxilary");
else if (status == 2)
System.out.println((++stepNumber) + ". Auxilary --> Source");
if((status = legalMove(Source,Destination)) == 1)
System.out.println((++stepNumber) + ". Source --> Destination");
else if(status == 2)
System.out.println((++stepNumber) + ". Destination --> Source");
}
if((status = legalMove(Auxilary,Destination)) == 1)
System.out.println((++stepNumber) + ". Auxilary --> Destination");
else if(status == 2)
System.out.println((++stepNumber) + ". Destination --> Auxilary");
}while(Destination.size()!=n);
System.out.println("X-----------------------X");
}
catch (Exception e){
}
}
}
