''Algorithmic Puzzles'' is a book of puzzles based on

computational thinking Computational thinking (CT) refers to the thought processes involved in formulating problems so their solutions can be represented as computational steps and algorithms. In education, CT is a set of problem-solving methods that involve expressin ...

. It was written by computer scientists Anany and Maria Levitin, and published in 2011 by

Oxford University Press Oxford University Press (OUP) is the publishing house of the University of Oxford. It is the largest university press in the world. Its first book was printed in Oxford in 1478, with the Press officially granted the legal right to print books ...

Topics

The book begins with a "tutorial" introducing classical algorithm design techniques including

backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

divide-and-conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dir ...

s, and dynamic programming, methods for the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

, and their application in example puzzles. 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, with the solutions forming the majority of pages of the book. Some of the puzzles are well known classics, some are variations of known puzzles making them more algorithmic, and some are new. They include: *Puzzles involving chessboards, including the

eight queens puzzle The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. ...

knight's tour A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again im ...

s, and the

mutilated chessboard problem The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard (or checkerboard) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 domin ...

* Balance puzzles * River crossing puzzles *The Tower of Hanoi *Finding the missing element in a

data stream In connection-oriented communication, a data stream is the transmission of a sequence of digitally encoded signals to convey information. Typically, the transmitted symbols are grouped into a series of packets. Data streaming has become u ...

*The

geometric median In geometry, the geometric median of a discrete point set in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances or absolute ...

problem for

Manhattan distance Taxicab geometry or Manhattan geometry is geometry where the familiar Euclidean distance is ignored, and the distance between two point (geometry), points is instead defined to be the sum of the absolute differences of their respective Cartesian ...

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. 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. Reviewer Narayanan Narayanan recommends the book to any puzzle aficionado, or to anyone who wants to develop their powers of algorithmic thinking. Reviewer Martin Griffiths suggests another group of readers, schoolteachers and university instructors in search of examples to illustrate the power of algorithmic thinking. Gasarch recommends the book to any computer scientist, evaluating it as "a delight".

References

{{reflist, refs= {{citation , last = Gasarch , first = William , authorlink = William Gasarch , date = December 2013 , doi = 10.1145/2556663.2556674 , issue = 4 , journal = ACM SIGACT News , pages = 47–48 , title = Review of ''Algorithmic Puzzles'' , url = https://www.cs.umd.edu/~gasarch/bookrev/44-4.pdf , volume = 44 {{citation , last = Griffiths , first = Martin , date = March 2014 , issue = 541 , journal = The Mathematical Gazette , jstor = 24496640 , page = 188 , title = Review of ''Algorithmic Puzzles'' , volume = 98, doi = 10.1017/S0025557200001182 {{citation, title=Review of ''Algorithmic Puzzles'', first=Narayanan, last=Narayanan, year=2012, journal=Mathematical Reviews, mr=2866446 {{citation, title=Review of ''Algorithmic Puzzles'', first=Stephan, last=Rosebrock, journal=zbMATH, zbl=1233.00005 Algorithms Puzzle books 2011 non-fiction books Oxford University Press books