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?

Gregarious

Doubt it. How do you even solve the Towers of Hanoi with X disks and Y towers? As far as I know, there is no proven algorithm that solves this with a minimum number of moves. Unless maybe you don't care about the number of moves being minimum? – Zomba

@IVlad: if you don't care about the number of moves being minimum, ignore all but 3 of the poles. Job done :-) – Curriery

@Steve Jessop - true :). @Gregarious - your best start is probably the Frame-Stewart algorithm described here: en.wikipedia.org/wiki/Tower_of_Hanoi - It's not known if the algorithm is truly optimal, but it most likely is. I don't know how exactly it can be adapted into a non-recursive solution that prints each move, but someone else will probably figure it out and hopefully post their findings :). – Zomba

It is easy enough to solve for X discs, you just have to know if it is even or odd. Y towers is the tricky bit. – Microwatt

The "optimal" solution is not known for > 3 disks [though the frame stewart conjecture gives some hint as to how to solve it] and the bit solution exploits assumptions in the 3-case. – Doorjamb

@Foo The optimal solution is not known for > 3 PEGS, not disks, I believe. – Involuted

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.

Thalassic