The Towers of Hanoi Puzzle

The Towers of Hanoi puzzle consists of a small board with three pegs on it. On the left most peg a stack of discs is arranged in descending order of size: the largest disc is on the bottom.

The puzzle is to move all the discs from the left most peg to the right most in the shortest number of moves while following these rules:

1. You may only move one disc at a time;
2. A disc may never be placed on top of a smaller disc.

The solution to this puzzle often appears in computer science lectures because it illustrates a recursive algorithm. Suppose that the three pegs are labelled a, b and c. Peg a is the left most and peg c the right most; the aim is to move all the disks from peg a to peg c. In pseudo-code the solution for moving n discs from peg X to peg Y via the third peg (called Z here) is:

hanoi( Peg X, Peg Y, Count n ) { if ( n > 0 ) {Peg Z = not peg X or peg Y hanoi( X, Z, n-1 ) Move 1 disc from X to Y hanoi( Z, Y, n-1 ) } }

So to solve the puzzle for five discs do hanoi( a, c, 5 ) and it will show each move of a disc. It works by moving 4 discs from peg a to peg b, moving the last disc (the biggest) from peg a to peg c and then moving the remaining 4 disks from peg b to peg c. To move each stack of 4 discs the same procedure is followed recursively for smaller and smaller stacks of discs. Moving just three discs requires 7 separate single disc movements. The following trace through of the pseudo-code shows the moves needed. Examining the code you'll find that for n discs 2ⁿ-1 moves are required.

hanoi( a, c, 3 ) hanoi( a, b, 2 ) hanoi( a, c, 1 ) hanoi( a, b, 0 ) Move one disk from a to c hanoi( b, c, 0 ) Move one disk from a to b hanoi( c, b, 1 ) hanoi( c, a, 0 ) Move one disk from c to b hanoi( a, b, 0 ) Move one disk from a to c hanoi( b, c, 2 ) hanoi( b, a, 1 ) hanoi( b, c, 0 ) Move one disk from b to a hanoi( c, a, 0 ) Move one disk from b to c hanoi( a, c, 1 ) hanoi( a, b, 0 ) Move one disk from a to c hanoi( b, c, 0 )

And this is connected with Make how?It turns out that GNU Make is powerful enough to solve the Towers of Hanoi puzzle. Here's a Makefile that does just that (by default it solves the puzzle for two disks):

DISCS=DD .PHONY: all all: a-c.$(DISCS) a-%.D: ; @echo Move one disk from a to $* b-%.D: ; @echo Move one disk from b to $* c-%.D: ; @echo Move one disk from c to $* a-b.D%: ; @$(MAKE) a-c.$* a-b.D c-b.$* a-c.D%: ; @$(MAKE) a-b.$* a-c.D b-c.$* c-a.D%: ; @$(MAKE) c-b.$* c-a.D b-c.$* c-b.D%: ; @$(MAKE) c-a.$* c-b.D a-c.$* b-a.D%: ; @$(MAKE) b-c.$* b-a.D c-b.$* b-c.D%: ; @$(MAKE) b-a.$* b-c.D a-c.$*

