Jan 172013
 

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

  4 Responses to “Non-recursive solution to tower of hanoi”

Comments (4)
  1. 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){
    }
    }
    }

  2. please write the code to non recursive hanoi towers 🙁

  3. Please write code.

  4. please write code for this in c language

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)