# Interview Questions

# Non-recursive solution to tower of hanoi

- January 17, 2013
- Posted by: Kamal Rawat
- Category: Algorithms Articles

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 2^{n} – 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

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

}

}

}

please write the code to non recursive hanoi towers 🙁

Please write code.

please write code for this in c language