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; } }