2013-10-23: Solving Sudoku in Racket

The other week I was teaching my aging father-in-law about Sudoku and I needed to explain to him the rules and what techniques I use when I solve one. I like to avoid search as much as possible, because I think it is inhumane. In this post, I encode my technique as a Racket program that avoids search as much as possible.

-

I assume that you know what Sudoku is, but if you don’t. You are solving a graph coloring completion problem where the graph is always the same but the initial coloring varies from game to game. Here is an example board in ASCII art:

This example comes from the Wikipedia page. My first task is implementing the solver was to turn this into a data-structure. I decided to represent the board as a homogeneous list of cells, rather than the actual graph, because I was lazy and wanted to use a data-structure that was amenable to pure functional programming. Each cell stores its X and Y position, plus a set of the available choices for its value. For example, blank cells in the input can be anything, but cells that can only be one thing are "solved".

The parsing of this list of strings into a list of cells is pretty boring and ugly code. I think this is a common experience: the nicer the format is for humans, the uglier the parser is. In general, that seems like a good trade.

The only cute thing in the parser is the way I use flatten and empty to ignore the vertical rules in the ASCII art. Normally, my performance sense would prevent me from writing code like that, but because I know the lists are small and the code is only run once, it’s not a big deal.

In order to help appreciate what the solver does, I wrote some code to visualize a sequence of grids into an animation. There’s nothing particularly interesting about it, so I will just put it here for you to skip over to the real interesting stuff of how I do the solving:

The key idea of the solver is to do naive propagation of constraints until it is impossible to move forward, at which point I devolve into searching. The core piece of this is a function to iterate a propagation function until it stops having an impact:

The function, f, will be repeatedly called starting with the object o. The function is expected to return a boolean to indicate if there was a "change". If there was, then the iteration continues. However, it is possible, during search, that propagation discovers an inconsistency, so the solution becomes "bad" and propagation should stop. For whatever reason, if the iteration stops, then a function is called with the last object.

It is easy in Sudoku to describe a bad solution: it’s one where a cell has no options for its value.

The function that will be iterated, however, is where the real interesting stuff happens. My personal technique of solving Sudokus is to pick a cell and then consider a few different situations. The most basic is, "What cells interfere with this one and prevent it from taking certain values?". Which cells are possibility interfering? From a graph perspective, it is the set of neighbors. In the world of Sudoku, it is cells that are in the same row, column, or box.

I actually find it easier to think about this from the dual perspective though: I look at a solved cell and remove possibilities from everything that it interferes with. I call the solved cell the "pivot". So, the next part of the solving algorithm looks for such pivots.

This function takes a function that tries out a pivot and receives a boolean indicating if a change happened, a new pivot value and a new list of objects. The idea here is that it goes through each cell looking for one where the propagation function can do something. What does this propagation function actually do? It’s now possible to talk about it.

The code has a pretty nice structure. We use an escape continuation to get an early return from one of three different techniques. If every technique fails, then we return the pivot and the rest of the cells unmodified with an indication there was no change.

The first technique is the one mentioned before. We only use it if the cell is solved, and if it is, we go through each of the cell’s neighbors and remove the solved cell’s values from their possibilities. If any set gets smaller, then we observed a change.

If you only use this technique, it works surprisingly well, but it fails on the example I showed before, <board1>. So, I had to deploy my next technique.

This technique looks a single set of neighbors (row, column, or box), which I inappropriately call a clique, and sees if the given cell is the only one that can take on a certain value. For instance, suppose a cell could be 3 and 4, but no other cell in its row could be 3, then the cell must be 3. In code, this means that if you take the cell’s possibilities and remove all the possibilities of everything else in one dimension of neighborness, then the set of possibilities is unit sized. This is easy to express in code:

This is all you need to solve the example from before and most Sudokus that WebSudoku categorizes as Easy and Medium. However, if we look at a Hard example, like the one below, then it will fail.

The next technique that I employ is when two cells in a clique both are limited to the same two possibilities, such as both being constrained to be 3 or 4. In this case, you can remove 3 and 4 from all other cell possibility sets in the clique. This is a bit more awkward to program, because there are two iterations of all the cells. You could do it in one, but I think it be more obtuse than is worth it.

Once this technique is in place, the aforementioned puzzle is solved. However, when I went to "Evil" puzzles, like the following one, I needed to use search.

The main impact of using searching is that we have to interleave the previous constraint propagation steps with arbitrarily picking the values of certain cells. I use a backtracking technique, where if after a fixed point is reached on the constraint solving, there are three possibilities. In one case, the puzzle is solved so we’re done and the rest of the trace is empty. In the next, the solution is bad and we need to backtrack. In the last case, we need to run search.

The search function that actually manages search will pick a cell and set it to solved and see if the rest of the puzzle can be solved using that choice. I think it is probably best to try cells that have fewer options, so first I sort them by their number of possibilities. Then, we try to find non-solved cell and set them to a particular answer and re-run the solver loop. If that stage of solving fails, then we backtrack, using an escape continuation, to the choice point and make another. If a given cell runs out of options, then we try a different cell, and if all cells fail, then we backtrack even earlier.

I think it is delightfully simple to do this backtracking because I was sure to use purely functional data-structures everywhere else in the solver. If I didn’t, then I would have to careful undo every change after the arbitrary choice, which would be complicated.

After I added this step, every puzzle I’ve given it is solved fairly quickly. I know that the NP-Completeness proof for generalized Sudoku is out there, so in the worst case this is the only stage of the algorithm that is really useful, but nevertheless, implementing the other kinds of reasoning for the solver was a lot of fun!

1 Yo! It’s almost time to go!

But first let’s remember what we learned today!

Parsing ASCII art is ugly.

Backtracking and purely functional data-structures are a match made in heaven.

Certain kinds of backtracking just needs escape continuations, which are cheaper than full continuations.

When n is 81, all exponentials are constant.

Finally, Sudoku is a boring game when you have to search.

If you’d like to run this exact code at home, you should put it in this order:

Or just download the raw version.