Solving the towers of Hanoi using Lindenmayer systems

Introduction

What I'm about to describe is a funny side result of a technique to transform recursion to iteration, derived mathematically in my PhD thesis "Platform-independent source code transformations for task concurrency management", written 10 years ago. Time flies!

Funny how after so many years I consider exactly this little side-result to be the most intriguing result of my thesis. The mathematical proof of how it works is best left to the thesis itself, but I will try to demonstrate you how you could calculate the j-th move in an N-disk Hanoi problem using a Lindenmayer system.

Solving what with what?!

towers of Hanoi

The towers of Hanoi are a puzzle in which one is asked to move disks from the rod on the left to the rod on the right according to the following rules:

1. move only one disk at a time
2. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
3. No disk may be placed on top of a smaller disk.

If you start with only three disks, it takes at least 7 moves to solve the problem. The wikipedia page linked above shows many ways to solve the Hanoi problem. The method I'm about to demonstrate is related to their "Binary solution" but it's different from what is described there.

Lindenmayer systems

A Lindenmayer system (or L-system as it's often called) consists of a series of symbols, called an alphabet (think: A,B,C,...) and a set of rules that transform sequences of symbols into new sequences of symbols. Here's an example:

• alphabet A, B, C.
• rule 1: ACB -> AB
• rule 2: AB -> 

Rule 1 can be read as: whenever you encounter the sequence ACB, replace it with AB.
Rule 2 can be read as: given sequence AB, remove it (or: replace it with an empty string, if you like fancy words :) )

We could apply the rules to the following start sequence: ABAABCBA

• first, use rule 2: ABAABCBA becomes  AABCBA
• then, use rule 2: AABCBA becomes ACBA
• then, use rule 1: ACBA becomes ABA
• then, use rule 2: ABA becomes A

I hope by now you get the idea... L-systems have various applications, but they are best known for generating computer graphics representations of plants and trees, and various fractals (the wikipedia entry linked above has a list of interesting demonstrations). To go from a sequence of letters to a drawing, each symbol is interpreted as a drawing operation (e.g. a symbol A could mean: turn 45deg, symbol B could mean: step 1 unit forward, etc.)

How are both things related?

The following drawings show the solution of the Hanoi problem with three disks:

• Move 1 goes from rod A to rod C
• Move 2 goes from rod A to rod B
• Move 3 goes from rod C to rod B
• Move 4 goes from rod A to rod C
• Move 5 goes from rod B to rod A
• Move 6 goes from rod B to rod C
• Move 7 goes from rod A to rod C

The question is: if we use 3 disks, and we want to calculate from which rod to which rod we have to move the upper disk, how can we do that? Or more general: if we use N disks, and we want to know the j-th move, can we calculate this, without actually doing all the previous moves first?

And the answer, of course, is yes we can!

Recipe

For the mathematical details of why the following recipe works, you will need to read chapter 6 in the thesis, but if you just want to apply a recipe and marvel at the wonders of science (ahem!), keep reading...

First the recipe itself, then I will illustrate using an application. If you want to calculate the j-th move (where j can go from 1 to 2^N-1) in an N-disk problem, do the following:

1. take j and write in binary representation
2. reverse the binary representation
3. pad with 0's on the right side until you've used N bits
4. remove everything coming before and including the first 1-bit
5. Now we have a sequence of 0 and 1 which we consider the alphabet of a Lindenmayer system and we apply the following rules (in any order you like) until no more rules can be applied:
   00 -> <empty>
   11 -> <empty>
   1010 -> 01
   0101 -> 10
6. eventually you end up with one of the following sequences. The  sequence we end up with directly tells us the j-th move in the N-disk towers of Hanoi problem:

Sequence	Move from to
0	A->B
1	B->C
01	B->A
10	C->B
101	C->A
010	C->A
<empty>	A->C

Example

Recall our N=3-disk Hanoi problem. Let's see if we can calculate the j=2nd move using the method shown above.

1. take number 2 and write it in binary representation:  10
2. reverse the binary representation: 01
3. pad with 0's to the right until we have used N=3 bits: 010
4. chop off everything before and including the first 1-bit:  0
5. apply the rules until you hit one of the cases in the table: no rules can be applied here, since we are already in the case 0. According to the table, ending up with 0 indicates a move from A->B
6. Double-checking in the solutions that were displayed before, we indeed see that the 2nd move goes from A->B.

