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