Background info: the Tower of Hanoi is a puzzle involving moving a stack of disks from one peg to another, one at a time. The Sierpinski triangle is a fractal generated by cutting an equilateral triangle into four and continuing with the three corners.

Turns out there’s more to the Tower of Hanoi than I knew. Although solving it recursively is quite easy, Wikipedia also lists an iterative system: make alternating moves between the smallest disk and another. Always move the smallest disk in the same direction, and for the other moves there’ll only be one option. All you have to remember is whether or not the smallest was moved in the previous turn.

Which is all very interesting, but scroll down to the “Graphical representation” section and something else interesting arises: a graph of the possible moves with each node representing the position of each disk.

For instance, the left node on the second row (“baa” ) means the smallest disk is on b, and the second and third are on a. That section lists a bunch of trends, but of note is that any state (except where all pieces are on the same peg) has three possible moves, which is two if you don’t undo. Also interesting is the possibility to encounter every possible state exactly once on the way to the solution.

But what gave the title of this post is the similarity to the Sierpinski triangle. With more disks, it looks more and more like it. I believe it would be fairly simple to generate the graph for any number of disks: note that, for instance, every node in the top third ends with “a”. Every node in the top third of that has “a” second, and so on.

Anyway, check out the Wikipedia article, there’s some interesting stuff there.