Tower of Hanoi Problem
There are three needles. The first needle has 64 disks with smaller disk sits on top of larger ones.
The problem is: how to use recursive method to move all 64 disks from first needle to third needle.
Rules
Only one disk can be moved at a time
Removed disk must be placed on one of the needles
A larger disk cannot be placed on top of a smaller disk
Analysis
1-disc (move from A to C).. trivial
2-disc ...straight-forward
3-disc .... the basic idea is
move top-2 from A to B (using 2-disc method above)
move the bottom purple one from A to C
move top-2 from B to C (using 2-disc method)
4-disc ... the basic idea is
move top-3 from A to B (using 3-disc method above)
move the bottom red one from A to C
move top-3 from B to C (again, using 3-disc method)
Hope you get the idea.
The algorithm for moving N disc from A (src) to C (dst)
move N-1 disc from A (src) to B (tmp)
move Nth from A (src) to C (dst)
move N-1 from B (tmp) to C (dst)
void TowerOfHanoi ( int NumberOfDisc, char Source='A', char Destination='C', char Temp='B') {
if (NumberOfDisc == 0) return;
TowerOfHanoi( NumberOfDisc-1, Source, Temp, Destination);
cout << "move " << NumberOfDisc << "th from " << Source<< " to " << Destination << endl;
TowerOfHanoi( NumberOfDisc-1, Temp, Destination, Source);
}
// modified Mar 2016
If all the source, destination, temp get you confused, here is the ABC version...B is our temp, so I'll use Temp instead
f ( n, A, C, Temp) { // move n from A to C
if (n==0) return;
f (n-1, A, Temp, C); // move n-1 from A to Temp
move the only remaining disc from A to C;
f (n-1, Temp, C, A); // move n-1 from Temp to C
}
1/7/2023 Python code for my grandkids:
def StackIt( Num, From, To, Temp) :
if (Num == 0):
return
StackIt( Num-1, From, Temp, To)
print("move ", Num, From, To )
StackIt( Num-1, Temp, To, From)
StackIt(4, "A", "C", "B")
-------------------------------------------------------
adding count
count=0
def StackIt( Num, From, To, Temp) :
if (Num == 0):
return
StackIt( Num-1, From, Temp, To)
global count
count = count+1
print(count,"move disc", Num, From, To )
StackIt( Num-1, Temp, To, From)
StackIt(5, "A", "C", "B")
-----------
Recommendation: run the above program at online w3c python compiler by cut-n-paste. Furthermore, try 10 discs and you can figure out the minimum number of moves required for a given number of discs. (note: it is 2**n - 1 )
Discussion
How to debug a recursive function?
When I encounter issues with looping functions (well, recursion is one of those), I usually start with breakpoint on each loop. For recursion, I look for the calling sequence and their respective parameters. The parameters can be viewed from IDE's local variables. The debug example used in other topics also applies to this case.
How long does it take for your computer to run tower of 10, 20? Have you tried tower of 64?