Tower of Hanoi code
January 16, 2013
Next greater power of 2
January 19, 2013

Non-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

  1. sai says:

    please write code for this in c language

  2. A says:

    Please write code.

  3. Ali Slt says:

    please write the code to non recursive hanoi towers 🙁

  4. Dhoomil Sheta says:

    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){
    }
    }
    }

  5. a says:

    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

  6. I want Python code for non-recursive Tower of Hanoi

  7. Abhay Gupta says:

    if total number of moves required is 2^n-1 then how come complexity of your algorithm is O(n)?

  8. Sayantan patra says:

    Easiest and fastest way

Leave a Reply to bedava Cancel reply

Your email address will not be published. Required fields are marked *