Numbrix

Numbrix is a number puzzle. It appears in Parade magazine, a supplement to the Sunday paper in like most every city in the U.S. It was developed by "the smartest woman in the world", Marilyn Vos Savant. Solving the puzzle requires filling in all the blanks with consecutive numbers between one and 81. Consecutive numbers must be adjacent either horizontally or vertically, not diagonally.

I find it fairly easy to solve. It is so easy for me I have added my own personal restriction of not making any errors. That does not happen often. I usually make at least one error. (Just because this number puzzle is easy for me doesn't mean all number puzzles are easy. I don't play Sudoku because it is too much work.)

A couple of weeks ago I was thinking about writing a computer program to solve this kind of puzzle. I was wondering just how a program would go about finding a solution. When I work on one of these puzzles by hand, I use a variety of techniques, whatever seems to get me further along with the least amount of effort. Pick the low hanging fruit first, as the saying goes. Only after I have gotten all the easy numbers do I start working on the rest of the puzzle. Lacking any better ideas, I started writing my computer program by attempting a translation of my paper and pencil technique.

The first step I use: look in the corners, there are some empty squares that are in between two numbers whose difference is two. Only one number can go in those squares.

This looks like a fairly simple rule, but translating it into code took a couple of pages. You have the situation where the three squares in question are all in a row, or they are all in a column, or they form a right angle. Then there is the question of whether your potential three-in-a-row squares are even all on the board, or whether they lap over the edge. These are things that are obvious to anyone looking at the board, but computers are stupid. You have to spell out every little thing for them. I could have gone ahead and written code to cover all the cases, but it looked like it was going be a good deal of work. There ought to be a better way.

The "better way" did not jump out at me, so I turned my attention to the data structures. I had started with a simple two dimensional array, 9 x 9, to represent the playing field. After attempting to replicate my paper-and-pencil techniques, I decided what each cell in this grid needed was a list of pointers to the adjacent cells. This would make it simpler to decide whether there was an adjacent cell or not. We would not have to use four separate cases to determine if we were at the edge, we could simple check to see whether the pointer was valid or not.

I also decided I needed a new copy of board for each number I placed, that way when I came to a dead end, I could simply throw away the dead end copy, and go back to the previous version and try the same number in a different square.

I went on like this for a while. Changing the data structures, and then rewriting the code to make use of the new rules. But I still didn't have a program that would solve the puzzle. All these things I was working on were essential, but they weren't getting the job done. It's like a painter sanding and priming the surface, but not applying the finishing coat, or a cook measuring and chopping and otherwise preparing all the ingredients for a meal, but not putting anything on the stove. Near as I can tell, my problem was that I wasn't feeling up to snuff. I was tired and my brain was fuzzy. I could not get myself to think about the problem.

Saturday I finally came up with a solution. (C language source code here.) The fuzzies must have cleared out for a bit. I only had to think about it for maybe ten or fifteen minutes. I spent maybe an hour writing the code and testing it, and presto, it works! Once I got it working, I realized that I didn't need any of the fancy data structures I had devised, or any of the code that dealt with them, so I was able to cut whole sections of code out of the program. What I ended up with is less than 200 lines of code, and less than 4,000 characters. Shoot, this post so far is 3,000 characters.

I am not sure just how I figured it out. Partly it was just having the problem percolating in my mind, part of it was identifying the tests I needed to make, and part of it was reducing those tests to their absolute minimum. What I am wondering is whether this kind of thing can be taught, or whether there is a part of the mind that just puts this stuff together. I remember studying this stuff in school, and a lot of it was really opaque. Only by hammering on it for long periods of time was I able to sort it out and make sense of it. If I can't explain how I did it, how could I teach anyone else to do it, much less a computer?

The program is not very smart. It uses a couple of very simple rules:

• We scan the grid one square at a time, for each square we try to "solve" the puzzle starting with the number one.
• If the square is empty, and the number hasn't been used, or the square already contains the number, put the number in the square. Otherwise go back to previous step.
• Now try to "solve" the puzzle with the next number in one of the adjacent squares. Try each of the adjacent squares in turn.

The program arrives at a solution by running these rules into the ground. At first I was afraid this set of rules would not work. I mean we have 81 numbers to place, and for each place we have three directions we can go, which means we have like 3 to the power of 81 possible solutions, which is a ridiculously huge number and there would be no way that this program could ever come to an end. Since the program did find a solution, my seat-of-the-pants estimate is evidently way off.

Solving an "Easy" puzzle only takes about 40,000 steps. Solving an "Expert" puzzle takes about a million steps. But who cares? We are doing this on a computer that can do a zillion steps a second. It may take the program a second to solve the puzzle, but I suspect most of that second is involved in setting up the virtual machine to run the program, and translating the output characters into a picture that can be shown on the display.

Kicker: I sat down to do the Numbrix in Sunday's paper, by hand, just like I usually do, and I couldn't solve it! This has never happened before! I must be missing something. I take the Parade downstairs, enter the numbers in my program and run it. No solution here either! WTF? Go back upstairs. Copy the puzzle onto a blank sheet of paper and try again, being a little more careful. Still no solution. This is just bizarre. Finally I check the online version and find that the number in the upper left square is different. My program solves the online version, no problem.

Update: Here's a photo of the puzzle as printed in the paper. I think my mind must have slipped a couple of gears last week. As you can see, the given numbers are identical to the ones in the online puzzle shown at the top. I just completed it without any problem. I need to get more sleep.

Update #2: 

Explanation of recursive procedure follow used to solve Numbrix puzzles