Sudoku

Path: physics insights > misc >

Sudoku

Puzzle 1

Before we begin, here's one to try your luck on while you're reading the page.
Maybe you can solve it by the time you get to the bottom of this page (if you read slowly enough)!

(Sorry, no slick user interface here; to conveniently work on this, you'll need to print it and use a pencil. Click on it to view the image, which is a little more printer-friendly than printing the whole page.)

The solution (yes, it has a solution!), along with notes on some features of the puzzle, is given at the bottom of this page.

On this page, I'm going to say a few things about solving Sudoku puzzles, and give some examples which I think are interesting. I'll also include a couple of Perl scripts for creating and solving them (they have minimal user interfaces, but then, you get what you pay for -- they're free).

(If you want to skip all the blah-blah and go straight to some puzzles, you should probably head over to the Sudoku Examples page.)

Terminology

I'm going to call the five things we need to worry about boards, cells, boxes, rows, and columns on this page.

The cells are the things you put numbers in.

The "boxes" are the nine 3x3 subarrays of the board.

If I slip up and call something a square, I'll usually mean a "cell".

Sudoku and Me

I've spent far too much time fiddling with sudoku puzzles since I first looked at one a few years ago. Not too surprisingly, that first puzzle left me completely at a loss as to how to proceed. So, of course, I wrote a program to solve it.

That first Perl script worked by guessing a value, one cell at at time, and backtracking when it got to a point with no legal guesses. It worked but it was horribly slow.

Of course, I eventually figured out that one can annotate the cells with the possible values, and fill in any which have just one possible value, and then update the annotations, and so on and so forth until the board's done. And I learned some things. Mostly what I learned is that I made a lot of mistakes. There were two kinds of errors I committed over and over again:

I messed up maintaining the annotations. Typically I'd forget to update something when I filled in a final value, and then they'd be out of date, with some cells showing values on their lists which weren't actually legal. Occasionally, though, I'd also be too clever and I'd eliminate a possibility that couldn't really be eliminated, and then some cells would be missing values from their lists. Either way, the result was not good.
I frequently would overlook numbers that were sitting right in front of me. So, for instance, I'd fill in a "2" in one of the boxes right next to a cell which already contained a "2".
It appeared that, if I was thinking about the penciled in numbers, which are kind of gray, I would simply not see the printed numbers, which are black. In other words, the written numbers and the printed numbers were different colors, and I could only concentrate on one or the other at one time. I dunno why this happens, maybe I'm slightly dyslexic, but whatever the reason I made this sort of mistake over and over and it was really annoying.

So, to eliminate these little problems, I stopped annotating (no more annotation errors!) and I switched from a pencil to a black pen (same color as the printer's ink). Much better!

Of course, there were some drawbacks to my new way of doing things. Without annotations, it definitely takes longer to do the puzzles (except when I would have messed up the annotations, of course). (And, as I learned when doing these pages, I can't do some puzzles without annotation -- there comes a point where I get stuck. So, I would correct this to say I do most puzzles without annotating...)

And when I make a mistake with a pen, I need to catch it right away; otherwise, if I've filled in more than a few cells wrong, the puzzle's a total loss. So I try not to make mistakes. (Hah hah.)

A Digression: How I Solve Them

Before I get to the point of this page (assuming it has one), I'm going to take a moment to explain my own approach to these puzzles. I figure at least a few people reading that I do them without annotations and never erase may have wondered a bit at what I actually do. Please note that I'm not suggesting anyone else take this approach; it's not especially efficient, and you'll certainly never win any sudoku speed solving contests with it.

I use negative constraints as much as I can, and I use a visual approach to filling in values. I start by working with the boxes, and only look at rows and columns after I've mostly run out of box-based operations.

I'm sure that all meant nothing to anyone reading it, so I'll draw it, and work through several moves on an example board. Suppose we have a puzzle that looks like this (click on the image to get something printable):

I would start this by first working with 1, and then iterating up through all nine possible values.

For each value, I move (my eyes) around the board, looking at each instance of that value in turn. I then mentally cross out the row and column in which that cell resides, along with the row and column of any other cell which contains the same value, and see if that gets me anywhere. If it does, I fill in a value, and continue on.

Usually, to help with the visualization, I run the back end of the pen along the rows and columns to (invisibly) "cross out" the affected rows and columns. (And sometimes I use the business end of the pen by mistake, and then I make a mess...)

Looking over the above board, I don't get any joy from the 1's, nor the 2's, nor the 3's (and I'm beginning to wonder why I chose this board for my example). Finally, with the 4's, I see something useful:

The cell with the green circle must be a 4. So we fill that in, and continue on up through 9.

(By the way, if you try this step with Puzzle 1, at the top of the page, you won't find any values you can fill in this way.)

And that's all I see on this pass. So we need to look a little harder. (In fact, I'd actually do a more complex search to start with; I'm breaking what I do down into smaller steps to make the process -- ahem -- slightly less murky.)

We look at each of the numbers again, but this time we're going to pay some attention to what's going on in nearby cells. 1 doesn't get us anywhere, but with 2 we see something. The 2 in the upper right box blocks one cell in the lower right box, which means one of two cells in the top row of that box must be a 2 (green oval):

We don't know which cell outlined in green has the 2, but we know one of them does, and we can (mentally) cross out the row containing them.

We extend the "cross out" across the board to the left, and then we "cross out" the column containing the 2 in the upper left box. In the lower left box, we see that the purple oval must consequently contain a 2. Unfortunately, this doesn't actually get us anywhere, since the oval spans two cells, but it illustrates the technique. (By the way, this technique won't help with Puzzle 1, at the top of the page.)

At this point we've gone about as far as we can go with "negative constraints" and we need to look at the positive constraints: We need to pay some attention to the rule that every digit must be present in every row, column, and box.

We'll start with the lower right box. (We happened to be looking in its direction already, and it only has three blank cells, which is a manageable number; there's no deeper reason for starting there.) It contains the values 1, 4, 5, 6, 7, and 9, so it's missing 2, 3, and 8. Let's see where they can go.

We see a 2 in the upper right box and an 8 in the lower left box which have some effect on the lower right box. Let's draw their "cross-out" lines, pink for the 2, and blue for the 8:

The 2 and the 8 are both restricted to the blue oval in the lower right box. So, the cell with the green circle in it must contain a 3, since it can't be a 2 or 8, and there are no other values missing from the lower right box.

The top two corner boxes don't have anything interesting for us at this time, and the center box, which is surrounded by empty boxes, can't be solved until we've got something filled in in one of the side boxes. So let's look at the lower left box.

The lower left box is missing four values: 2, 6, 7, and 9. Glancing around the board, we see that 7 and 9 both appear in the bottom row. Crossing that out (shown in pink), we see the following:

7 and 9 are restricted to the squares under the green oval in the lower left box.

So, the two empty cells in the bottom row of the lower left box must contain 2 and 6. We've also crossed out (in blue) the column containing a 2 in the upper left corner. From that, we can see that the missing 2 must go in the cell with the blue circle in it, and that leaves only the lower left corner cell for the 6.

(By the way, this technique, also, will not help with Puzzle 1.)

That's about as far as we can go working with the boxes, so let's look at a row. The bottom row has just 3 blanks in it, so let's see if we can make any progress there.

It's missing the values 1, 4, and 8. We've crossed out the column which contains 1 and 8 (in pink):

1 and 8 must both go into the cells marked with the green circles. That leaves only the center cell for the missing 4.

We're now in a position to go back to using simple "crossing out" by itself to make some more progress.

If we cross out the two columns containing 4s in the center box, and cross out the two rows containing 4s in the top left and right boxes, we see:

And the only place a 4 can go in the upper middle box is the cell with the green circle.

I think this is sufficient to give a pretty clear picture of how I go about solving puzzles without annotations. Continuing the same way, it's possible to solve this puzzle completely, as you can see here (I diverged from my usual black pen, and switched to a blue pen for the additional values which I filled after the 4 in the upper middle box).

As I said to start with, it's slower to do it this way -- annotations allow you to make the same deductions without the need to visually rescan the board each time. But, as I also said, this way I never mess up the annotations (and I find it more fun to do it this way).

(Finally, I should mention that none of the techniques I've described so far will help in the least with solving Puzzle 1, at the top of the page.)

Some Tools

To build, analyze, and solve sudoku puzzles, I've been using a collection of Perl scripts, which are located here. See the file README.txt for a brief description of what each of them is for.

In case you're worried about corruption and viruses, the md5sums for the scripts are given here. The originals are stored on a Linux system in back of a firewall, and contain only the code I wrote [inspected visually]. (In any case, I've never heard of a virus being injected into a Perl script on a Unix system.)

The Solver Script, and Solver Levels

N.B. -- Since writing the first draft of this page, I renumbered my "solver levels" to split level 4, thus leading to six total levels, rather than five. There may still be a few places where I refer to the former 5-level scheme. If so, sorry for the confusion!

The Perl script I use to analyze (and solve) sudokus is given here.

The solver script reads a text file which contains the board to be solved. The format is simple: there's one line per row, and the values are delimited by blanks. Once it's read the board, it tries to solve it; it proceeds exactly the way a human would do it. If you want it to analyze a board which you subsequently plan to solve by hand, pass it the argument -no_show; it will still print a rating and some additional information about the board, but won't print the solution. (If you just want to know how difficult a board is, use the script score_puzzle, which runs the solver and digests the output to produce just the difficulty information.)

Solving is done by determining the permissible values for each empty cell, and then operating on the permissible value sets. (In other words, it annotates the board and looks for cells that have just one value on their list.) It runs up to 5 passes over the board, using progressively more complex operations. After each pass, it checks to see if it's filled all cells on the board; if it has, then it's done.

The difficulty level of a puzzle, typically indicated by a number of stars, is a rather mushy concept. What, exactly, makes a puzzle hard to do? The number of empty squares, the number of squares you can fill in easily to start with, the lengths of the possibility lists you'll need to deal with -- a number of things affect it. It's obvious, after looking at puzzles from several different companies, that everybody who sets out to rate boards does it a little differently.

The solver script discussed here provides an alternative, much clearer way of rating a board. The solver level of the puzzle is the number of passes it took the solver program to solve it. Since each pass uses more sophisticated techniques, this is a direct measure of how clever you need to be to solve the puzzle. (Unfortunately this doesn't correspond all that well with how "hard" a puzzle seems to be, which is probably why everybody who makes these things comes up with some other way of assigning stars.)

When the solver script runs, it keeps a work queue of rows, columns, and boxes to be processed; before each pass, all rows, columns, and boxes are pushed onto the queue. (Unlike a human, the program never forgets to update the annotations on affected cells when it fills one in!) Here are the passes that it runs, with each pass being used only if the previous passes failed to generate a solution:

Negative constraints -- no two cells in a row, column, or box can contain the same value:
On the first pass, permissible values for a cell are determined by eliminating all values which occur in the same row, column, or box as that cell. (We could call this using negative constraints. In fact, I guess I just did call it that in the header to this paragraph.) Any cell which has just one permissible value is filled in.
Each time a cell is filled in, the row, column, and box containing the cell are pushed onto the work queue for reprocessing, to see if any further changes need to be made. Objects are popped from the work queue and processed until the queue is finally empty.

A "level 1" Sudoku is one which the solver has completed when it gets to the end of pass 1.
(When the solver was given Puzzle 1, it filled in zero squares on pass 1.)
Positive constraints -- Every value must be represented in each row, column, and box:
On the second pass, we again iterate over all objects (rows, columns, and boxes) which are in the work queue. Permissible values for each cell are determined as in pass 1, and then we count the number of cells which can have each value in the object. If there is just one cell that can have some value in the object we're working on, we fill in that cell, and push the row, column, and box containing the cell back onto the work queue.
As in pass 1, objects are popped from the work queue and processed until the queue is empty.
(A human being would do this at the same time as the operations in bullet (1); only a computer program could be dumb enough to use two whole separate passes for these operations.)

A "level 2" Sudoku is one which the program can solve in its first two passes. A human can solve a level 2 puzzle just by determining the possibilities for each cell based on values in cells in the same row, column, and box, filling in any cells with just one possibility, and then updating the remaining possibilities.
Most puzzles which I've analyzed in daily papers were solver level 2.

(When the solver was given Puzzle 1, it could fill in no squares at all in the first two passes. So, Puzzle 1 is not a level 2 Sudoku.)

Multiset checks:
On the third pass, we add some intelligent processing of the possibilities.
We look for groups of cells within a single object which have the same possibility sets.
Thus, if there are three blank cells in a particular box (or row or column), we'll look for any pair of cells in that box which have the same two possibilities. If we find such a pair, then we know they must actually have those values, and the remaining cell in the box must have the third value.
For example, suppose a row has three blank cells, shown as a, b, c:

Furthermore, suppose the possibilities for the three blanks are a={1,2}, b={1,2}, and c={1,2,3}.
Then we know that the first two cells must contain the values 1 and 2 (in one order or the other), so the third cell must contain a 3:

(This example is pretty lame. c was the only cell which had 3 for a possibility, so you didn't need to go through all this rigamarole to get to the conclusion that it should be 3. A more interesting example requires at least 5 cells to be free in the row; as soon as I have time I plan to provide such an example.)

More generally, if there are k cells in an object which have identical possibility lists, with just k possibilities, then no other cells in the object can have any of those values. For example, suppose there are 4 blank cells in a row, labeled a,b,c,d:

Let's assume the possibilities for the blank cells are a={1,2}, b={1,2}, c={1,2,3,4}, and d={2,3,4}.
Then we know the first two must take on values 1 and 2, so we can prune the possibility lists for the other cells. The pruned possibility lists for those four cells will be a={1,2}, b={1,2}, c={3,4}, d={3,4}.

In addition, during pass 3 the solver looks for cases where k cells have identical possibility lists with more than k entries, but there are k possibilities which only occur in those cells. In that case, the possibility lists for the cells in question can be reduced to just the shared values. For example, suppose we have five cells in a row, with possibilities a={1,2,3}, b={1,2,3}, c={3,4,5}, d={4,5}, e={4,5}.

Cells a and b share the values {1,2}, and those appear in no other cells in the row, so we can prune the lists of possibilities to produce a={1,2,}, b={1,2,}, c={3,4,5}, d={4,5}, e={4,5}. The new pruned list has 3 appearing only on the list for cell c, so we can fill it in, leaving us:

with remaining possibilities a={1,2}, b={1,2}, d={4,5}, e={4,5}.

The program actually considers sets of up to 8 cells, which is too many for a human to conveniently handle. However, in commercial sudokus I don't think I've ever seen a case where more than 3 cells had common values and could be handled this way.

A "level 3" Sudoku is one which the program can solve in three passes.
Every puzzle (but one) which I've analyzed from a newspaper was level 1, 2, or 3.

(When the solver was given Puzzle 1, it could fill in no squares at all in the first three passes. So, Puzzle 1 is not a level 3 Sudoku.)

Esoteric checks, part 1:
On the fourth pass we do yet more pruning of the possibility lists. This is a little more complex.

In a row or column, we may find that a particular value is limited to the possibility lists for the cells contained in a single square. In that case, we can eliminate that value from all other possibility lists for other cells in the square.
Similarly, if we find a square in which a particular value is limited to cells in one row or column, we can eliminate that value from the possibility lists of all the other cells in that row or column.

This is actually a very natural operation when a human being is working on a sudoku, and you may do this without even thinking about it. None the less, I have never seen a daily paper sudoku which required a move of this sort.

A "level 4" Sudoku is one which can be solved in four passes.
I have never seen a level 4 Sudoku in a newspaper. I have seen them, quite recently, in puzzle books. They were marked "Very challenging" or "Warning -- Very hard".

(When Puzzle 1 was given to the solver, it failed to fill in any cells in the first four passes. Therefore, Puzzle 1 is not a level 4 Sudoku.)

Esoteric checks, part 2:
On the fifth pass we redo the checks from pass 3, only this time we relax the requirement that all possibility lists involved be identical.
These may seem simpler than the level 4 check, but in practice, they're harder to do, and among randomly produced boards, level 5 puzzles seem to be rarer than level 4 puzzles.

a) We repeat the first multiset checks, for k cells which can contain only k values, but we don't require that all possibility lists match. Instead, we take the union of the possibility lists in each set of cells, and if the number of possibilities in the united lists is equal to the number of cells in the set, then each of the values on the united possibility list must appear in those cells, and no others. An example may clarify this. Let's once again look at a row with four blank cells:

Let's assume the possibilities for the blank cells are a={1,2}, b={2,3}, c={1,3}, and d={1,2,3,4}. Then cells a, b, and c together have possibilities {1,2,3}, and so each of the values {1,2,3} must appear in one of those three cells. Therefore we'll prune the list for cell d, removing {1,2,3} from it; that leaves only {4}, so we can fill it in:

b) We repeat the second multiset check, but again we relax the requirement that the possibility sets are identical in all cells in the subset we're looking at. I'll just give one example. Let's assume we have a row with six blanks, with possibilities a={1,4}, b={2,3,5}, c={1,2,3,4,5}, d={4,5,6}, e={4,5}, f={5,6}.

The values {1,2,3} appear only on the lists for cells a, b, and c. So, those cells must actually contain those values, and no others; we can prune off all other values from the possibility lists for those cells, to obtain a={1}, b={2,3}, c={1,3}, d={4,5,6}, e={4,5}, f={5,6}.
We've reduced a to just one value, which we can fill in, and eliminate from the possibility lists from the other cells in the row. That, in turn, reduces c to just one value, which, when filled in, reduces b to just one value, bringing us to:

In fact, case (b) is just case (a) inverted, and doesn't add any additional power to what we're doing.

These situations can be hard to recognize, even with annotations. Without annotations I can't come close to solving most level 5 boards.

A "level 5" Sudoku is one which can be solved in five passes.
I have never knowingly seen a commercial level 5 Sudoku, from any source.

(When Puzzle 1 was given to the solver, it failed to fill in any cells in the first four passes. Therefore, Puzzle 1 is not a level 5 Sudoku.)

This brings us to the end of the "natural" techniques I'm aware of for reducing the possibility lists. If I've overlooked something, please don't just snicker behind your hands -- email me!

Total lose: Guess and backtrack
When all else fails, the solver selects a cell with the smallest number of possibilities (at least 2, of course), and picks a value arbitrarily to fill in. It then proceeds normally with the rest of the puzzle, until it either solves it or jams.
If it jams (can't proceed) then that was the wrong guess, and it backs up and tries the next possibility for that cell.
If it solves it, it backs up anyway, and tries the next possibility, just to see if the puzzle has more than one solution. Note that if we solve it using "natural" techniques, in passes 1 through 5, we know there can be no second solution, because the only possibilities were the ones we filled in. With the guess-and-backtrack solver, that's no longer true, so we must check explicitly.
It's possible for the backtracking solver to encounter a second situation where the natural solver can't proceed. In that case, it takes a (recursive) second guess, fills in a second cell, and keeps going.

A "level 6" Sudoku is one which, as far as I know, can't be solved without guessing.

An Example Worked Through All Five Levels

Well I was planning on writing this section, but this is all taking way too long. I plan to get to it but it's going to be a while yet.

Here's our example board, with the fetching name Board A1-c:

It's worth taking a moment to admire it. It doesn't look like much -- not symmetric, no blank rows or columns, no entirely missing values, nothing especially "cute" about it -- but it's the end result of running the board builder through about 5,000 boards under control of a driver script, looking for that one special board. It has the remarkable property that there are cells which can be filled in on (nearly) every pass of the solver, and so it is an ideal example board. (I wouldn't recommend trying to do it by hand, however, for reasons we'll see a little later.)

And I'll fill in the rest of this section just any day now!

Imagine My Surprise

I said above that every Sudoku (but one) which I've seen (and analyzed) from a newspaper was level 1, 2, or 3.

A few months ago, I would have said that was true of all the Sudokus I'd seen (save for my own creations).

A couple years ago, someone gave me a book of Sudoku puzzles from Kappa (volume 21, as it happens). They were rated with from 1 to 4 stars. The 1-star puzzles (at the beginning of the book) were really easy, so I tried the 4-star puzzles (at the back of the book). All of them which I tried were very easy, also, and I put the book aside.

A couple months back, for no particular reason, I took it down off the book case and started doing the 4-star puzzles. As I said, they all seemed quite easy -- until I got stuck on #95. That sometimes happens to me (comes from doing them without notes, or so I claim, anyway); normally it just means I've overlooked something. I put it aside, and looked at it again the next day.

Still stuck.

And the next day: still stuck. At that point, I went over the puzzle with a fine tooth comb, checking everything carefully, paying close attention to what I was doing. I even annotated it:

Still stuck.

So, I dusted off my old solver script, which I hadn't run in years, and fed it puzzle 95. (And that was what got me to thinking again about finally writing this page, by the way.)

It's a level 6. And it's in among a bunch of level 2 so-called "4-star" puzzles; there's no hint in the text that there's a wolf in there among the sheep.

A bug in Kappa's software? I don't know. (All sudokus are created by computer, of course -- hand building one would be well nigh impossible.) I went through their remaining 4-star puzzles which I hadn't yet done, feeding them all to the solver (with the -no_show argument, just to get the ratings). Five of the 27 "4-star" puzzles in the book were level 6; a couple were level 3; the rest were easy level 2 puzzles. Some major inconsistency there!

Since, as far as I know, a level 6 puzzle is essentially unsolvable, save by machine (unless you have the patience to use guess-and-backtrack techniques manually) this seems pretty tacky to me, but maybe people get a kick out of hitting an occasional "impossible" puzzle. Maybe it increases the satisfaction of solving the easier ones which surround them.

Yet More Surprise

I get daily-paper puzzles from Dave Green (Conceptus puzzles), in the Ottawa Citizen, and I get them from Fabian Savary, in Devoir. I used to see them in the Boston Globe (a long time ago). I also occasionally do puzzles from Yan Georget, which appear in LeMonde, when I feel moved to print them out (I just get it the online version of that paper).

The puzzles in the papers are all, in general, pretty easy; I never am (quite) forced to annotate them in the course of solving them. So, imagine my surprise when I printed out a puzzle from Le Monde and got stuck trying to solve it. Here it is, at the point where I got stuck:

You guessed it -- it is a level 6.

Mistake?

I don't know. It was rated "Expert", after all. But again, this seems pretty tacky to me; it's such a huge jump in difficulty from their usual "Expert" puzzles that it is, essentially, unsolvable.

The Puzzle Generator Script

The Perl script I used to create the puzzles on these pages is given here.

It has a large number of arguments, with a very primitive interface, and its output is simple text. See the README.txt file in the scripts directory, and check the argument list in the script for detailed information. I may eventually write more about it. In the mean time, if you don't know Perl you may not want to bother with it.

If you do use it, and its sister script, build_sudoku_to_spec, you will probably want to run make_sudoku_board on the output to turn it into something which can be printed nicely.

Some Boards

See: Some Puzzle Examples. These are mostly level 4 or 5 boards, the like of which one doesn't see in the daily papers. There are just a few, but they're all hand tested, with comments on the results...

As promised, here are some comments on Puzzle 1, given at the top of the page.

If you tried to do it, you're probably already aware that there's something strange going on there. In fact, you might even suspect that it's broken, or a mistake, and you may be starting to doubt that there's a solution to it at all.

Well, let me reassure you; the puzzle isn't broken, and there's no error in it. It has a solution, and what's more it has just one (in other words, it's fully determined, like any good Sudoku puzzle). So, here's the solution, along with some notes from the solver output when run on that puzzle.

And in case you're wondering, I certainly did not solve that one by hand. I gave it a whirl when I put this page together, but it's ... well ... strornry hard, as Christopher Robin might have expressed it.

If you solve it (by hand) please email me (the webmaster), and let me know how you went about it!

Page created on 5 March 2013, and last updated on 28 April 2013