CODEWITHSUNDEEP
pythonalgorithmrecursion
user7551834
user7551834

Reputation:

Tower of Hanoi recursive algorithm for four towers in Python

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:

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:

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.

Upvotes: 0

Views: 4788

Answers (2)

Chris
Chris

Reputation: 1

def move4Poles(begin, end, temp1, temp2, disks):

    if disks == 1:
        print(begin, "to", end)
        return

    if disks == 2:
        move4Poles(begin, temp1, '_', '_', 1)
        move4Poles(begin, end, '_', '_', 1)
        move4Poles(temp1, end, '_', '_', 1)
        return

    if disks >= 3:
        move4Poles(begin, temp2, temp1, end, disks - 2)
        move4Poles(begin, end, temp1, '_', 2)
        move4Poles(temp2, end, temp1, begin, disks - 2)

move4Poles('A', 'D', 'B', 'C', 4)


A to B
A to C
B to C
A to B
A to D
B to D
C to B
C to D
B to D

Upvotes: 0

Blckknght
Blckknght

Reputation: 104762

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

Upvotes: 0

Related Questions