Scaling an iterative, bitwise algorithm to solve the Towers of Hanoi using X discs and Y towers

Question

I like the algorithm mentioned in this question: "How does this work? Weird Towers of Hanoi Solution" How does this work? Weird Towers of Hanoi Solution

Is there any way to scale that non-recursive solution of Towers of Hanoi to use X disks and Y towers, with towers represented as stacks?

Answer 1

An iterative solution for the tower of Hanoi with Y=3 Towers and X discs and can be found on Wikipedia:

For an even number of disks:

• make the legal move between pegs A and B
• make the legal move between pegs A and C
• make the legal move between pegs B and C repeat until complete

For an odd number of disks:

• make the legal move between pegs A and C
• make the legal move between pegs A and B
• make the legal move between pegs B and C repeat until complete

In each case, a total of 2^X-1 moves are made. The number of moves with this algorithm is only minimal for Y=3.

This solution ignores the other towers, so it works with any Y >= 3 and any X.

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.

Quoted from Wikipedia.