Java iterative program to solve Tower of Hanoi puzzle.

For 3 discs the output is:

   |         |         |      
   #         |         |      
  ###        |         |      
 #####       |         |      
TTTTTTT   TTTTTTT   TTTTTTT   

0. Moved disc 1 from tower 0 to tower 1
   |         |         |      
   |         |         |      
  ###        |         |      
 #####       #         |      
TTTTTTT   TTTTTTT   TTTTTTT   

1. Moved disc 2 from tower 0 to tower 2
   |         |         |      
   |         |         |      
   |         |         |      
 #####       #        ###     
TTTTTTT   TTTTTTT   TTTTTTT   

2. Moved disc 1 from tower 1 to tower 2
   |         |         |      
   |         |         |      
   |         |         #      
 #####       |        ###     
TTTTTTT   TTTTTTT   TTTTTTT   

3. Moved disc 3 from tower 0 to tower 1
   |         |         |      
   |         |         |      
   |         |         #      
   |       #####      ###     
TTTTTTT   TTTTTTT   TTTTTTT   

4. Moved disc 1 from tower 2 to tower 0
   |         |         |      
   |         |         |      
   |         |         |      
   #       #####      ###     
TTTTTTT   TTTTTTT   TTTTTTT   

5. Moved disc 2 from tower 2 to tower 1
   |         |         |      
   |         |         |      
   |        ###        |      
   #       #####       |      
TTTTTTT   TTTTTTT   TTTTTTT   

6. Moved disc 1 from tower 0 to tower 1
   |         |         |      
   |         #         |      
   |        ###        |      
   |       #####       |      
TTTTTTT   TTTTTTT   TTTTTTT   

8. Moved disc 1 from tower 1 to tower 2
   |         |         |      
   |         |         |      
   |        ###        |      
   |       #####       #      
TTTTTTT   TTTTTTT   TTTTTTT   

9. Moved disc 2 from tower 1 to tower 0
   |         |         |      
   |         |         |      
   |         |         |      
  ###      #####       #      
TTTTTTT   TTTTTTT   TTTTTTT   

10. Moved disc 1 from tower 2 to tower 0
   |         |         |      
   |         |         |      
   #         |         |      
  ###      #####       |      
TTTTTTT   TTTTTTT   TTTTTTT   

11. Moved disc 3 from tower 1 to tower 2
   |         |         |      
   |         |         |      
   #         |         |      
  ###        |       #####    
TTTTTTT   TTTTTTT   TTTTTTT   

12. Moved disc 1 from tower 0 to tower 1
   |         |         |      
   |         |         |      
   |         |         |      
  ###        #       #####    
TTTTTTT   TTTTTTT   TTTTTTT   

13. Moved disc 2 from tower 0 to tower 2
   |         |         |      
   |         |         |      
   |         |        ###     
   |         #       #####    
TTTTTTT   TTTTTTT   TTTTTTT   

14. Moved disc 1 from tower 1 to tower 2
   |         |         |      
   |         |         #      
   |         |        ###     
   |         |       #####    
TTTTTTT   TTTTTTT   TTTTTTT

Main.java

import java.util.Scanner;

// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        System.out.println("Hanoi solver iterative algorithm");
        System.out.println("TheFlyingKeyboard.net 2018");
        System.out.println("Enter number of discs:");

        HanoiSolver hanoiSolver = new HanoiSolver(reader.nextInt());
        hanoiSolver.solve();
    }
}

HanoiSolver.java

// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class HanoiSolver {
    private Tower[] towers = new Tower[3];
    private int discsCount;

    public HanoiSolver(int discsCount) {
        this.discsCount = discsCount;

        for (int i = 0; i < towers.length; ++i) {
            towers[i] = new Tower(discsCount);
        }

        fillFirstTower();
    }

    private void fillFirstTower() {
        for (int i = discsCount; i > 0; --i) {
            towers[0].place(i);
        }
    }

    public void solve() {
        printTowers();

        for (int i = 0; i < (2 << discsCount) - 1; ++i) {
            if (i % 2 == 0) {
                moveDiscOne(i);
            } else {
                moveSmallest(i);
            }
        }
    }

    private void moveDiscOne(int count) {
        int smallestIndex = findDiscOne();

        towers[smallestIndex].removeTop();

        if (smallestIndex == towers.length - 1) {
            towers[0].place(1);
            printMove(count, 1, smallestIndex, 0);
        } else {
            towers[smallestIndex + 1].place(1);
            printMove(count, 1, smallestIndex, smallestIndex + 1);
        }

        printTowers();
    }

    private void moveSmallest(int count) {
        int smallestIndex = findSmallest();
        boolean canPlace = false;

        for (int j = 0; j < towers.length; ++j) {
            if (towers[smallestIndex].isEmpty()) {
                break;
            }

            if (towers[j].isEmpty()) {
                canPlace = true;
            } else {
                canPlace = towers[j].getTop() > towers[smallestIndex].getTop();
            }

            if (canPlace) {
                printMove(count, towers[smallestIndex].getTop(), smallestIndex, j);

                towers[j].place(towers[smallestIndex].removeTop());

                printTowers();
                break;
            }
        }
    }

    private int findDiscOne() {
        for (int i = 0; i < towers.length; ++i) {
            if (!towers[i].isEmpty()) {
                if (towers[i].getTop() == 1) {
                    return i;
                }
            }
        }

        return -1;
    }

    private int findSmallest() {
        int smallest = discsCount + 1;
        int index = 0;

        for (int i = 0; i < towers.length; ++i) {
            if (!towers[i].isEmpty()) {
                if (towers[i].getTop() < smallest && towers[i].getTop() != 1) {
                    smallest = towers[i].getTop();
                    index = i;
                }
            }
        }

        return index;
    }

    private void printTowers() {
        int height = towers[0].getTowerChars().getHeight();

        for (int i = 0; i < height; ++i) {
            for (int j = 0; j < towers.length; ++j) {
                System.out.print(towers[j].getTowerChars().getRow(i) + "   ");
            }

            System.out.println();
        }

        System.out.println();
    }

    private void printMove(int count, int disc, int from, int to) {
        System.out.println(count + ". Moved disc " + disc + " from tower " + from + " to tower " + to);
    }
}

Tower.java

import java.util.Stack;

// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class Tower {
    private Stack<Integer> discs = new Stack<Integer>();
    private TowerChars towerChars;

    public Tower(int discsCount) {
        towerChars = new TowerChars(discsCount);
    }

    public TowerChars getTowerChars() {
        return towerChars;
    }

    public void place(int disc) {
        discs.push(disc);
        towerChars.place(disc);
    }

    public int removeTop() {
        towerChars.remove();
        return discs.pop();
    }

    public int getTop() {
        return discs.peek();
    }

    public boolean isEmpty() {
        return discs.isEmpty();
    }
}

TowerChars.java

// 2018 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class TowerChars {
    private final char discChar = '#';
    private final char poleChar = '|';
    private final char baseChar = 'T';
    private final char emptyChar = ' ';

    private int currentDiscHeight;
    private char[][] tower;

    public TowerChars(int discCount) {
        tower = new char[discCount + 2][discCount * 2 + 1];

        for (int i = 0; i < discCount + 1; ++i) {
            for (int j = 0; j < tower[i].length; ++j) {
                tower[i][j] = j == tower[i].length / 2 ? poleChar : emptyChar;
            }
        }

        for (int i = 0; i < tower[0].length; ++i) {
            tower[tower.length - 1][i] = baseChar;
        }

        currentDiscHeight = tower.length - 1;
    }

    public void place(int disc) {
        --currentDiscHeight;

        disc = disc * 2 - 1;

        int emptySpace = (tower[0].length - disc) / 2;

        for (int i = 0; i < disc; ++i) {
            tower[currentDiscHeight][i + emptySpace] = discChar;
        }
    }

    public void remove() {
        for (int i = 0; i < tower[0].length; ++i) {
            tower[currentDiscHeight][i] = emptyChar;
        }

        tower[currentDiscHeight][tower[0].length / 2] = poleChar;
        ++currentDiscHeight;
    }

    public String getRow(int row) {
        return new String(tower[row]);
    }

    public int getHeight() {
        return tower.length;
    }
}

 



Java Hanoi Iterative Solver ASCII Graphics
Tagged on:             

Leave a Reply

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

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close