Towers Of Hanoi with Stacks Implementation and Recursion (Java)

Question

I'm trying to solve the Towers of Hanoi problem through recursion, while using stacks. The output should look as follows, using n # of disks of increasing size. Disks must move from Pillar1 to Pillar3, one at a time:

// assuming n = 3;

Pillar1: 3 2 1

Pillar2:

Pillar3: 

// "\n"

Pillar1: 3 2 

Pillar2:

Pillar3: 1

// "\n"

Pillar1: 3 

Pillar2: 2

Pillar3: 1


// "\n"

Pillar1: 3 

Pillar2: 2 1

Pillar3: 


// "\n"

Pillar1: 

Pillar2: 2 1

Pillar3: 3


// "\n"

Pillar1: 1

Pillar2: 2

Pillar3: 3

// "\n"

Pillar1: 1

Pillar2: 

Pillar3: 3 2


// "\n"

Pillar1: 

Pillar2: 

Pillar3: 3 2 1

My code is below, I am having a hard time with the output with disks > 1:

import java.util.*;
class TowersOfHanoiThree
{
   public static Stack<Integer>[] tower = new Stack[4];
   public static int temp;

   public static void TowersOfHanoiThree(int numDisk)
   {
      //adding disk to stack
      temp = numDisk;
      tower = new Stack[4];

      for(int a = 0; a <= 3; a++)
      {
         tower[a] = new Stack<Integer>();
      }

     for (int i = numDisk; i > 0; i--)
     {
        tower[1].push(numDisk);
        show();
     }
     solver(numDisk, 1, 3, 2);
 }

public static void show()
{
   //System.out.println("Pillar1: ");
   //System.out.println("Pillar2: ");
   //System.out.println("Pillar3: ");

   String Pillar1 = "Pillar1: ";
   String Pillar2 = "Pillar2: ";
   String Pillar3 = "Pillar3: ";

   for(int x = temp -1 ; x >= 0 ; x--)
   {
      String emptStr1 = "";
      String emptStr2 = "";
      String emptStr3 = "";

     try
     {
        emptStr1 = String.valueOf(tower[1].get(x));
     }
     catch(Exception e)
     {
     }

     try
     {
        emptStr2 = String.valueOf(tower[2].get(x));
     }
     catch(Exception e)
     {
     }

     try
     {
        emptStr3 = String.valueOf(tower[3].get(x));
     }
     catch(Exception e)
     {
     }
     System.out.print(Pillar1+emptStr1+"\n");
     System.out.print(Pillar2+emptStr2+"\n");
     System.out.print(Pillar3+emptStr3+"\n");
     System.out.print("\n");
  }
}//end show

public static void solver(int numDisk, int start, int middle, int end) 
{
   if(numDisk > 0) 
   {
      try
      {
         //sorting disks
         solver(numDisk - 1, start, end, middle);
         int dis = tower[start].pop(); //move disk top-most disk of start
         tower[middle].push(dis);
         show();
         solver(numDisk - 1, middle, start, end);
      }
      catch(Exception e)
      {
      }
   }
}

public static void main(String args[])
{
    tower[1] = new Stack<Integer>();
    tower[2] = new Stack<Integer>();
    tower[3] = new Stack<Integer>();

    TowersOfHanoiThree(2);
}
}

Alexandru Stana · Accepted Answer · 2017-10-14 09:37:48Z

Using the following implementation should offer you the desired result. I have also placed some inline comments with the modifications made

public static void TowersOfHanoiThree(int numDisk)
{
  //adding disk to stack
  temp = numDisk;
  tower = new Stack[4];

  for(int a = 0; a <= 3; a++)
  {
     tower[a] = new Stack<Integer>();
  }

 for (int i = numDisk; i > 0; i--)
 {
    tower[1].push(i); // to show "1 2 3" i changed the value which was pushed in the stack
// from tower[1].push(numDisk) to tower[1].push(i)
 }
 show(); //In your example this method call was placed inside the for loop.
//Moving it outside will show the stacks only after the values are added
 solver(numDisk, 1, 3, 2);
}

 public static void show() {
    // System.out.println("Pillar1: ");
    // System.out.println("Pillar2: ");
    // System.out.println("Pillar3: ");

    String Pillar1 = "Pillar1: ";
    String Pillar2 = "Pillar2: ";
    String Pillar3 = "Pillar3: ";

    String emptStr1 = "";
    String emptStr2 = "";
    String emptStr3 = "";
//the empStr variable are moved outside the loop because only after the 
//loop has finished we know what values are in each pillar
    for (int x = 0; x <= temp - 1; x++) {

        try {
//here we just append the values from the pillar to string empStr1
            emptStr1 += String.valueOf(tower[1].get(x)) + " ";
        } catch (Exception e) {
        }

        try {
            emptStr2 += String.valueOf(tower[2].get(x)) + " ";
        } catch (Exception e) {
        }

        try {
            emptStr3 += String.valueOf(tower[3].get(x)) + " ";
        } catch (Exception e) {
        }
    }
//finally when the loop is done we have the results
    System.out.print(Pillar1 + emptStr1 + "\n");
    System.out.print(Pillar2 + emptStr2 + "\n");
    System.out.print(Pillar3 + emptStr3 + "\n");
    System.out.print("\n");
}// end show

d.j.brown · Accepted Answer · 2017-10-14 09:56:26Z

There are a few problems you need to address. I'll try my best to explain them and offer possible solutions.

Firstly, you always push numDisks onto your initial stack (pillar) in your TowersOfHanoiThree(int) method. The offending part:

for (int i = numDisk; i > 0; i--) {
   tower[1].push(numDisk); // should be tower[1].push(i);
   show();
}

Fix:

for (int i = numDisk; i > 0; i--) {
   tower[1].push(i); // fixed
   show();
}

Secondly, your show() method isn't correct for a number of reasons:

You should start iterating over each of your stacks in the array tower from index 0 rather than the last index (temp - 1), as you want to display the disks from the bottom to the top.
You should declare your Strings emptStr1, emptStr2, emptStr3 prior to the for loop. At present you're resetting them to empty Strings with each iteration.
You need to concatenate your disks to your Strings emptStr1, emptStr2, emptStr3, rather than overwritting them by reassignment.
You should output your Strings emptStr1, emptStr2, emptStr3 after the for loop.

I would suggest a complete re-write of show(), e.g.:

public static void show() {
    for (int i = 1; i < tower.length; i++) { // iterate over your array of stacks
        String pillar = "Pillar " + i + ":"; // e.g. "Pillar 1: "
        for (int disk : tower[i]) { // iterate over the stack located at index i
            pillar += " " + disk; // concatenate the current disk to the String
        }
        System.out.println(pillar); // Display this pillar
    }
    System.out.println(); // Line break to seperate the show() calls
}

Finally, the second recursive call in solver(int, int, int, int) is incorrect.

The offending line:

solver(numDisk - 1, middle, start, end);

This should be changed to:

solver(numDisk - 1, end, middle, start);

Additionally, whilst not a reason for failure, your array tower has a capacity of 4, but it should be 3. You're currently ignoring index 0. I presume you did this intentionally as you wanted to display pillars as 1, 2 and 3? In any case, this can be confusing. Instead, when you display your pillar information, just add 1 to your index.

Collectives™ on Stack Overflow

Towers Of Hanoi with Stacks Implementation and Recursion (Java)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related