I have this weird issue whenever my program attempts to solve the Tower of Hanoi puzzle. Whenever it tries to solve it, it will move the first two discs over to the end pole (the pole all the way to the right), but it will move the remainder of the discs back to the starting pole. For example, if I have a Tower of Hanoi with 10 discs, it will move the first several discs from the start pole, but only the top 2 make it to the end pole. The rest of the discs end up back on the first pole. When it does this, it gives me an index out of bounds error. I am not sure what is going wrong with it, and any help would be greatly appreciated. Thanks in advance.
public class TowerOfHanoi
{
private int[] towerOne;
private int[] towerTwo;
private int[] towerThree;
private int discOne;
private int discTwo;
private int discThree;
/* Construct the Towers of Hanoi (3 towers) with aNumDisc
* on the first tower. Each tower can be identified by an
* integer number (0 for the first tower, 1 for the second
* tower, and 2 for the third tower). Each disc can be identified
* by an integer number starting from 0 (for the smallest disc)
* and (aNumDisc - 1) for the largest disc.
*/
public TowerOfHanoi(int aNumDiscs)
{
towerOne = new int[aNumDiscs];
for(int i = 0; i < aNumDiscs; i++){
towerOne[i] = aNumDiscs - 1 - i;
}
towerTwo = new int[aNumDiscs];
towerTwo[0] = aNumDiscs;
towerThree = new int[aNumDiscs];
towerThree[0] = aNumDiscs;
discOne = aNumDiscs;
discTwo = 0;
discThree = 0;
}
/* Returns an array of integer representing the order of
* discs on the tower (from bottom up). The bottom disc should
* be the first element in the array and the top disc should be
* the last element of the array. The size of the array MUST
* be the number of discs on the tower. For example, suppose
* the tower 0 contains the following discs 0,1,4,6,7,8 (from top
* to bottom). This method should return the array [8,7,6,4,1,0]
* (from first to last).
* @param tower the integer identify the tower number.
* @return an array of integer representing the order of discs.
*/
public int[] getArrayOfDiscs(int tower)
{
int[] tempTower;
if(tower == 0){
tempTower = new int[discOne];
for(int i = 0; i < discOne; i++){
tempTower[i] = towerOne[i];
}
return tempTower;
}
if(tower == 1){
tempTower = new int[discTwo];
for(int i = 0; i < discTwo; i++){
tempTower[i] = towerTwo[i];
}
return tempTower;
}
if(tower == 2){
tempTower = new int[discThree];
for(int i = 0; i < discThree; i++){
tempTower[i] = towerThree[i];
}
return tempTower;
}
return towerOne;
}
/* Gets the total number of discs in this Towers of Hanoi
* @return the total number of discs in this Towers of Hanoi
*/
public int getNumberOfDiscs()
{
return discOne+discTwo+discThree;
}
/* Gets the number of discs on a tower.
* @param tower the tower identifier (0, 1, or 2)
* @return the number of discs on the tower.
*/
public int getNumberOfDiscs(int tower)
{
if(tower == 0){
return discOne;
}
if(tower == 1){
return discTwo;
}
if(tower == 2){
return discThree;
}
return 0;
}
/* Moves the top disc from fromTower to toTower. Note that
* this operation has to follow the rule of the Tower of Hanoi
* puzzle. First fromTower must have at least one disc and second
* the top disc of toTower must not be smaller than the top disc
* of the fromTower.
* @param fromTower the source tower
* @param toTower the destination tower
* @return true if successfully move the top disc from
* fromTower to toTower.
*/
public boolean moveTopDisc(int fromTower, int toTower)
{
if((fromTower == 0 && discOne == 0)||(fromTower == 1 && discTwo == 0) || (fromTower == 2 && discThree == 0)){
return false;
}
if(fromTower == 0){
if(toTower == 1){
if(discTwo != 0&&towerOne[discOne-1]>towerTwo[discTwo-1]){
return false;
}
else{
towerTwo[discTwo]=towerOne[discOne-1];
towerOne[discOne-1] = 0;
discOne--;
discTwo++;
return true;
}
}
if(toTower == 2){
if(discThree != 0&&towerOne[discOne-1] > towerThree[discThree-1]){
return false;
}
else{
towerThree[discThree] = towerOne[discOne-1];
towerOne[discOne-1] = 0;
discOne--;
discThree++;
return true;
}
}
}
if(fromTower == 1){
if(toTower == 0){
if(discOne != 0&&towerTwo[discTwo-1]>towerOne[discOne-1]){
return false;
}
else{
towerOne[discOne]=towerTwo[discTwo-1];
towerTwo[discTwo-1] = 0;
discTwo--;
discOne++;
return true;
}
}
if(toTower == 2){
if(discThree!= 0&&towerTwo[discTwo-1] > towerThree[discThree-1]){
return false;
}
else{
towerThree[discThree] = towerTwo[discTwo-1];
towerTwo[discTwo-1] = 0;
discTwo--;
discThree++;
return true;
}
}
}
if(fromTower == 2){
if(toTower == 0){
if(discOne !=0 && towerOne[discOne-1]>towerTwo[discTwo-1]){
return false;
}
else{
towerOne[discOne]=towerThree[discThree-1];
towerThree[discThree-1] = 0;
discThree--;
discOne++;
return true;
}
}
if(toTower == 1){
if(discThree !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){
return false;
}
else{
towerTwo[discTwo] = towerThree[discThree-1];
towerThree[discThree-1] = 0;
discThree--;
discTwo++;
return true;
}
}
}
return false;
}
}
This is the class I am using to run the program above.
import javax.swing.JFrame;
public class THSolverFrame
{
public static void main(String[] args) throws InterruptedException
{
int numberOfDiscs = 10;
TowerOfHanoi towers = new TowerOfHanoi(numberOfDiscs);
THComponent thc = new THComponent(towers);
JFrame frame = new JFrame();
frame.setTitle("Tower of Hanoi");
frame.setSize(500,500);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(thc);
frame.setVisible(true);
Thread.sleep(5000);
solveTower(towers, thc, numberOfDiscs, 0, 1, 2);
System.out.println("DONE!!!");
}
public static void solveTower(TowerOfHanoi towers, THComponent thc, int numberOfDiscs, int startPole, int tempPole, int endPole) throws InterruptedException
{
if(numberOfDiscs == 1) {
towers.moveTopDisc(startPole, endPole);
thc.repaint();
Thread.sleep(100);
}
else {
solveTower(towers, thc, numberOfDiscs - 1, startPole, endPole, tempPole);
towers.moveTopDisc(startPole, endPole);
thc.repaint();
Thread.sleep(100);
solveTower(towers, thc, numberOfDiscs - 1, tempPole, startPole, endPole);
}
}
}
I tracked it down to two lines in your moveTopDisk() method. First one was this:
if(fromTower == 2){
if(toTower == 0){
if(discOne !=0 && towerOne[discOne-1]>towerTwo[discTwo-1]){ <---- HERE
The third If statement here is trying to access towerTwo when it should be using towerThree and discThree so I changed it to this:
if (fromTower == 2) {
if (toTower == 0) {
if (discOne != 0 && towerOne[discOne - 1] > towerThree[discThree - 1]) {
The way it was before, the code was trying to pull a disc from a tower without any discs on it and causing the error. After running it again, I found another such typo within the same area. :
if(toTower == 1){
if(discThree !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){
This second If statement is targeting discThree, when it should be using discTwo.
if(toTower == 1){
if(discTwo !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){
After these changes, the code ran for me, error free. The only issue I had after that is that it was unable to solve the puzzle! The algorithm is not able to solve the puzzle for anything above 3 discs. I tried it with 3, 4, 5, and 10 and it only solved it for 3. With 4 and 5, the program stopped, but was not in a winning configuration and when I tried it with 10, it only managed to shuffle the first 3 discs around and never come to a solution (I let it run for a solid 5 minutes just in case).
TL;DR My only suggestions are to be careful of copy/pasting, be mindful of whether you are using a zero-index or not, and you should take a look at your algorithm again to see if it can actually solve the puzzle. I myself have not written anything to do the Hanoi puzzle, so I'm not familiar with how to implement it in code. I do see that you have the idea though. That being that to solve the puzzle for n discs, you first have to solve it for n-1 discs. Good luck on the rest of your work!