Puzzle Building and the Creative Mind

It's an article about puzzles. I thought I would organize it as a series of questions, like a FAQ, because questions and puzzles are both manifestations of the same thing. They both have answers, and when they are left unanswered, or unsolved, we lack closure. This article, then, is a series of closures.

Among other things, I am a constructor of logic puzzles -- Sudoku, Kakuro, Slitherlink, and a few others. My website, Krazydad.com, is full of them; mostly in the form of PDF files, so people can print out small batches of them to solve with a pencil. Like a drug dealer, I produce them in small batches so you'll get addicted and come back for more.

I started making them for myself, and my wife. Most nights, before going to sleep, we solve a few puzzles with paper and pencil. It's an addictive bedtime ritual. I make them for my friends, and for visitors to my website. When visitors to the website click the ads, or send me donations, I make a little money. Puzzles aren't making me rich though - I'm keeping my day job, as a programmer for Yahoo! And even if puzzles made me no money at all, I'd still probably make them, because I'm addicted to solving them. I'm still my own best customer.

There are very few people in the world who have figured out a way to make a living from puzzle construction. One of these is Will Shortz, Crossword Editor for the New York Times, who is more of a puzzle editor than puzzle constructor. The folks who design crosswords for the New York Times (probably the highest paying publication) get paid $200 for the daily puzzle, and $1000 if they are lucky enough to land a Sunday puzzle. There are a whole slew of people working on crosswords, so it would be an enormous achievement for any one puzzle constructor to average more than a few hundred dollars a week. In my experience, book and magazine publishers pay very little for puzzles, and the kind of computer-generated puzzles I specialize in are a ubiquitous commodity.

My theory is that the brain is a natural pattern-matching machine. One of the brain's main purposes is to solve puzzles - originally these would be caveman puzzles like "How do I open a clam?" and "What should I do when charged by a woolly mammoth?". In solving puzzles, we are fooling the brain - the brain solves whatever puzzle it is is presented with, having no simple way of measuring how useful the particular puzzle being solved is. If I ask you, "What is 12 + 17 ?" it is very hard for you to simply ignore the question, without ferreting out the answer.

Recreational Puzzles are a luxury, of course. A high standard of living has removed many of the more useful puzzles from our day-to-day lives, yet we still have a need to solve them, whether they are useful or not. Have you ever noticed that some people always seem to be embroiled in some kind of soap-opera intrigue -- no matter how many real stressors they have going on in their lives at the moment? The would be miserable sipping a Pina Colada on the beach in Kauai. I think this is a manifestation of the same thing - these people have a need to solve puzzles, whether real puzzles exist or not. If you know any of these people, you should introduce them to Sudoku.

In my life, recreational puzzles also serve as a form of escape, as do books and movies, and as a way to occupy the brain in situations where you can't accomplish much else, such as riding the train, or sitting in a doctor's office. When I recently reported for Jury Duty, I brought a stack of blank puzzles and left it in the Juror waiting room. I hope they weren't thrown out!

A good puzzle is addictive. After you finish it, you reach for the next one. I think this addictive property is most affected by carefully controlling the difficulty of the puzzle. That difficulty level needs to be be just right for you (and it very much depends on the experience and intuition of the solver). A good puzzle is like an Al Dente noodle. It has some firmness to it, but it is still pliable. The difficulty is right at the edge of what you're capable of.

Much of this character comes from the variety of puzzle, rather than puzzle itself.

Here I am talking about puzzle variety - Sudoku versus Crosswords, as opposed to a specific puzzle. The criteria for good puzzles is similar to that for strategy games like Go and Chess (which are a kind of multi-player puzzle). The ideal form of these games is "a minute to learn, a lifetime to master" and so it goes with puzzles.

Good puzzles are easy to explain. In my printable puzzles, I include a paragraph at the bottom that explains how to solve the puzzle. Ideally, this paragraph must serve to introduce someone to the puzzle who has never solved this type of puzzle before. If I can't explain it in a short paragraph, than the number of new solvers I am going to attract is going to be very small. One of my personal favorites of the new crop of Japanese logic puzzles is called Nurikabe, but I find it difficult to explain the rules succinctly enough for that little paragraph, so I have hesitated to put Nurikabe on my website.

Ideal puzzles have a broad range of solving strategems. I personally find Sudoku puzzles slightly more satisfying than Kakuros, because I have reduced Kakuro to a smaller set of solving strategems, so solving them is a little bit more tedious. This experience may depend on the solver though. My wife finds Kakuro more appealing, for similar reasons - she has reduced Sudoku to a small set of strategems and finds Kakuro more interesting. One of the reasons I have been experimenting with alternate tiling systems for my Slitherlink puzzles is that these tiling systems (such as Penrose tiles) increase the catalog of strategems available to the solver.

