Saturday, July 13, 2013

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:
  7. SequenceMove from to
    0A->B
    1B->C
    01B->A
    10C->B
    101C->A
    010C->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.BinaryReversePadChop L-system simplifcationMove according to the table
1 1 1 10000<empty>A->C
2 10 01 01000A->B
3 11 11 1101010C->B
4 100 001 001<empty><empty>A->C
5 101 101 1010101B->A
6 110 011 01111B->C
7 111 111 11111<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.BinaryReversePadChop L-system simplifcationMove according to the table
111100000000<empty>A->C
21001010000000A->B
3111111000100010C->B
41000010010000<empty>A->C
510110110100010001B->A
6110011011001001B->C
7111111111001100<empty>A->C
8100000010001000A->B
91001100110010001010C->B
101010010101010010010C->A
111011110111010101001B->A
1211000011001101010C->B
1311011011101100110<empty>A->C
1411100111011101100A->B
151111111111110111010C->B
16100000000100001<empty>A->C
17100011000110001000101B->A
181001001001010010011B->C
191001111001110011001<empty>A->C
201010000101001010101B->A
21101011010110101010110C->B
22101100110101101101101C->A
23101111110111101110101B->A
2411000000110001111B->C
251100110011100110011<empty>A->C
261101001011010110110A->B
27110111101111011101110C->B
2811100001110011111<empty>A->C
29111011011110111011101B->A
301111001111011111111B->C
311111111111111111111<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 ;)

No comments:

Post a Comment