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.
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.
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:
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]
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
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. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.
Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited to being an endeavor for amateurs, many topics in this field require no knowledge of advanced mathematics. Recreational mathematics involves mathematical puzzles and games, often appealing to children and untrained adults, inspiring their further study of the subject.
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, the tour is closed ; otherwise, it is open.
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that satisfies the given conditions. Mathematical puzzles require mathematics to solve them. Logic puzzles are a common type of mathematical puzzle.
God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the Deity is based on an assumption that only an omniscient being would know an optimal step from any given configuration.
The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:
Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?
In computational complexity theory, a problem is NP-complete when:
William Ian Gasarch is an American computer scientist known for his work in computational complexity theory, computability theory, computational learning theory, and Ramsey theory. He is currently a professor at the University of Maryland Department of Computer Science with an affiliate appointment in Mathematics.
Chases and Escapes: The Mathematics of Pursuit and Evasion is a mathematics book on continuous pursuit–evasion problems. It was written by Paul J. Nahin, and published by the Princeton University Press in 2007. It was reissued as a paperback reprint in 2012. The Basic Library List Committee of the Mathematical Association of America has rated this book as essential for inclusion in undergraduate mathematics libraries.
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation is a book on the travelling salesman problem, by William J. Cook, published in 2011 by the Princeton University Press, with a paperback reprint in 2014. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.
Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle is a book on the mathematics of Sudoku. It was written by Jason Rosenhouse and Laura Taalman, and published in 2011 by the Oxford University Press. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. It was the 2012 winner of the PROSE Awards in the popular science and popular mathematics category.
Calendrical Calculations is a book on calendar systems and algorithms for computers to convert between them. It was written by computer scientists Nachum Dershowitz and Edward Reingold and published in 1997 by the Cambridge University Press. A second "millennium" edition with a CD-ROM of software was published in 2001, a third edition in 2008, and a fourth "ultimate" edition in 2018.
Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles is a book on reverse mathematics in combinatorics, the study of the axioms needed to prove combinatorial theorems. It was written by Denis R. Hirschfeldt, based on a course given by Hirschfeldt at the National University of Singapore in 2010, and published in 2014 by World Scientific, as volume 28 of the Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore.
Sacred Mathematics: Japanese Temple Geometry is a book on Sangaku, geometry problems presented on wooden tablets as temple offerings in the Edo period of Japan. It was written by Fukagawa Hidetoshi and Tony Rothman, and published in 2008 by the Princeton University Press. It won the PROSE Award of the Association of American Publishers in 2008 as the best book in mathematics for that year.
Quantum Computing: A Gentle Introduction is a textbook on quantum computing. It was written by Eleanor Rieffel and Wolfgang Polak, and published in 2011 by the MIT Press.
The Tower of Hanoi – Myths and Maths is a book in recreational mathematics, on the tower of Hanoi, baguenaudier, and related puzzles. It was written by Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, and published in 2013 by Birkhäuser, with an expanded second edition in 2018. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.
Polyominoes: Puzzles, Patterns, Problems, and Packings is a mathematics book on polyominoes, the shapes formed by connecting some number of unit squares edge-to-edge. It was written by Solomon Golomb, and is "universally regarded as a classic in recreational mathematics". The Basic Library List Committee of the Mathematical Association of America has strongly recommended its inclusion in undergraduate mathematics libraries.
Games, Puzzles, and Computation is a book on game complexity, written by Robert Hearn and Erik Demaine, and published in 2009 by A K Peters. It is revised from Hearn's doctoral dissertation, which was supervised by Demaine. The Basic Library List Committee of the Mathematical Association of America has recommended it for inclusion in undergraduate mathematics libraries.