When a puzzle has a wide variety of solving strategems, it can be generated in a wide range of difficulties, to appeal to a greater number of solvers with diverse skills.

I should also mention that while there are some puzzle varieties that are wonderful, they are not necessarily wonderful for my website. I love crosswords, but I don't offer them.

Because I don't have a lot of free time, and perhaps because I'm a huge nerd, I produce my puzzles with computer software (which I write and run). As you'll find out later, in order to teach a computer to construct a puzzle, I first have to teach it to solve the puzzle. This means that the puzzles on my website must be solvable by a computer. This rules out crosswords, which demand that the clues be written by a clever human. For me, much of the appeal of a good crossword puzzle is puzzling out the meaning from a deviously written clue. Good crossword clue writing is one of those things the brain does well but that computers will not achieve in my lifetime.

Producing puzzles with computers generally means my puzzles usually involve either numbers, or simple abstract graphics. This restriction has the side benefit that my puzzles don't require knowledge of the english language nor western pop culture. Unlike the TV Guide Crossword, the puzzles are culture-independent, appealing to a diverse international audience.

I personally don't much like solving sudoku and similar puzzles on a computer screen. I prefer to solve them in a chair, or better yet, in bed (with a pen, in my case), and the puzzles on my website are intended for a similar audience of slothful Luddites. For the most part, most of the puzzles on my site are in the form of PDF files, intended to be printed, and solved on paper.

As the proud owner of a cheap-ass printer, I don't like spending fifty dollars on printer cartridges, so I prefer it if my printable puzzles don't generate a lot of solid black squares which eat through ink and toner. Similarly, I prefer it if the solving process doesn't require me to shade in squares or polygons, using up a lot of ink or lead, and making excessive motions which might burn calories.

Because I deal puzzles like crack, I want people to return to my website, I hope my puzzles have that aforementioned addictive quality. But in addition, there are a few qualities I am attracted to personally: I like a puzzle that is pretty, and well balanced. Many (but not all) of my puzzles employ symmetrical layouts. I tend to gravitate to round layouts, rotational symmetry or 180 degree symmetry.

Finally, the puzzles I offer must cater to the specific community that visits my site, which, when I think about it, is kind of a self-fulfilling prophecy. People visit my site because they like what they find there, but also, if I find they like a particular thing a lot, I make more of that thing.

My guess is that there are two principal kinds of puzzle solvers (although in reality, I suppose real people tend to combine these two types).

The majority are what I would call "comfort solvers". These folks like one kind of puzzle only, probably Sudoku, and they don't like them too difficult. They are not solving the puzzles so much for the challenge, as for something to do to keep their brain engaged. I know from the occasional email that some of these folks are retired, or otherwise idle, or printing the puzzles out for their parents and patients.

The minority are people more like me, who I call the "challenge solvers". These people like a really tough puzzle that might take all evening or even two or three days to tease out. Not only do these folks like the tougher puzzles, but they also are more likely to try new varieties of puzzles.

How do I know that the "comfort solvers" are in the majority? The statistics I get from my webserver shows me that. Here is yesterday's breakdown showing the six most popular puzzle varieties on my website:



The full diagram looks like a typical "long tail" diagram with all the more obscure puzzle varieties meriting one or two stars.

The majority, the "comfort solvers" are not particularly interested in constantly trying new varieties - they tend to prefer old favorites (Sudokus in my case...). If you look at the rack of puzzle magazines at your local drugstore or supermarket, you'll find that the publishing industry is well aware of this distribution. Most of the magazines are full of easy-level puzzles in a well known format. Variety magazines featuring difficult puzzles are harder to find.

While most visitors to my website are comfort solvers, I am definitely not. I like tough puzzles, and I like to change puzzle varieties fairly frequently.

Perhaps that is why I like making puzzles in addition to solving them. Learning how to make a new puzzle is one of the hardest puzzles of all! Unfortunately, the audience for new puzzle varieties is definitely way out on the long tail, so designing new puzzles is also not likely to make me rich.

The preponderance of "comfort solvers" saddens me a little, because it can be more fun for me to figure out how to make interesting new puzzles. It's also more fun to figure out how to make tough puzzles, because it involves teaching the computer how to *solve* tough puzzles - more on that below.

