Algorithmic Puzzles

Anany Levitin and Maria Levitin
OXFORD UNIVERSITY PRESS USA 2011, 336 PAGES
PRICE £13.99 (PAPERBACK) ISBN 978-0-199-74044-4

This book is a collection of one hundred and fifty puzzles that can be solved by using clearly defined algorithmic procedures. The authors state that solving algorithmic puzzles is the most productive and definitely the most enjoyable way to develop one’s algorithmic thinking skills. If I had any doubts about this before I started working my way through this book I assure you that they are now completely gone.

Writing about a book filled to the brim with puzzles, I feel I have to describe a couple of my favourites.

Puzzle No. 21 Square Dissection
A square can always be divided up into an exact number of smaller squares, apart from the cases of 2, 3 or 5 squares.

Here are some examples of a square being divided into 4, 7 and 8 squares.

The reason that 2, 3 and 5 are not possible is due to the fact that the four right angles of the initial square must be in the smaller squares and this cannot happen in the three special cases of 2, 3 and 5.

Puzzle No. 97 The Game of Topswops
Invented by John Conway this game is traditionally played with the thirteen cards of the same suit.

If you start with five cards, ace to five, from a deck you see clearly how the mechanics of the game works. Shuffle the cards and place them face up so you can see the top card. Use the value on the uppermost card and count that many cards onto the table, then put these cards back on top of the deck. For example, if the deck was ordered from the top 32514 you would count three cards onto the table and then put these cards back on top to get the new order 52314. You now repeat this procedure with the new top card, 5 in this case, to get 41325. The game ends if an ace appears on top, as this results in a one-loop pattern.

You can play this game with more or less cards and also against other players to look for patterns. In a game of two or more people, each player shuffles their set of cards. The first player calls their top card and the second player counts off that number from their pack and then replaces these cards on top of their deck. The second player then calls their top number for the first player. The winner is the first player to get an ace as their top card.

An interesting question to consider is where does the ace have to be placed in the deck to give the greatest number of turns before it appears at the top of the pile?

The book is divided into three main sections – puzzles, hints, and solutions. I highly recommend this book as an engaging ‘pencil and paper’ read.