Learning Make with the Towers of Hanoi

[article]
Summary:

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 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 n-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

Pages

About the author

AgileConnection is one of the growing communities of the TechWell network.

Featuring fresh, insightful stories, TechWell.com is the place to go for what is happening in software development and delivery.  Join the conversation now!