An extension of the well-known Towers of Hanoi puzzle--a fixture in introducing recursive algorithms in programming--is explained in this paper.

The extension is to regard the pegs as vertices in a digraph, so that adjacency becomes a constraint. Since a complete characterization of digraphs for which the Hanoi puzzle is solvable is known, namely graphs whose transitive closure contains a 3-clique, the authors are interested in infinite graph families that admit optimal solutions. The solvability characterization is obvious: in such a graph, there is always a path to a 3-clique; if the pegs are the clique’s vertices, then the situation reduces immediately to the classical Hanoi puzzle.

The graph families studied are motivated directly by the observation on solvability. The authors define these families in a somewhat elliptical manner and give only diagrams. The bulk of the paper contains numerous inductive arguments and the main interest attaches to the optimality arguments. The move counts obtained are quite similar to the classical case, so nothing remarkable emerges on that account.

I must admit that while these arguments may be of use in analyzing certain kinds of combinatorial routines, the paper is so specialized that it seems to fall outside the scope of this journal.