Before diving into how that works (and learning about some Make syntax along the way) let's try it out. The number of discs is encoded in the DISCS variable by setting it to the appropriate number of letter D's: one D per disc. For example if DISCS is DDD then this Makefile will solve the puzzle for 3 discs. We use this encoding (perhaps you'd call it a hack) because GNU Make does not include any facility for doing arithmetic. Here's a sample run for three discs:

% gmake DISCS=DDD Move one disk from a to c Move one disk from a to b Move one disk from c to b Move one disk from a to c Move one disk from b to a Move one disk from b to c Move one disk from a to c

Variable PrecedenceNotice how the value of the DISCS variable was specified on the command-line, overriding the definition of DISCS on the Makefile's first line. Another way to specify DISCS is in the environment. In bash if you do

% export DISCS=DDD % gmake Move one disk from a to b Move one disk from a to c Move one disk from b to c

you'll perhaps be surprised that the environment variable value of DISCS has been discarded and the value on the first line of the Makefile has been used (in this case DD and the two disc puzzle is solved). That's because GNU Make has a strict order in which it considers variables: A command-line definition takes precedence over...A Makefile definition which take precedence over...
An environment variable. If we want to switch the order of the last two, so that the environment takes precedence over definitions in the Makefile we run with the -e switch:

% export DISCS=DDD % gmake -e Move one disk from a to c Move one disk from a to b Move one disk from c to b Move one disk from a to c Move one disk from b to a Move one disk from b to c Move one disk from a to c

Phony TargetsThe first rule in the Makefile is for a target called all. There's also a line which specifies that all is phony. Normally, GNU Make considers targets to be actual files, marking a target as phony means that GNU Make treats the target as simply a name, and doesn't check to see if a file with the same name exists. If a target is not phony then GNU Make will check to see if the target exists to decide whether a rule needs to be run. Since we want our Makefile to always run the all rule, since it's the rule that fires off the Towers of Hanoi solution we mark it as phony. Even if there's a file called all the all rule runs. A Simple PatternIf we start with the simplest case, one disc, we can trace through the Makefile to see what happens when we type gmake DISCS=D. The all rule has a dependency on a-c.$(DISCS) and since DISCS is D that means the rule is equivalent to:

all: a-c.D

To build all we need to build a-c.D. To encode the different disc moves in the Makefile I've used targets in the form -.. So a-c.D means move one disc (the single D) from peg a to peg c. To build a-c.D GNU Make searches for an explicit rule to make it, that is a rule whose target is a-c.D. There isn't one in the Makefile so GNU Make searches for a pattern rule that applies. A pattern rule is a rule whose target contains a percent sign. The percent sign acts as a wildcard and matches any string (including the empty string). GNU Make finds the following matching rule:

a-%.D: ; @echo Move one disk from a to $*

and matches the % against c in a-c.D. This pattern is a rule that specifies how to move one disc from peg a to some other peg matched by %. When it runs it will print out

Move one disk from a to c

$* is an automatic variable set by GNU Make for this rule and it contains the value matched by the %, which GNU Make refers to as the stem. In this case the matching part was just the letter c. Since GNU Make only allows one % sign in the target of a pattern rule we have to write additional rules for moving a single disc from peg b and from peg c.

b-%.D: ; @echo Move one disk from b to $* c-%.D: ; @echo Move one disk from c to $*

To recap: GNU Make looks for explicit rules first, then searches for a pattern rule that uses the % wildcard and if it finds a match sets the $* variable for the part that matched the % sign. GNU Make has two ways of specifying the commands for a rule, the most familiar is the “line that starts with a tab” form:

foo.o: foo.c compileit

If there's only one command to run then the more compact “semicolon” form that's used in the puzzle Makefile can be used:

foo.o: foo.c ; compileit

It takes less space in the Makefile and has the added advantage that is can be copied and pasted without being concerned that the tab in the other form has been turned into spaces. Make GoalsNow consider a slightly more complex case, here we use the Makefile to solve the puzzle for two discs by running gmake DISCS=DD. In this case the all rule evaluates to

all: a-c.DD

and GNU Make looks for a rule to build a-c.DD. It finds another more complex pattern rule:

a-c.D%: ; @$(MAKE) a-b.$* a-c.D b-c.$*

In this case the % sign matches the second D in a-c.DD and $* will be set to that same single D. The command, when building a-c.DD is:

$(MAKE) a-b.D a-c.D b-c.D

which means “run make and build a-b.D, a-c.D and b-c.D.” The targets specified on the command-line of Make are called goals and they are built from left to right. That means that a-b.D will happen before a-c.D which will happen before b-c.D. In the language of Towers of Hanoi that means “move a disc from a to b then move a disc from a to c and finally move a disc from b to c” which is exactly what is required. Try tracing through the three disc case (DISCS=DDD). A Make goal is the name of any target specified in the Makefile (or a target that can be built by using a pattern rule) and directs Make to build that target (or targets). If no goal is specified then the first target seen in the Makefile is considered to be the goal. In the puzzle Makefile it's the phony target all. More Complex PatternsAlthough we don't use them in the example Makefile GNU Make has more complex pattern rules where a % sign can appear in the target and the prereq of the rule. A common example would be a rule for building a .o file from a .c:

%.o: %.c ; compileit

The two percent signs each have the same value: if we're building foo.o then this pattern would apply if there were a file called foo.c. The automatic variable $@ is set to the value of the file on the left-hand side of the : (e.g. foo.o) and $< to the file on the right-hand side (e.g. foo.c). As before $* is set to the part of the filename that is matched by the % (e.g. foo). No Phony PatternsEarlier I mentioned that the all target is phony because it's not a real file and we don't want Make confused if there were a real file called all in the current directory. The same is true for the other targets in this example. For example, if there were a file called a-c.D then we'd never see the messages for moving a disc from peg a to peg c. What you'd like to specify is something like:

.PHONY: a-c.%

so that any movement of discs from a to c would be considered phony. Unfortunately, there's no such syntax in GNU Make, .PHONY can only be used with explicit target names and trying to specify all the possible combinations of a, b, c and different numbers of D's would be impossible. ConclusionThe designers of Make didn't intend it to be used in this way, but it's a good example of the power of GNU Make that it can solve a puzzle like the Towers of Hanoi. Next month I'll get back to more mundane topics and show you a single character you can insert into your Makefiles to speed them up.