Algorithmic Puzzles

Algorithmic Puzzles is a book of puzzles based on computational thinking. It was written by computer scientists Anany and Maria Levitin, and published in 2011 by Oxford University Press.

Topics

The book begins with a "tutorial" introducing classical algorithm design techniques including backtracking, divide-and-conquer algorithms, and dynamic programming, methods for the analysis of algorithms, and their application in example puzzles.^[1][2] The puzzles themselves are grouped into three sets of 50 puzzles, in increasing order of difficulty. A final two chapters provide brief hints and more detailed solutions to the puzzles,^[2] with the solutions forming the majority of pages of the book.^[3]

Some of the puzzles are well known classics, some are variations of known puzzles making them more algorithmic, and some are new.^[4] They include:

• Puzzles involving chessboards, including the eight queens puzzle, knight's tours, and the mutilated chessboard problem^[1][3][4]
• Balance puzzles^[3]
• River crossing puzzles^[3][4]
• The Tower of Hanoi^[4]
• Finding the missing element in a data stream^[1]
• The geometric median problem for Manhattan distance^[1]

Audience and reception

The puzzles in the book cover a wide range of difficulty, and in general do not require more than a high school level of mathematical background.^[3] William Gasarch notes that grouping the puzzles only by their difficulty and not by their themes is actually an advantage, as it provides readers with fewer clues about their solutions.^[1]

Reviewer Narayanan Narayanan recommends the book to any puzzle aficionado, or to anyone who wants to develop their powers of algorithmic thinking.^[4] Reviewer Martin Griffiths suggests another group of readers, schoolteachers and university instructors in search of examples to illustrate the power of algorithmic thinking.^[3] Gasarch recommends the book to any computer scientist, evaluating it as "a delight".^[1]

References