Tower of Hanoi recursive algorithm for four towers in Python

Question

I'm having a decent amount of trouble implementing the optimal algorithm for the tower of hanoi game for four stools in python.

First, in class we solved the tower of hanoi algorithm for three towers, for which we were given the following algorithm:

Move all but the bottom disk from source to intermediate tower
Move the bottom disk form the source to the destination
Move all but the bottom disk from intermediate stool to destination tower

The actual code for this algorithm (with model being of class Model which has towers and disks, with a move method that moves disks from one tower to another) yields:

def move_disks(n, source, intermediate, destination):

    """Move n disks from source to destination
    @param int n:
    @param int source:
    @param int intermediate:

    @param int destination:
    @rtype: None
    """
    if n > 1:
        move_disks(n - 1, source, destination, intermediate)
        move_disks(1, source, intermediate, destination)
        move_disks(n - 1, intermediate, source, destination)
    else: 
        model.move(source, destination)

Now for four stools, I'm given the following:

Move n- i disks to intermediate stool using all four towers
Move i disks from the original tower to the destination tower, using only three available towers
Move n-i smallest disks from intermediate tower to destination tower

Manually playing around with disks and towers I got n-i = 2 if n>=3 and i = 1 if n =2. Since there are 4 possible sources and destinations, in my own function I have 5 arguments instead of 4:

def move_disks(n, source, intermediate, intermediate2, destination):

    """Move n disks from source to destination
    @param int n:
    @param int source:
    @param int intermediate:
    @param int intermediate2:
    @param int destination:
    @rtype: None
    """
    if n > 1:
        move_disks(n - i, source, intermediate 2 destination, intermediate)
        move_disks(1, source, intermediate, intermediate2, destination)
        move_disks(n - i, intermediate, intermediate2, source, destination)
    else:
        print("{} -> {}".format(source,destination)) # used to explicitly follow output in the console
        #model.move(source, destination) --> to be implemented when the function returns the right output

When I run it for n=3 I get:

1 -> 3
1 -> 2
3 -> 2
1 -> 4
2 -> 3
2 -> 4
3 -> 4

which gives the same number as moves as the solution for three towers. The optimal solution for four stools should yield:

1 -> 3
1 -> 2
1 -> 4
2 -> 4
3 -> 4

The problem is definitely coming from my understanding of the algorithm so I've tried tracing function calls on a dry erasable board for a few hours to no avail.

Any tips or tricks for what else I should be doing or looking for to solve this algorithm? I'm honestly lost and a little bit discouraged.

Whats the purpose of source, intermediate and following parameters? They're used nowhere in the code except as parameters for the recursive calls in both provided code-snippets. — Paul
The code works like this: in the base case it moves from source -> destination. if not in the base case, it has to move from source ->intermediate so intermediate becomes the new "destination" and so on. Same thing for intermediate and intermediate 2. — user7551834
I do understand that. My point is that none of these parameters is ever modified in any way — Paul
@Paul: The parameters other than n are just labels for the towers. The recursion is happening on n (with the others parameters merely getting rearranged). — Blckknght
Sorry I misunderstood your question. In the context of this particular code, we have a model of towers and disks. move_disks is simply a function meant to solve the game in the least amount of moves, so none of the parameters are altered in the code except for the number of disks we need to move -- but the location of the the disks on the towers change in the Model class (which are essentially dictionaries with values lists) are altered through the method move found in the base case. — user7551834

Blckknght Blckknght · Accepted Answer · 2017-02-12T01:17:44

I see two issues with your code.

The first is that you're using a variable i without defining it in the function. It probably has a global value in your environment, but perhaps not an appropriate one for the given n. You should probably have your function figure out what i should be and assign it as a local variable.

The second issue is that you're always recursing using the same four-tower function, while the algorithm you describe is supposed to use only three towers in the middle step. This probably means you should keep around your original function (in the first code block), and use a different name for your four-tower function.

If we name your first function move_disks3 and the second move_disks4, we can make it work:

def move_disks3(n, source, intermediate, destination):
    """Move n disks from source to destination
    @param int n:
    @param int source:
    @param int intermediate:
    @param int destination:
    @rtype: None
    """
    if n > 1:
        move_disks3(n - 1, source, destination, intermediate)
        move_disks3(1, source, intermediate, destination)
        move_disks3(n - 1, intermediate, source, destination)
    else:
        print("{} -> {}".format(source,destination))

def move_disks4(n, source, intermediate, intermediate2, destination):
    """Move n disks from source to destination
    @param int n:
    @param int source:
    @param int intermediate:
    @param int intermediate2:
    @param int destination:
    @rtype: None
    """
    if n > 1:
        if n > 2: # I'm not sure this picks the optimal i in all cases, but it does for n=3
            i = 2
        else:
            i = 1
        move_disks4(n - i, source, intermediate2, destination, intermediate)
        move_disks3(i, source, intermediate2, destination)
        move_disks4(n - i, intermediate, intermediate2, source, destination)
    else:
        print("{} -> {}".format(source,destination))

I'm not certain I understood your statements about the optimal i value, so you might need to make a few changes if I got something wrong there. But this code does work, and does give the desired results for n = 3 (and plausible results for a few higher n values I tested):

>>> move_disks4(3, 1, 2, 3, 4)
1 -> 2
1 -> 3
1 -> 4
3 -> 4
2 -> 4

Tower of Hanoi recursive algorithm for four towers in Python

1 Answers