Introduction

“My interview at a company well known for its hard and puzzling questions was a joke after this class.”

-Boris, a graduate of my puzzle class at NYU

Overview

Some people, like me, love puzzles. Others feel they must study puzzles to succeed at job interviews. I’ve written this book for both. You’ll find here some kick-ass puzzles, but I also take you on a kind of tutorial tour of problem solving techniques to help you face new puzzle challenges. Oh, and then there’s the possibility of a prize if you solve the super-hard puzzles at the end.

Puzzles as an interviewing tool have many detractors. Criticism often comes down to the implausibility of a puzzle scenario in which, say, a perfectly logical person is mute and refuses to write. Now, I admit to having written such puzzles, but most of my puzzles come from real problems (e.g., occasionally failing hardware being modeled by occasional liars). In my own research, I try to abstract the problem at hand to a puzzle, in the hopes that I can understand the fundamental issues and take care of the window dressing later. It works pretty well. So, to me, puzzles, especially the right kinds of puzzles, provide a tunnel into scientific and engineering insight.

So why do I write puzzles for other people? First, because they’re fun. Second, because they exercise the brain in a useful way. In the puzzle course that Boris talks about in the epigraph, students write programs every week. The programs compete (each having two minutes to run) and the winner gets a Kit Kat bar. I lecture little, offering the techniques you’ll find in Part II. By the end of the course, the students find themselves incomparably better at solving the kind of application problems the real world throws at them-problems that algorithms professors will call “intractable” but that nevertheless have to be solved. I can’t tell you exactly what brings about the transformation in the students, but it happens.

Most of the puzzles in Part I of this book come from my columns in Scientific American and Dr. Dobb’s Journal, where many readers have given me important and imaginative feedback. That feedback, or sometimes the puzzle itself, has suggested new variants, so you will find more to think about, even if you’ve already encountered the puzzles in those magazines.

Many times, when I have no idea how to solve a puzzle (and this happens for puzzles I invent, too), I begin with an initial attempt scribbled on paper. It’s usually wrong, but sometimes it leads to a better approach. You’ll find room to scribble at the end of each puzzle statement in Part I.

Solving puzzles demands a mindset, a vulnerable openness at the beginning followed by a rigorous drive to find a solution-spiritually akin to the technique discussed in Part II called “simulated annealing.” Mine is rarely the only possible mindset. When other puzzlists have shared better ideas with me, I present their approaches to you.

Each short chapter in Part I, “Mind Games,” presents a puzzle. The solutions to those puzzles appear at the end of Part I. Part II, “The Secret of the Puzzle,” shows how to solve several classes of puzzles, both by hand and by computer. You’ll find ways to solve elimination puzzles like Sudoku, scheduling puzzles, mathematical word puzzles, and probabilistic puzzles. The approach is unapologetically algorithmic. I believe in using every tool at your disposal. Part III, “Faithful Foes,” asks you to solve a mystery involving codes, bank accounts, and geography. You’ll accompany a certain mathematical detective named Dr. Ecco and some of his friends. (You may have met them before.) Solve the mystery and you have a chance to win a prize.

Have fun and good luck.