Problem
In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. How can you transfers N rings from one peg to another. The only operation you can perform is taking a single ring from the top of one peg and placing it on the top of another peg. You must never place a larger ring above a smaller ring.
Solution
It is hard to start, so let's start from smallest.
Move 1 disk from tower 1 to tower 3. An easy success.
Let's move 2 disks from tower 1 to tower 3. We have to move top disk to tower 2 then move bottom to tower 3, then move top to tower 3 as well. There's not much to think about in this case, there is only one way of doing this: move top to the tower other than the target tower, then move bottom to the target tower, then move top to the target tower.
Now let's move 3 disks from tower 1 to tower 3. After playing for a while, we suddenly realize the recursive pattern -- think of the top 2 disks as one piece, we already know how to move them anywhere -- since all the disks below the top 2 disks are larger, they are no different than flat ground and can be ignored when we move the top 2 disks around. With the confidence that we can handle the top 2 disks regardless of the other disks, we can now treat the 2 disks as one disk.
At this point, the cursive code start to reveal itself, but haven't crystal clear.
Let's start coding, the code will express our thought, make the details fall into places. We need 3 stack to model the towers, we need to calculate the empty slots other than source and destination, we can code 1 disk move case, we can code 2 disks move case, the only thing left is recursive part. Let's fill in that blank and work out a working code.
/*
- -
--- | --- | | - | - | | --- | ---
----- | ----- - | ----- --- - | ----- --- | --- ----- | - --- ----- | - ----- | -----
*/
import java.util.*;
class HanoiTowers {
private Stack<Integer>[] slots = new Stack[3];
private int n = 0;
public HanoiTowers(int n) {
this.n = n;
for(int i = 0; i < 3; i++) {
slots[i] = new Stack<Integer>();
}
for(int i = n; i >= 1; i--) {
slots[0].push(i);
}
}
//
private void move(int topN, int source, int target) { //5 0 2
int emptySlot = emptySlot(source, target);//1
if(topN == 1) {
slots[target].push(slots[source].pop());
} else if(topN == 2) {
slots[emptySlot].push(slots[source].pop());
slots[target].push(slots[source].pop());
slots[target].push(slots[emptySlot].pop());
} else {
move(topN - 1, source, emptySlot); //4 0 1 -> 3 0 2 | 2 0 1, 2 1 2
slots[target].push(slots[source].pop());
move(topN - 1, emptySlot, target); //4 1 2
}
}
public void move() {
move(n, 0, 2);
}
public static void main(String...args) {
HanoiTowers ht = new HanoiTowers(5);
//ht.printTowers();
ht.move();
ht.printTowers();
}
private void printTowers() {
for(int i = 0; i < 3; i++) {
System.out.println("=========");
Stack<Integer> stack = slots[i];
while(!stack.isEmpty()) {
System.out.print(stack.pop() + ", ");
}
}
}
private int emptySlot(int a, int b) {
if(a == 0 && b == 1 || a == 1 && b == 0) return 2;
else if(a == 0 && b == 2 || a == 2 && b == 0) return 1;
else return 0;
}
}
- -
--- | --- | | - | - | | --- | ---
----- | ----- - | ----- --- - | ----- --- | --- ----- | - --- ----- | - ----- | -----
*/
import java.util.*;
class HanoiTowers {
private Stack<Integer>[] slots = new Stack[3];
private int n = 0;
public HanoiTowers(int n) {
this.n = n;
for(int i = 0; i < 3; i++) {
slots[i] = new Stack<Integer>();
}
for(int i = n; i >= 1; i--) {
slots[0].push(i);
}
}
//
private void move(int topN, int source, int target) { //5 0 2
int emptySlot = emptySlot(source, target);//1
if(topN == 1) {
slots[target].push(slots[source].pop());
} else if(topN == 2) {
slots[emptySlot].push(slots[source].pop());
slots[target].push(slots[source].pop());
slots[target].push(slots[emptySlot].pop());
} else {
move(topN - 1, source, emptySlot); //4 0 1 -> 3 0 2 | 2 0 1, 2 1 2
slots[target].push(slots[source].pop());
move(topN - 1, emptySlot, target); //4 1 2
}
}
public void move() {
move(n, 0, 2);
}
public static void main(String...args) {
HanoiTowers ht = new HanoiTowers(5);
//ht.printTowers();
ht.move();
ht.printTowers();
}
private void printTowers() {
for(int i = 0; i < 3; i++) {
System.out.println("=========");
Stack<Integer> stack = slots[i];
while(!stack.isEmpty()) {
System.out.print(stack.pop() + ", ");
}
}
}
private int emptySlot(int a, int b) {
if(a == 0 && b == 1 || a == 1 && b == 0) return 2;
else if(a == 0 && b == 2 || a == 2 && b == 0) return 1;
else return 0;
}
}
The time complexity is O(2^n), we for 1 disk, 1 move; 2 disks 3 moves; 3 disks top 2 need to move twice, so double the cost; 4 disks, the top 3 need to move twice, double the cost again, so the trend is 2^n. The space complexity is the 3 stacks, which is O(N)
