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

• 1. move top-2 from A to B (using 2-disc method above)

  2. move the bottom purple one from A to C

  3. move top-2 from B to C (using 2-disc method)

4-disc ... the basic idea is

• 1. move top-3 from A to B (using 3-disc method above)

  2. move the bottom red one from A to C

  3. 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)

• 1. move N-1 disc from A (src) to B (tmp)

  2. move N^th from A (src) to C (dst)

  3. 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

• 1. How to debug a recursive function?

  2. 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.

  3. How long does it take for your computer to run tower of 10, 20? Have you tried tower of 64?