/*
TowerOfHanoi.java 遞迴版 及 模擬呼叫堆疊版 求解河內塔
> java TowerOfHanoi
Hanoi Tower by Implicit Call Stack 遞迴版
A:[3, 2, 1], B:[], C:[] 1: Move disk 1 from A to C
A:[3, 2], B:[], C:[1] 2: Move disk 2 from A to B
A:[3], B:[2], C:[1] 3: Move disk 1 from C to B
A:[3], B:[2, 1], C:[] 4: Move disk 3 from A to C
A:[], B:[2, 1], C:[3] 5: Move disk 1 from B to A
A:[1], B:[2], C:[3] 6: Move disk 2 from B to C
A:[1], B:[], C:[3, 2] 7: Move disk 1 from A to C
A:[], B:[], C:[3, 2, 1]
Hanoi Tower by Explicit Stack 模擬呼叫堆疊版
A:[3, 2, 1], B:[], C:[] 1: Move disk 1 from A to C
A:[3, 2], B:[], C:[1] 2: Move disk 2 from A to B
A:[3], B:[2], C:[1] 3: Move disk 1 from C to B
A:[3], B:[2, 1], C:[] 4: Move disk 3 from A to C
A:[], B:[2, 1], C:[3] 5: Move disk 1 from B to A
A:[1], B:[2], C:[3] 6: Move disk 2 from B to C
A:[1], B:[], C:[3, 2] 7: Move disk 1 from A to C
A:[], B:[], C:[3, 2, 1]
*/
import java.util.Stack;
public class TowerOfHanoi
{
static Stack stackA = new Stack<>(); // 柱A
static Stack stackB = new Stack<>(); // 柱B
static Stack stackC = new Stack<>(); // 柱C
static int nDisks = 5; // Number of disks 盤數
static int count = 0; // 步數
static boolean printGoal = false; // 列印目標否
static boolean printOperation = true; // 列印步驟否
static boolean printStack = false; // 列印模擬呼叫堆疊否
// 印n格空白
public static void printSpaces(int n)
{
for(int i=0; i <= n -1; i++) System.out.print(" ");
}
// 印柱A,柱B,柱C堆疊,前面n層內縮
public static void printStacks(int n)
{
StringBuilder sb = new StringBuilder();
sb.append("A:" + stackA);
sb.append(", B:" + stackB);
sb.append(", C:" + stackC);
System.out.println();
printSpaces(n*8); // 每層內縮8格
System.out.print(sb.toString());
}
// 搬移柱from頂一個盤子到柱to
public static void transfer(char from, char to)
{
if(from=='A' && to=='B') stackB.push(stackA.pop());
if(from=='A' && to=='C') stackC.push(stackA.pop());
if(from=='B' && to=='A') stackA.push(stackB.pop());
if(from=='B' && to=='C') stackC.push(stackB.pop());
if(from=='C' && to=='A') stackA.push(stackC.pop());
if(from=='C' && to=='B') stackB.push(stackC.pop());
}
// 遞迴版解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
public static void solveHanoi(int n, char source, char auxiliary, char target)
{
if(printGoal)
{
System.out.println();
printSpaces((nDisks - n)*8);
System.out.print(String.format("hanoi(n:%d,s:%c -> t:%c)",n,source,target));
}
if (n == 1)
{
if(printOperation)
System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
transfer(source, target);
}
else
{
solveHanoi(n - 1, source, target, auxiliary);
printStacks(nDisks - n);
if(printOperation)
System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
transfer(source, target);
printStacks(nDisks - n);
solveHanoi(n - 1, auxiliary, source, target);
}
}
// 模擬呼叫記錄
static class HanoiCallRecord
{
int num;
char source;
char auxiliary;
char target;
int stage; // 0 for moving n-1 disks from source to auxiliary rods;
// 1 for moving the disk n from source to target rods
// and moving n-1 disks from auxiliary to target rods
// 2 for backtracking to the previous call record
// 建構子
public HanoiCallRecord(int num, char source, char auxiliary, char target)
{
this.num = num;
this.source = source;
this.auxiliary = auxiliary;
this.target = target;
this.stage = 0; // 預設從階段0開始
}
// 列印呼叫記錄
public String toString()
{
return String.format("(n:%d,s:%c,a:%c,t:%c,s:%d)",
num, source, auxiliary, target, stage);
}
}
// 模擬呼叫堆疊，解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
public static void hanoiUsingStacks(int num, char src, char aux, char tgt)
{
Stack stack = new Stack<>();
HanoiCallRecord initial = new HanoiCallRecord(num, src, aux, tgt);
stack.push(initial); // 壓入第1層呼叫記錄
while (stack.isEmpty()==false)
{
if(printStack) System.out.print("\n" + stack);
HanoiCallRecord current = stack.peek(); // 檢視本層呼叫記錄
int n = current.num;
char source = current.source;
char auxiliary = current.auxiliary;
char target = current.target;
int stage = current.stage;
if (n == 1) // 執行特別任務，然後退回上一層任務
{
if(printOperation)
System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
transfer(source, target);
stack.pop(); // 彈出本層呼叫記錄,
}
else if(stage == 0) // 階段0, 執行本層第0階段任務
{
// solveHanoi(n - 1, source, target, auxiliary);
HanoiCallRecord next = new HanoiCallRecord(n - 1, source, target, auxiliary);
stack.push(next); // 壓入下層呼叫記錄
current.stage++; // 更新本層呼叫記錄的階段欄位
}
else if(stage == 1) // 階段1, 執行本層第1階段任務
{
printStacks(nDisks - n);
if(printOperation)
System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
transfer(source, target);
printStacks(nDisks - n);
// solveHanoi(n - 1, auxiliary, source, target);
HanoiCallRecord next = new HanoiCallRecord(n - 1, auxiliary, source, target);
stack.push(next); // 壓入下層呼叫記錄
current.stage++; // 更新本層呼叫記錄的階段欄位
}
else if(current.stage == 2) // 階段2,本層任務完成,退回上一層任務
{
stack.pop(); // 彈出本層呼叫記錄,
}
}
}
// 測試主程式
public static void main(String[] args)
{
nDisks = 3; // Number of disks
count = 0;
for(int i=nDisks; i >= 1; i--) stackA.push(i);
System.out.print("Hanoi Tower by Implicit Call Stack 遞迴版");
printStacks(0);
solveHanoi(nDisks, 'A', 'B', 'C');
printStacks(0);
// ===================================
count = 0;
stackA.clear();
stackB.clear();
stackC.clear();
for(int i=nDisks; i >= 1; i--) stackA.push(i);
System.out.print("\n\nHanoi Tower by Explicit Stack 模擬呼叫堆疊版");
printStacks(0);
hanoiUsingStacks(nDisks, 'A', 'B', 'C');
printStacks(0);
}
}