The short answer: take a shower. That's pretty much where all my good ideas come from.

I've spent little time attempting to create new puzzles varieties out of thin air. I would imagine it to be very hard to do. Much of my creative process involves modifying existing things, or mashing up two things, rather than inventing entirely new things (and I am not even sure such a thing is really possible - it seems like everything, both physical and intellectual, is made of stuff that already exists).

Nonetheless, there are some talented puzzle constructors out there who have produced remarkably fruitful and diverse works. I'll talk about them more below. But I'm definitely no Sam Loyd.

But occasionally, a good idea will pop into my head, unbidden, usually in the shower. The two most interesting new puzzle varieties I have created are Krypto Kakuro and the Variety Slitherlink, both of which are varieties of established puzzle varieties popularized by the Nikoli company in Japan. In both cases, I came up with the variant during a period when I was working on creating software to generate the original. So the new puzzle was a natural extension (it seemed to me at the time) of the original puzzle, and the original puzzle was much in my thoughts.

Prior experience with things that are near-puzzles helps as well. I had a lot of experience with amateur cryptography and cryptogram puzzles, which lead me try encrypting Kakuro puzzles to create Krypto Kakuro. My exposure to tiling systems (Penrose tiles in particular), and my experience using a variety of tiling systems to build mazes, led me to the idea of trying them out for Slitherlink puzzles. The more algorithmic ideas I am exposed to, the richer the palette of ideas I can bring to puzzle creation, and the more connections I can draw between diverse idea spaces.

Most of the puzzles I work with consist of a set of constraints, which are expressed in the rules of the puzzle. There is usually a very large number of possible puzzles meeting those constraints. For example, when you take various symmetries into account, there are about 5.5 billion different sudoku puzzles.

Many of the logic puzzles from Nikoli, such as Slitherlink share some other common features. I've noticed that a lot of them feature networks which resemble mazes. This structures of connected walls is called a Nurikabe in the Japanese puzzle books. A maze, of course, is a kind of puzzle, and the connections between mazes and logic puzzles seems close.

It has been demonstrated that a lot of logic puzzles, including Sudoku and Slitherlink are NP-Complete, which is a measure of their algorithmic complexity. One ramification of this is that there is no known algorithm for efficiently solving these puzzles in a fixed amount of time. The hard puzzles may take much longer to solve than the easy ones. This makes it difficult to generate hard puzzles - for example, it was extremely time consuming to generate the hundreds of large Kakaro puzzles that appear on my website. It might take my computer 15 minutes to produce a single such puzzle.

Three of my heroes in this area are Martin Gardner, A.K. Dewdney, and Sam Loyd. Gardner (now 92 years old, and recently interviewed in Make magazine) wrote the Mathematical Recreations article for Scientific American for many years, and was a great compiler of mathematical puzzles, many of which are collected now in various Dover editions. It was Gardner who popularized Penrose's Tiles, Conway's game of "Life" and Mandelbrot's Fractals, all of which are grist for the puzzle mill.

A.K. Dewdney, who took over Gardner's role at the magazine with his "Computer Recreations" column, was a huge influence on me. I was learning my craft as a programmer when Dewdney was active at the magazine. His articles on computer wallpaper, fractals, and artificial life were all seeds that spurred me to write software and algorithms, some of which I still use and cherish. Dewdney's columns were collected in the book "Armchair Universe", now sadly out of print (is a book ever "happily out of print" I wonder?).

It's hard for me to mention Gardner and Dewdney, without also mentioning Douglas Hofstadter and Clifford Pickover, but I will attempt to do so.

Sam Loyd, an inspiration for the likes of Martin Gardner and Donald Knuth, is a more recent discovery for me. His 1914 "Cyclopedia of Puzzles" is an amazing collection, and available in full online. Unfortunately, the work is full of much of the racist caricatures which was prevalent then, and his prose style hasn't withstood the test of time either. You have to get past that stuff to get to the puzzles. Then you can admire the mind that came up with this nifty lip reading novelty.

The thing that impresses me when I see monstrosities like Loyd's "Out of the Klondike," is that this puzzle was generated without a computer!

"Wow!" I think, "That guy must have had a lot of time on his hands!" Amusingly, this is the exact same comment my computer-generated mosaics tend to elicit from the ill informed...

Although Gardner, Dewdney and others serve as inspiration, my biggest influence, puzzle-wise, is not an individual, but a company in Japan: Nikoli.

