Towers of Annoyed [From the Archives]

My “Day I Left Pennsylvania” led me to some archived website posts (before blogs were invented) I had written many years ago. I’m re-posting them now. Bear in mind that most of the content in this series is over 5 years old. I have left the content more or less intact. I have removed some links and added some others — but that’s it. Enjoy!


(Just kidding, it’s “Towers of Hanoi” :) )

hanoiAny first or second-year computer programmers have likely run into this problem, most likely when they first get introduced to recursion.

Legend has it that in a temple in the Far East, priests are attempting to move a stack of disks from one peg to another. The initial stack had 64 disks threaded onto one of three pegs and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from that peg to a second peg. The only constraints are that disks must be moved one at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding disks.(Supposedly the world will end when the priests finish, so you would kind of wonder why we would want to help them, eh? ;^)

Ok, that’s a mouthful! Let’s start by breaking this down into some simpler rules:

The Rules

  1. Three pegs, arranged horizontally. The object is to move all disks from one peg to either of the other two pegs.
  2. One “move” consists of taking the topmost disk of one peg and placing it at the topmost position on another peg.
  3. The topmost disk on any peg must always be the smallest disk on that peg. (i.e. you can’t put a medium sized disk on top of a smaller disk, but you can put it on top of a larger disk.)
  4. While you technically have unlimited moves, it is considered favorable to make the transition in as few moves as possible.

Walkthrough

First, let’s do a walkthrough of an example using only three disks. The setup would look nearly identical to the picture above, except without the green disk. Below, we’ll use the notation: x -> y where X is the source peg and Y is the destination peg. So if we were to say 1 -> 3 then that means we take the topmost disk on peg 1, and place it on peg 3.

#
Move
Diagram
Description
Starting
= | |
(L)arge, (M)edium, and (S)mall disks are all on peg 1
1
1 -> 3
- | _
Move (S) from peg 1 to peg 3 (LM, empty, S)
2
1 -> 2
_ _ _
Move (M) from peg 1 to peg 2 (L, M, S)
3
3 -> 2
- |
Move (S) from peg 3, on top of (M) (L, MS, empty)
4
1 -> 3
- _
Move (L) from peg 1 to peg 3 (empty, MS, L)
5
2 -> 1
_ _ _
Move (S) from peg 2 to peg 1 (S, M, L)
6
2 -> 3
_ | -
Move (M) from peg 2 on top of (L) (S, empty, L)
7
1 -> 3
| | =
Move (S) from peg 1 on top of (L) & (M) (empty, empty, SML)

Some key points here that may not seem immediately obvious are: Notice that from step 2 to step 4 the moves seem to be redundant or useless. The significance to these moves it that it gets the (L) disk moved to a different disk. Another interesting point is if you look at the sequence of boldfaced letters in the “Description” column, you’ll notice that (S) is moved 4 times, while (M) only twice, and (L) once. We can infer a couple things from these frequencies: First, the larger the peg, the less it moves. This means that there is a definite conservation of movements in terms of size. While the small one can be moved all over, the large one is only moved when it’s getting moved to it’s new permanent home. There is also a possibility that the number of times a disk is moved is a power of 2.

Moves Disk
8
[tiny]
4
[.Small.]
2
[..Medium..]
1
[.......Large.......]

What does this mean exactly?

Well if we consider the italicized letterings in the top row to be simply a guess, then it means that each additional disk that is added must be moved twice as much as the disk below it. The bottom most disk will be moved once, to its final destination, and it will more than likely be directly at the midpoint of all the moves, as seen above.

Move #
Tiny
Small
Medium
Large
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
9
X
10
X
11
X
12
X
13
X
14
X
15
X

So looking back at our original image of the problem, what’s the best way to tackle a four-disk towers set? Well we can first assume that it will take 15 moves, as per our inferences above. (1 + 2 + 4 + 8 moves). We can also assume that the (L) disk will be moved on move 8. The (M) disk will be moved on moves 4 and 12, and the (S)mall on moves 2, 6, 10, and 14, and then (T)iny one the rest of the time. How can I make this assumption?

See the pattern here? As you move down each disk, you make twice as many moves, and the moves are always at the midpoints of the next disk’s moves. The puzzle practically solves itself after seeing this graph. Before continuing on, see if you can solve it yourself. The order of the moves is already determined for you, so all you have to do is figure out where to move the disk! :)

The solution is like this:

Move
Tiny
Small
Med
Large
1
1>3
2
1>2
3
3>2
4
1>3
5
2>1
6
2>3
7
1>3
8
1>2
9
3>2
10
3>1
11
2>1
12
3>2
13
1>3
14
1>2
15
3>2

Do you get it? Step #9 is especially important. Placing the smallest ontop of the largest, instead of on an empty peg is crucial, as it eliminates a potential redundancy. A good way to really grasp this is to get four pieces of paper (I used four poker chips with a sharpie marker to label them) and label the papers 1 through 4 (or T,S,M,L, whatever). Then follow the movements through this sequence.

If you’d like to go off on a really nerdy tangent with this, you may notice that the number of moves in each column in our matrix there (Tiny, Small, Med, Large) corresponds with the binary (base 2) number system. The Large column always has 1 move, the Med column always 2 move, the Small always 4, and tiny always 8. If we were to add a smaller disk, it’s value would be 16, the next 32, and so on. Each one would increase by a power of 2.

16 8 4 2 1 <— # of moves necessary for each disk.
# T S M L XL Notice the exponential progression?
1 1>3
2 1>2 (table truncated for simplicity)

If you’re interested in really working those neurons and understanding this inside and out, just pick a number of disks and solve it. You can work it through step by step like we did here; Just remember the two rules: the number of moves it will require is the sum of all 2^N, where N goes from (X-1) to 0, where X is the number of disks used. Then when you’re plotting the points, make sure each move is at the midpoint of the moves to its left.
Problem paraphrased from How to Program C++ by H.M. Deitel & P.J. Deitel