Was this an accident, or does it really work? Lets quickly try it for all 7 moves. Each column represents a step in the recipe.

Move no.	Binary	Reverse	Pad	Chop	L-system simplifcation	Move according to the table
1	1	1	100	00	<empty>	A->C
2	10	01	010	0	0	A->B
3	11	11	110	10	10	C->B
4	100	001	001	<empty>	<empty>	A->C
5	101	101	101	01	01	B->A
6	110	011	011	1	1	B->C
7	111	111	111	11	<empty>	A->C

If we take the successive moves listed in the right-most column of this table, and compare it to the solution shown before it becomes clear that the system indeed results in the correct solution (at least for the case N=3). In this case, our L-system didn't really have a lot of work to do: only twice it reduced a bit sequence. This is to be expected for low values of N (N = the number of disks used, here 3).

Example for N=5

Now let's apply the recipe to the 5-disk problem. The 5-disk problem takes (2^5-1) = 31 moves to solve.

Move no.	Binary	Reverse	Pad	Chop	L-system simplifcation	Move according to the table
1	1	1	10000	0000	<empty>	A->C
2	10	01	01000	000	0	A->B
3	11	11	11000	1000	10	C->B
4	100	001	00100	00	<empty>	A->C
5	101	101	10100	0100	01	B->A
6	110	011	01100	100	1	B->C
7	111	111	11100	1100	<empty>	A->C
8	1000	0001	00010	0	0	A->B
9	1001	1001	10010	0010	10	C->B
10	1010	0101	01010	010	010	C->A
11	1011	1101	11010	1010	01	B->A
12	1100	0011	00110	10	10	C->B
13	1101	1011	10110	0110	<empty>	A->C
14	1110	0111	01110	110	0	A->B
15	1111	1111	11110	1110	10	C->B
16	10000	00001	00001		<empty>	A->C
17	10001	10001	10001	0001	01	B->A
18	10010	01001	01001	001	1	B->C
19	10011	11001	11001	1001	<empty>	A->C
20	10100	00101	00101	01	01	B->A
21	10101	10101	10101	0101	10	C->B
22	10110	01101	01101	101	101	C->A
23	10111	11101	11101	1101	01	B->A
24	11000	00011	00011	1	1	B->C
25	11001	10011	10011	0011	<empty>	A->C
26	11010	01011	01011	011	0	A->B
27	11011	11011	11011	1011	10	C->B
28	11100	00111	00111	11	<empty>	A->C
29	11101	10111	10111	0111	01	B->A
30	11110	01111	01111	111	1	B->C
31	11111	11111	11111	1111	<empty>	A->C

So now you can calculate the optimal move in a N-disk Hanoi puzzle with 3 poles at any moment in time without having to know any of the previous or future moves.

Order of rule application in the L-system simplifications

From the N=5 case, it becomes clear that the L-system has more work to do, and the work to be done by our L-system increases as N increases.

One thing I'd like to show you in more detail is how the order of application of the rules doesn't influence the end result. This is not as obvious as it might seem.

First consider a different L-system with the following rules:

• alphabet: 0,1
• rule 1: 001 -> 0
• rule 2: 00 -> <empty>

Now start from the sequence: 001

• If you first apply rule 1, you get 001 ->  0
• On the other hand, if you first apply rule 2, you get 001-> 1

We ended up with 2 different results that can no longer be further simplified. Clearly, in general the order of rule application matters!

But interestingly enough, this is not the case in our towers of Hanoi move simplification L-system. While the proof is in the thesis, I will just demonstrate on a few values.

Consider the 45th move in an 9-disk problem.

• 45 binary:  101101
• reversed: 101101
• padded to 9 bits: 101101000
• chopped after first 1 bit: 01101000

The L-system is asked to simplify 01101000. It's clear that the rules can be applied in different order, but the end result is always the same move. This is not a coincidence, but a direct result of how the method works. Here are some different orders that yield the same result. No matter how hard you try, you won't find a counter-example (unless you made a calculation error ;) ).

• 01101000 -> 001000 -> 1000 -> 10 -> move C->B
• 01101000 -> 010100 -> 1000 -> 10 -> move C->B
• 01101000 -> 011010 -> 0101 -> 10 -> move C->B
• 01101000 -> 011010 -> 0010 ->  10 -> move C->B
• ...

There you have it. L-systems solving the towers of Hanoi problem. Who would have thought ;)