In recent years, all good puzzles seem to come from Japan. The most popular publisher of puzzles in Japan is a company called Nikoli, which prints a number of magazines for the Japanese market. Although Sududu and Kakuro are both older puzzles that were originally published in the west by Dell, it is Japan's Nikoli that is responsible for their enormous popularity in recent years.

Nikoli specializes in the kinds of culture-independent numeric and logic puzzles that I feature on my website. In addition to Sudoku and Kakuro, they have originated a bewildering variety of new logic puzzles, some of which you can read about on Wikipedia.

Nikoli has managed this without having a resident puzzle genius. Instead they really on a carefully cultivated society of readers. Nikoli publishes a quarterly magazine, "Puzzle Communication Nikoli," which presents new puzzle varieties submitted by readers. This magazine is a crucible for generating new puzzle varieties. When a puzzle proves to be popular, Nikoli spins it off and publishes it in a separate magazine. The combination of this system (combined with an ever-increasing corps of amateur puzzle constructors armed with computers) has worked wonders. It's the right system, at the right time.

The closest thing we have in this country is Games magazine, which I've contributed to a few times, but Games, a shadow of its former self, when it was edited by Will Shortz, is no "Puzzle Communication Nikoli".

A good way to sample some of Nikoli's offerings, aside from Nikoli's website, is with Simon Tatham's portable puzzle collection, which features a number of Nikoli puzzles (and Nikoli-like puzzles).

When I start writing the program to construct some kind of puzzle, I usually have a pretty good idea how to solve the puzzle, and I already have a sample or two, but I don't have much of an idea of how to create the puzzle. I start with what I know I can do - by writing a program that can solve the puzzle, using text as input. To my program that solves Sudoku puzzles, a sudoku puzzle looks like this:

{"title of puzzle", 9, 3, 3, "..52.13....786..9129...78...8.1.2.3.92.....76.7.6.9.8...89...2363..584....94.36.."}

The periods indicate the squares that are unknown, and the numbers are the clues. It is the solver's job to replace those periods with numbers.

I've written two main kinds of solvers: "logic" solvers and "backtracking" solvers. The "logic" solver works somewhat similarly to the way I work myself when I solve a puzzle. It tries out a series of strategems on the puzzle, one after another, from easiest to hardest. For example, when I solve a Slitherlink, I might do the following:

1. Look for two cells that both contain a 3 and are adjacent. For those squares, there are three lines that can always be filled in, and some lines that can be eliminated.
2. Look for a 3 which is next to a zero. If so, there are three lines that can be filled in.
3. Look for two 3s which are diagonally adjacent, for those squares there are four lines that can be filled in. and so on...

Whenever a particular strategem results in some minor success - filling in a line, or ruling out a line, I start over again from step 1 (the easiest strategy). If, after running through all my strategies, the puzzle is not yet solved, then I can't solve the puzzle.

The second type of solver I've written is the "brute force" solver with backtracking. This kind of solver will make a series of guesses until it either solves the puzzle or runs into a mistake. If it runs into a mistake, it backtracks and guesses again. A human could do this, but it would be tedious and very easy to make mistakes. One of the solvers I use for Sudoku uses a special kind of backtracking algorithm developed by the master Donald Knuth called "Dancing Links". This is the fastest sudoku solver I have encountered.

Backtracking solvers can be significantly faster than the logic-strategy, and they can solve puzzles that humans would find impossible to solve by logic, so you can use them to create insanely hard puzzles, if you want to.

For the purposes of puzzle construction, it can be useful to have a fast backtracking solver so you can solve a lot of puzzles quickly. This leads to the "sieve" method of puzzle construction. The basic idea is this.

1. Generate a random puzzle which may or may not be solvable.
2. Attempt to solve it. If there is a problem, go back to step 1.
3. Voila, you have a puzzle. Save it and make another.

A variation of the sieve method that I use a lot is the "clue reduction" method, which I've used for Sudoku, Slitherlink and many other puzzles:

1. Generate a random puzzle with the solution all filled in.
2. Attempt to solve it, if there is a problem go back to step 1.
3. Remove one of the clues.
4. Attempt to solve the puzzle, if it is still solvable, go back to step 3 (while there are still untested clues). If if is not solvable, put the clue back.

The order that clues are removed is important and affects how many clues are removed in total. In general, I prefer to remove as many clues as possible, so I may repeat this process a hundred times, randomizing the order each time, trying to find the smallest set of clues I can provide.

For the sieve method to work, the solver needs to be able to quickly solve the puzzle, and determine that there is one, and only one solution. If there is more than one solution, the solver shouldn't waste time finding them all - it should just abort, so the sieve algorithm can get on with the business of a generating a new puzzle to solve (or removing a different clue).

