First, the function is wrong, there’s a print
the plus and the second recursive call changed the order of the towers:
def hanoi(disc, ori, dest, aux):
if disc == 1:
print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
return
hanoi(disc - 1, ori, aux, dest)
print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
hanoi(disc - 1, aux, dest, ori)
Now to the problem. The problem of the Tower of Hanoi consists of moving a number of disks from one tower to another (with a third auxiliary tower). The discs have different sizes, and one disc can never be placed on top of another smaller than it. Moreover, only one disc can be moved at a time.
The if
deals with the most basic case: when there is only 1 disk. In this case the solution is easy: move the disk from the initial tower to the final, ie from the origin (ori
) to fate (dest
).
But what if we have more than one disk? In this case, assuming that the towers are A (origin), B (destination), and C (auxiliary), the idea of the algorithm is (for N disks):
- solve the problem for N - 1 disks, only moving from A to C (ie using C as target and B as auxiliary)
- move 1 disk from A to B (from source to destination)
- solve the problem for N - 1 disks, only moving from C to B (i.e., C is the source, B is the destination and A is the helper)
That’s what recursive calls are doing. hanoi(disc - 1, ori, aux, dest)
corresponds to step 1 above. The print
soon after is step 2, and hanoi(disc - 1, aux, dest, ori)
is step 3.
The big trick is that each of these recursive calls can generate other recursive calls, until they arrive in the case where it only has a 1 disk, which is when they return and return printing the respective steps.
For example, if I have 5 disks and want to move them from A to B (where C is the auxiliary tower). The idea is:
- move 4 disks from source (A) to auxiliary (C)
- move disk 5 to target (B)
- move the 4 disks that are in auxiliary (C) to destination (B)
But how to do the first step (move 4 disks from A to C)? Simple, I call the function again for 4 disks (N - 1), only considering that C is the destination and B is the auxiliary. Then she will do all three steps above, but considering this new context (4 disks, destination is C and B is auxiliary). The same thing for the third step (only now are 4 disks whose origin is C, destination is B and the auxiliary is A).
For example, if I have 3 disks, the execution looks like this:
- first I solve the problem for 2 disks, moving from A to C, using B as auxiliary
- resolvo to 1 disk, moving from A to B, using C as auxiliary
- movement 2 from A to C
- solve to 1 disk, moving from B to C, using A as auxiliary
- I move disk 3 from A to B
- resolvo for 2 disks, moving from C to B, using A as auxiliary
- solve to 1 disk, moving from C to A, using B as auxiliary
- movement 2 from C to B
- resolvo to 1 disk, moving from A to B, using C as auxiliary
Calling in the code would be:
hanoi(3, 'A', 'B', 'C')
Exit:
Move disc 1 from tower A to the tower B
Move disc 2 from tower A to the tower C
Move disc 1 from tower B to the tower C
Move disc 3 from tower A to the tower B
Move disc 1 from tower C to the tower A
Move disc 2 from tower C to the tower B
Move disc 1 from tower A to the tower B
See the code running on Ideone.com
What can be confusing is that with each recursive call, the towers used as source, destination, and auxiliary change. But the logic is the same for calls (move N - 1 disks from source to auxiliary, move 1 disk from source to destination, move N - 1 disks from auxiliary to destination).
Remembering also that for N disks, the solution requires 2N - 1 steps, and depending on N, that whole amount of recursive calls can cause a pile overflow. The exact amount depends on the value of the recursion limit (that can be changed), but the value default it’s not that big (example).
https://www.python-course.eu/towers_of_hanoi.php
– Leonardo Bonetti
From what I understand you want to know how it works right? If yes the function in question it is comparing the possibility of movement be it in the tower or to the tower. If that’s not it please rephrase the question.
– Fernando Cordeiro
"I’m not getting it from
if
down". Easier you say you didn’t understand anything... hahaha– fernandosavio