It is possible to generate a simple fractal that provides a solution to Towers of Hanoi.
If the three towers are arranged in a circle, we can impose the restriction that pieces
should always be moved to the next available tower in a clockwise direction, respecting the
constraint that a piece may not be put on top of a smaller one.
The construction of the fractal is as follows:
The basic construct is the shape:
|
a---+---c
|
|
b---+---d
|
This is the first generation. To create the second generation, reproduce the construct
between points a and b, as well as points c and d:
|
|
+------+------+
| | |
---+--- | ---+---
| | |
| | |
---+--- | ---+---
| | |
+------+------+
|
|
For the basic 3-ring version of Hanoi, a 3rd-generation fractal is required.
|
+--------+--------+
| | |
+---+---+ | +---+---+
| | | | | | |
--+-- | --+-- | --+-- | --+--
A | | | | | | | B
--+-- | --+-- | --+-- | --+--
| | | | | | |
+---+---+ | +---+---+
| | |
+--------+--------+
|
The solution can be found by tracing a straight path from A to B. Whenever the path crosses
once of the constructs, a note is made of which generation it is from:
|
+--------+--------+
| | |
+---+---+ | +---+---+
| | | | | | |
--+-- | --+-- | --+-- | --+--
A~~3~~~2~~~3~~~~1~~~~3~~~2~~~3~~B
--+-- | --+-- | --+-- | --+--
| | | | | | |
+---+---+ | +---+---+
| | |
+--------+--------+
|
This sequence gives the order in which the rings should be moved to complete the puzzle,
bearing in mind the restriction of movement described above. Each generation number represents
a ring size; 1 being the largest ring, down to 3 being the smallest ring.
In general, N-rings require N generations to provide the solution.