Generating a tuple of tuples for the Tower of Hanoi

Question

My class has recently introduced us to tuples, and quite quickly thrown us a problem on creating a problem of the renowned "Tower of Hanoi". Essentially, we are supposed to create a tuple of (source, destination) for each movement of a plate in the Tower of Hanoi. The professor has given us this code, without much explanation:

def hanoi(n, src, des, aux):
    if n == 1:
        return ((src, des),)
    else:
        return hanoi(n-1, src, aux, des) + (((src, des),) + hanoi(n-1, aux, des, src))

I'm almost at a complete loss. (The poles are labelled Pole 1, 2 and 3 respectively. A sample input of hanoi(1,1,3,2) would yield ((1, 3),), indicating movement from Pole 1 to Pole 3 for that step.)

Ok, I know what the base case is. If I only have 1 plate, I move it directly from the source pole to the destination pole. Beyond that, I know that hanoi(n-1, src, aux, des) is the recursive step, intended to simulate when n-1 discs are left in the original stack. But I'm bummed by why hanoi(n-1, aux, des, src) swaps the positions of aux, des and src.

I also cannot quite understand why the else: statement is arranged as hanoi(n-1, src, aux, des) + (((src, des),) + hanoi(n-1, aux, des, src))?

Any tips and advice would be appreciated! I have tried for hours to see the pattern, and I know the rules of the game via drawing it out, but I am unable to comprehend how it is converted to computer (Python) logic.

Thank you!

Answer 1

A full explanation with visuals for

I'm bummed by why hanoi(n-1, aux, des, src) swaps the positions of aux, des and src.

Is in the following links:

https://www.geeksforgeeks.org/python-program-for-tower-of-hanoi/

https://runestone.academy/runestone/books/published/pythonds/Recursion/TowerofHanoi.html

Regarding the last question:

I also cannot quite understand why the else: statement is arranged as hanoi(n-1, src, aux, des) + (((src, des),) + hanoi(n-1, aux, des, src))?

This is because you want a set of steps, so you add the movement to the set.

So lets say that each call return a tuple of tuple [((src, des),)] right, so for example take the dummy function:

def f():
    return((1,2),) + ((2,3),) + ((1,3),)

It returns the "sum" of each tuple of tuples, that will give you just a concatenated tuple of tuples.

Answer 2

at level n, you have to move n-1 plates from src to aux (an intermediate storage pole) : hanoi(n-1, src, aux, des)

Then you are left with the largest plate on src, you can move it from src to dest : (((src, des),)

And finally you have to move all the n-1 plates from aux to dest (using src as the new intermediate pole) : hanoi(n-1, aux, des, src))

hence the need to swap the positions.

The function computes the list of all moves as shown below for hanoi(2,'pole1-src','pole2-dest','pole3-aux')

(('pole1-src', 'pole3-aux'),
 ('pole1-src', 'pole2-dest'),
 ('pole3-aux', 'pole2-dest'))```