Tower of Hanoi code
January 16, 2013Next greater power of 2
January 19, 2013Non-recursive solution to tower of hanoi
We discussed problem of Tower of Hanoi earlier and written a recursive function to solve the problem, Recursive functions take lot of extra memory (New activation record for each call on the stack) (A detailed analysis of recursion is done in this post of mine).
Todays question is to write a Non-recursive function to solve problem of Tower Of Hanoi.
The function should not take more than O(n) time (n = number of Moves actually required to solve the problem) and O(1) extra space.
The signature of the function will be
/* The three char represents the characters representing three rods * and n is the number of discs (initially in s) */ void towerOfHanoi(char s, char d, char e, unsigned int n)
Solution:
If there are n discs in a Tower Of Hanoi puzzle, then the total number of moves required to solve the puzzle will be 2n – 1.
The solution to this problem is required some moves to be repeated depending on whether n is even or odd and it is based on the below fact
At any given time, there is only one legal move between any two pegs.
Algorithm:
Repeat below steps till the total number of moves becomes 2^n - 1
If (n is even)
Make_move (S, E)
Make_move (S, D)
Make_move (E, D)
Else
Make_move (S, D)
Make_move (S, E)
Make_move (E, D)
The function Make_move is a simple function that will make the legal move between the two pegs (the only possible move)
I know you can write the code for this.. so am leaving it to you. If you want me to write the code also, please drop a comment
8 Comments
please write code for this in c language
Please write code.
please write the code to non recursive hanoi towers 🙁
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
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)
{
A.push(B.pop());
return 2;
}
else if(b == 0)
{
B.push(A.pop());
return 1;
}
if(a b)
{
A.push(B.pop());
return 2;
}
return -1;
}
public static void main(String[] args) {
int stepNumber = 0;
int status = 0;
try {
Stack A = new Stack();
Stack B = new Stack();
Stack C = 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(n0; i–)
A.push(i);
int m = n%2;
do {
if(m==1)
{
if((status = legalMove(A,C)) == 1)
System.out.println((++stepNumber) + “. A –> C”);
else if (status == 2)
System.out.println((++stepNumber) + “. C –> A”);
if((status = legalMove(A,B)) == 1)
System.out.println((++stepNumber) + “. A –> B”);
else if(status == 2)
System.out.println((++stepNumber) + “. B –> A”);
else
break;
}
else
{
if((status = legalMove(A,B)) == 1)
System.out.println((++stepNumber) + “. A –> B”);
else if (status == 2)
System.out.println((++stepNumber) + “. B –> A”);
if((status = legalMove(A,C)) == 1)
System.out.println((++stepNumber) + “. A –> C”);
else if(status == 2)
System.out.println((++stepNumber) + “. C –> A”);
}
if((status = legalMove(B,C)) == 1)
System.out.println((++stepNumber) + “. B –> C”);
else if(status == 2)
System.out.println((++stepNumber) + “. C –> B”);
}while(C.size()!=n);
System.out.println(“X———————–X”);
}
catch (Exception e){
}
}
}
with 3 rods and 10 disks your algorithm needs 29523 moves to finish.
with 11 disks it loops with a finished rod in the center
if i reverse the move_number %2 == 0, it needs 88572 moves on 11 disks
I want Python code for non-recursive Tower of Hanoi
if total number of moves required is 2^n-1 then how come complexity of your algorithm is O(n)?
Easiest and fastest way