Using three types of solitaire puzzles, peg-jumping games, chessboard tiling problems, and a type that the authors call replacement-set games, the authors provide examples of the use of invariants in the design and solution of such puzzles. Their aim, stated several times throughout the paper, is to provide examples “with a view to using them as an aid to teaching algorithmic problem-solving.”

With regard to this pedagogical goal, the material in Sections 2 and 3 on peg games and tiling is accessible to upper-level undergraduates with some knowledge of abstract algebra. However, the results in these sections are primarily about solvability rather than designing algorithms. Invariant properties of polynomials over a finite field are used to classify the positions in peg-jumping puzzles. The authors prove necessary and sufficient conditions on m and n for tiling an m × m checkerboard with a single 1 × 1 tile and a set of n ×1 tiles, where n < m.

It is not until the much longer Section 4 on replacement-set games that more attention is given to developing algorithmic solutions to puzzles. The material, which depends heavily upon the theory of cyclotomic polynomials, seems much more suited to a graduate special topics seminar than a standard or advanced course in algorithm design. The puzzles, which involve stacking and unstacking checkers on the cells of an infinite one-dimensional tape according to a fixed set of rules, are variants of the so-called “nuclear pennies game,” and the authors describe how to construct and solve an infinite class of such puzzles.

Throughout the paper, some remarks are included to explain or justify nonstandard or unfamiliar notations; for instance, the authors adopt the so-called Eindhoven quantifier notation and use a lengthy footnote to describe it. The reasons for such notational choices are not always clear from the paper itself, but the references (particularly chapter 2 of the third author’s PhD dissertation) supply insights into the pedagogical motivations behind such decisions.

While Section 4 seems to be less clearly valuable as a teaching example than the two preceding sections (at least for standard algorithm design courses), the results are nonetheless interesting and thought provoking. Most of the necessary theorems on fields and field extensions, cyclotomic polynomials, and so on are provided in the paper; the references and Wikipedia provide the rest.