0
$\begingroup$

I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.

However one thing still bugs me - I can't yet work out how this simple seeming algorithm can "know" which move to make first - whether to the destination peg or the spare peg.

I can see it depends on whether there is an odd or even number of discs, and I understand how the algorithm works, thanks to this great article: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

It's just that first move that remains a mystery to me. Any clarification musch appreciated.

def hanoi(n, from_peg, to_peg, spare_peg):
    if n == 1:
        print("Moving disc from " + from_peg + " to " + to_peg)
        return
    hanoi(n-1, from_peg, spare_peg, to_peg)
    print("Moving disc from " + from_peg + " to " + to_peg)
    hanoi(n-1, spare_peg, to_peg, from_peg), 

print (hanoi(4, 'A', 'C', 'B'))
$\endgroup$
  • $\begingroup$ The first move is the first to be made, not the first to be computed. $\endgroup$ – André Souza Lemos Jan 22 '18 at 21:03
1
$\begingroup$

The first move is produced by the first recursive call in the code, which is repeatedly invoked many times, until the base case is reached -- printing the first move.

We note that hanoi(n, from_peg, to_peg, spare_peg) makes as its first recursive call hanoi(n-1, from_peg, spare_peg, to_peg), so this swaps the last two arguments, and decreases n.

Hence, the last two arguments will be swapped n-1 times, until we reach n=1 triggering the base case.

Concluding, performing n-1 swaps, leaves those arguments where they are if n is odd, or swaps them (once), if n is even.

$\endgroup$
1
$\begingroup$

If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is hanoi(n, 'A', 'B', 'C') :

hanoi(n, 'A', 'B', 'C')
hanoi(n-1, 'A', 'C', 'B')
hanoi(n-2, 'A', 'B', 'C')
...
hanoi(1, 'A', $ , €)
Moving disc from A to $

To see if $ is equal to B or C, you just have to remark that the value of to_peg and spare_peg alternate each time so the disk to move only depends on the parity of n. In our example :

If n is odd then \$ = B and otherwise, \$ = C

$\endgroup$
0
$\begingroup$

The broad idea behind solving Tower of Hanoi problem by recursion is this:enter image description here

The whole stack of n disks needs to be transferred to the to pole from from pole. Imagine there are n disks (instead of 3 shown) on the from pole. The idea behind recursive solution is to consider the top $n-1$ disks as a single disk, transfer this combined disk to using pole, place the $nth$ disk on the to pole, and then place the aggregated disk on the top of the $nth$ disk on the to pole. Now, how do I move that aggregated disk to the using pole ? Apply the above procedure to the top $n-1$ disks forgetting about the bottom $nth$ disk, and that's what recursion is.

So, in order to find out the first move, we keep reducing the size of our aggregated disk until we reach the top 2 disks, or just simply call your code with n=2.

def hanoi(2, from_peg, to_peg, spare_peg):

Now this line below

hanoi(1, from_peg, spare_peg, to_peg)

moves $1st$ disk from from pole to aux peg. Following which

print("Moving disc from " + from_peg + " to " + to_peg)

moves $2nd$ disk from from pole to to pole. And finally,

hanoi(1, spare_peg, to_peg, from_peg),

places $1st$ disk from aux back to to pole on top of $2nd$ disk.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.