Friday 21 January 2011

A Neat Solution to the Towers of Hanoi Problem



Just browsing through Wikipedia, and they show a solution to the Towers of Hanoi puzzle that I had never seen using a ruler as a solution key.

If you have been off planet for the last 130 years and don't know the Towers problem, you can play online here. You might try that first, and set the number of discs to 6 so that it matches the solution shown below.

And for those who know the game but just want to see how a ruler is used, here is the graphic.



For any move, just move the disc whose size compares to the marks on the ruler. For instance the first five marks on a ruler marked in 32nds would be 1/32, 1/16/ 3/32, 1/8, 5/32.... The denominators tell you which disk to move. The largest denominator (smallest scale) goes with the smallest disc, etc. If you then apply two fundamentals of any solution, always move the smallest disc From rod A, to B to C and back to A in a cycle, and never put a bigger disc on a smaller one, then you have a solution... That's easier than Gray codes isn't it.

Why have I never encountered this before? The connection was made in 1956 by Donald W. Crow, in relation to traversing the vertices of a cube in n-dimensions[ D. W. Crowe, The n-dimensional cube and the tower of Hanoi, Amer. Math. Monthly, 63 (1956), 29-30.]

Those interested in a little history of the Puzzle can find a few brief notes here.

POSTSCRIPT:::: For another really insightful solution (maybe the best of them all) See the comment by Jeffo....Thanks guy, why don't I see ideas like that?

1 comment:

Jeffo said...

If the rods are placed in a circular arrangement instead of linear, then a correct solution will involve always moving the smallest disk one rod clockwise every other move. The alternate moves are forced.