Part II: The Secret of the Puzzle

Chapter List

The Puzzles

Part Overview

Ravi, Prasad, and I are working together still at the same software company. The founding partners of our company are always raving about how great it was to have recruited from the heuristics class.

- from a graduate of the Heuristic Problem Solving class at New York University

Part of the charm of puzzles is that they escape formulaic solutions. I often encounter students who do very well in calculus and discrete mathematics but find themselves stumped by puzzles whose reasoning requires only the most elementary algebra. Creativity is not the issue. Some people find the freedom offered by puzzles unfamiliar, and even slightly frightening. In this chapter, together, we will exorcise that fear demon.

The best puzzles may appear impossible at first, until you break them down, try alternatives, and finally solve them. The fact that a similar process is necessary in all large engineering and software projects is one reason that puzzles are used to screen job candidates. (A competing theory is that interviewers use puzzles to see people squirm. I’m not denying there is a little of that.)

If you had asked me a few years ago how to improve your puzzle-solving abilities, I would have recommended trying a lot of puzzles until you understood the patterns. But I’ve come to realize that certain patterns can be taught and their role in puzzles exposed. I’ve taught a class at New York University based on that belief, and it seems not only to hold, but also to be relevant to job success, as you can see from the quote that began this chapter. (By the way, I’m far from the first to create a course based on solving puzzles. Donald Knuth at Stanford and Ken Ross at Columbia had done similar courses before me, so I had existence proofs.)

Okay, I’m biased about the importance of puzzles. But my observation is that the problems people want to solve are often NP-hard (i.e., requiring an exhaustive search to guarantee to get the best answer - see the following sidebar). This is true whether you are doing register allocation in a compiler, or aligning genomes, or allocating seats on an airplane. You can, as a programmer, avoid such problems and write programs for accounts payable systems, but come on - the hard problems make our jobs fun.

What’s an NP-hard Problem?

The term NP (non-deterministic polynomial) refers to the class of problems whose solutions can be verified in polynomial time in the size of the input. For example, if you ask me to find a route through 17 cities that will cost less than $3,000 and I present you a route R, you can easily compute the cost of route R by adding up 17 leg costs. In that case, the cost of verification would be linear in the number of cities, a polynomial of degree 1. Unfortunately, finding such a route may be much harder than verifying it. Intuitively, a problem is NP-complete if its solution can be verified in polynomial time, but there is no known polynomial time algorithm to find the solution. (A full formal definition would also go into the concept of reducibility, but we’ll leave that to the textbooks.) For example, finding a route through a collection of cities that costs less than a certain amount is an NP-complete problem. By contrast, a problem is NP-hard if there is no known polynomial method to find an acceptable solution and possibly not even to verify one.

Since so many puzzles are elimination (or, if you wish, constraint-oriented) puzzles, we’ll look at many of them in this chapter. The most familiar modern example of such a puzzle is Sudoku, though books of brainteasers are filled with other elimination puzzles. An elimination puzzle presents starting conditions, a set of constraints, and a target state. The goal is to reach the target state from the starting conditions while satisfying the constraints.

The reasoning these puzzles embody comes up often in design problems as well. At base, that reasoning entails a careful case analysis. Case analysis is fun if there are a small number of cases, but painful when there are many. For this reason, I present sample pseudo-code in the examples here, and I encourage you to solve these puzzles in your favorite programming language.

Case analysis implies speculation, i.e., reasoning of the form: “Assume the following holds. Here are the consequences.” Sometimes, the consequences are undesirable, so you must unroll one speculative guess and try another one. This kind of guess-and-test strategy works well for games as simple as Sudoku, because the number of speculations is well under 1,000 and usually more like 20.

When the number of guesses is large, you’ll want to use other techniques. My standout favorite is dynamic programming. The classic example of dynamic programming is string edit distance (the basis for the diff program in Unix/Linux). Given two long strings, what is the shortest “edit sequence” of inserts, deletes, and single-letter rewrites that can convert one to the other? Go ahead and give it a try with these two invented genes: TGGAGACAGTCT and TAGATGGTCT.

Without dynamic programming, you could imagine lots of possible edit sequences, but it would be hard to know when you had found one of minimum cost. Dynamic programming offers a simple-to-program, efficient approach that is guaranteed to be optimal for this problem, as we’ll see.

Unfortunately, dynamic programming doesn’t solve all problems. NP-complete problems arise often and you will need to turn to heuristics to avoid an exhaustive search.^[1] I’ll give pseudo-code for my favorite heuristic technique - simulated annealing - and will invite you to try it out on some NP-hard puzzles. We’ll start easy. If you have trouble along the way, note that the solutions to early puzzles offer techniques you can use for the later ones.

^[1]Russians prefer the term “perebor,” which means brute force, to exhaustive search- I like the feeling of that term. I imagine a hardy Russian bear doing perebor on a beehive.