I still haven't explained how to do step 1 "Generate a random puzzle with the solution filled in...". For something like a sudoku, this might be as simple as filling a grid with random numbers. The problem with that technique is that the vast majority of the time, you are going to end up with an invalid puzzle that has repeating numbers where it shouldn't. So you have to check the grid as you generate each number, to make sure that the result is apparently valid.

What you really need is a fast algorithm that uses a few heuristics to insure that you have a pretty good chance of producing a valid puzzle. If the heuristics aren't very good, then you will waste a lot of time trying to solve invalid puzzles and you'll only spit out a valid puzzle once in a blue moon.

A technique used for generating a solved slitherlink puzzle (before clue removal) is a little bit like growing a crystal. You start with a seed square which is filled in, and then gradually connect squares to that, maintaining free clearance around each filament. This produces a network of filaments, which corresponds to the looping path in the answer, when it is finished. The algorithm is very similar to one I used back in the 80s for generating drawings that resemble ice crystals on a windshield.

Interestingly, I've noticed that as a human puzzle solver, there is one strategy available to me that is not available to the computer. Since I know the puzzle has already been found to have one, and only one solution, I know that if making a particular decision (such as marking a particular edge in Slitherlink) will result in two equally valid solutions that don't affect the rest of the puzzle, I can assume that candidate decision is invalid. When the computer is testing puzzles for validity, it can't use this "meta" technique.

I've used a number of computer languages to create puzzles. It's fairly common for me to start with Processing (p5) which a superset of the Java programming language with some programmer-friendly graphics routines. Processing enables me to prototype puzzles and see them graphical as the solver attempts to solve the puzzle, so it makes debugging the solving algorithm easier.

Another language I use frequently is Perl, which isn't very fast, but is a very expressive language which enables me to accomplish a lot with a very little code.

Once I have a puzzle construction algorithm working, in one of those languages, I will often port it to C++, so I can get it to run faster. With a C++ program, I can generate hundreds or even thousands of puzzles very quickly, saving them to a text file.

After the C++ program generates the text file, I use a Perl script to read the text file and render the graphics into the PDF files I put on my website. I use a Perl library called PDF::Rewrite for this purpose.

To generate puzzles quickly, you need a fast solver. But once you know a puzzle is solvable, you can run a slower "logic" solver on it so that you can gauge it's difficulty. As I described earlier, the solver tries a series of strategems, from easy to hard. By keeping track of which strategies are used, and how many steps it takes to solve a puzzle, I can grade the puzzle. The are a number of things which I know contribute to the difficulty of a puzzle.

1. The degree of difficulty of the strategems required to solve the puzzle. I can force the generation of easier puzzles by disallowing the more advanced strategems.
   
2. The variety of strategems required to solve the puzzle (a puzzle that requires 6 different strategems is harder than one that requires 2).
   
3. How early in the solving process a difficult strategem is required. If a difficult strategem is required earlier on, the puzzle is more difficult. I've noticed that the Sudoku puzzles featured in the Los Angeles times and other newspapers don't take this into account. A sudoku puzzle that requires a guess when the puzzle is nearly all filled up is much easier than one that requires a guess when the puzzle has barely been started.
   
4. The number of logical steps needed to solve the puzzle.

One thing that is certainly clear is that the value of individual puzzles is approaching zero. Puzzles have become a commodity. While a good crossword constructor can make a few hundred bucks selling a puzzle to the New York times, the same is certainly not true of Sudoku. This is one of the reasons why I do not sell the puzzles I produce, but instead choose to give them away (and run ads on the pages). If you attempt to sell puzzles that can be easily mass produced, there will always be someone else waiting in the wings willing to produce them more cheaply.

I do believe that computers could take a bigger role in puzzle design (just as I believe they can take a bigger role in other making creative decisions in other art forms). Looking at the rich variety of Nikoli puzzles that are available, you will begin to notice that similar constraints tend to reappear in different puzzle varieties. Constraints such as

"The number does not repeat"
"The line does not cross itself"
"The wall is connected"

...and so on. I think it may be possible to make an automated puzzle designer that pulls handfuls of these constraints and tries combining them to make a new kind of puzzle. Just as writing a program to produce puzzles is much harder than solving the puzzle it produces, writing this program to design a multitude of puzzles would be significantly harder than writing a program to make any one puzzle.

It would be the ultimate puzzle. Perhaps some day I'll give it a go.