Towers of Hanoi with 4 towers

Question

So far i know how to do the tower of Hanoi with 3 towers, but i have no idea on how to implement the Frame Steward Algorithm for 4 towers.

this is how my current three tower function looks like.

def move_three_towers(n, from_tower, to_tower, spare_tower):
    if (n > 0):

        move_three_towers(n-1, from_tower, spare_tower, to_tower)
        print(from_tower, ' --> ', to_tower)
        move_three_towers(n-1, spare_tower, to_tower, from_tower)

i need help implementing n - k disks to another tower using 4 towers. for some 1 ≤ k < n

here is my attempt at the algorithm but it doesn't work, please help.

def move_four_towers(n, k = 0, from_tower, to_tower, spare_tower1, spare_tower2):
     if n == 1:
        print(from_tower, ' --> ', to_tower)
     if n > 1:
        move_four_towers(n - k, from_tower, spare_tower2, spare_tower1, to_tower)
        print(from_tower, ' --> ', to_tower)
        move_three_towers(k, from_tower, to_tower, spare_tower1)
        move_four_towers(n - k, spare_tower2, to_tower, spare_tower1, from_tower)

@kindall: the Frame Steward algorithm give a solution which is conjectured to be optimal in the number of moves. Yours is certainly not. — hivert
But i would like to optimize my solution to use the Frame Stewart Algorithm, ignoring a tower defeats the purpose of having 4 towers. — Spock
Well, think about what you'd use another tower for if solving the game by hand. Try it with 4 discs, first using 3 towers and then using 4. How could you use the fourth tower to solve it faster? — kindall
@kindall +1 I would have loved to turn that in (ignoring the 4th) when I was in college and to see the look on my professor's face. — evanb
You have misunderstood Frame Steward. For a given n, you have to pick the optimal k -- it's not a parameter to the function. For 4 pegs, that k is n - round(sqrt(2n+1)) + 1. — Paul Hankin

OJFord OJFord · Accepted Answer · 2014-02-21T23:27:53

Wikipedia gives a nice description of the algorithm for r pegs and n disks:

The algorithm can be described recursively:

For some k, 1 <= k < n, transfer the top k disks to a single peg other than the start or destination pegs, taking T(k,r) moves.

Without disturbing the peg that now contains the top k disks, transfer the remaining n-k disks to the destination peg, using only the remaining r-1 pegs, taking T(n-k,r-1) moves.

Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.

Towers of Hanoi with 4 towers

1 Answers