Solving Any Sudoku Puzzle¶

The rules of Sudoku are simple and finite: fill in the empty squares so that each column, row, and 3x3 box contains all the digits from 1 to 9:

Puzzle	Solution

This notebook develops a program to solve any Sudoku puzzle, in about 100 lines of Python. You can also see:

• The original 2006 version of this notebook, as a raw HTML page:
  • It uses some outdated Python idioms; the Python code in this notebook is more modern.
  • Thus, if you read this notebook, you don't need to see the older version.
  • However, the disqus comments might be of some interest.
• A Java program for Sudoku that solves over 100,000 puzzles per second.
• A Python program for Star Battle, a related fill-in-the-grid puzzle game.

Sudoku: Implementing Basic Concepts¶

Here are the key concepts and the Python implementation choices I made:

• Digit: the digits are the characters '1' to '9'.
• Digit set: when several digits could fill a square, use '123' to mean 1, 2, or 3 are possible.
• Rows: by convention the 9 rows have labels 'A' to 'I' (top to bottom).
• Columns: by convention the 9 columns have labels '1' to '9' (left to right).
• Boxes: the 9 boxes are 3×3 squares within the grid (outlined with heavy black lines in the diagram).
• Square: a square is named by the concatenation of its row and column labels, e.g. 'A9' is the upper-rightmost square.
  • squares is a tuple of all 81 squares.
• Grid: a grid of 81 squares is represented as a dict of {Square: DigitSet} such as {'A9': '123', ...}.
  • Fail represents a grid that has no solution (e.g. if we guess wrong on the filler for some square).
• Picture: for input and output, a string picture of the grid is used (details described below).
• Unit: a unit is a row, column, or box; each unit is a list of 9 squares.
  • all_units is a tuple of all 27 units.
  • units[s] is a tuple of the 3 units that square s is a part of.
• Peers: the squares that share a unit are called peers.
  • peers[s] is a set of 20 squares that are in some unit with s.
• Solution: A grid is a valid solution to a puzzle if:
  • A square that was filled with a digit in the puzzle has the same digit in the solution.
  • Every unit is filled with all nine digits, one to a square, no repeats.

For example, here are the three units (and the 20 peers) for the square C2:

.  A2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         A1 A2 A3|.  .  . |.  .  .  
.  B2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         B1 B2 B3|.  .  . |.  .  .  
.  C2 . |.  .  . |.  .  .         C1 C2 C3|C4 C5 C6|C7 C8 C9        C1 C2 C3|.  .  . |.  .  .  
--------+--------+--------        --------+--------+--------        --------+--------+-------- 
.  D2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  
.  E2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  
.  F2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  
--------+--------+--------        --------+--------+--------        --------+--------+-------- 
.  G2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  
.  H2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  
.  I2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  . 

Roads not taken¶

I made my implementation choices for clarity and ease of debugging. There are alternative choices I could have made:

• Digit: could have been an int, but:
  • There is no need to do arithmetic on digits (all that matters is that they are unique).
  • I wanted the compact DigitSet representation.
• Digit set: I considered two other options:
  • set of digits: a good choice, but:
    • I would then need to do a deepcopy of each grid, not just a copy.
    • The printed representation '123' is shorter and easier to read than {'1', '2', '3'} when debugging.
  • int bitset: each digit is represented by a bit; a DigitSet is a 9-bit binary int.
    • Efficient, but obfuscating. Used in the Java version for efficiency.
• Grid: I considered three other options:
  • defaultdict: the default is the DigitSet '123456789'.
    • I thought that the top levels in the search tree would have only a few entries, so this would save space.
    • But the first round of constraint propagation touches almost all the squares anyway.
  • list of 9 rows, each a list of 9 squares (or a numpy 2D array):
    • Then a Square is a pair of coordinates, like (1, 2) rather than the simpler string C2.
    • Copying a grid would again require a deepcopy.
  • list of 81 squares:
    • Then a Square is an integer from 0 to 81.
    • Efficient, but for debugging it is clear that C2 is in the third row and second column; it is not obvious that 19 is.

Input and Output: Pictures and Grids¶

We will need to convert between a Picture (used for input/output) and a Grid (used for computation). Conventions for Picture:

• A filled square is represented by a single digit, e.g.: 5.
• A blank square is represented by a period: ..
• Spaces, newlines, and dashes/bars to separate boxes are included on output, and ignored on input.
• An uncertain square is represented by a DigitSet in braces, e.g.: {123}.
  • This '{123}' notation never occurs in a standard Sudoku puzzle, but it is what picture(grid) produces for a grid that is partially solved, so I thought it was important to be able to read that format back in with parse(picture).

Here we parse a picture string into a grid, and then print the grid's picture:

In a grid, filled squares have one possible digit, and unfilled squares have all 9 possible digits:

Constraint Propagation¶

Sudoku players know these two key strategies:

1. If a square has only one possible digit, then eliminate that digit from the square's peers.
2. If a unit has only one possible square that can hold a digit, then fill the square with the digit.

This suggests two functions:

1. eliminate(grid, s, d) to eliminate digit d as a possibility for square s
2. fill(grid, s, d) to fill square s with the digit d.

You might think that fill is the most fundamental operation, and that it could be implemented with grid[s] = d. But the code is simpler if we think of eliminate as the fundamental operation, and implement fill as "eliminate all the digits except for d from s." Both functions mutate the grid they are passed, and return the mutated grid if they can perform the operation, or return Fail if there is a contradiction.

We say that these two strategies constitute constraint propagation: "constraint" because they constrain what values can go in what squares, and "propagation" because a fill of one square can lead to eliminate in other squares, which can in turn cause a fill of yet another square, and so on.

Here is the code:

To see how this all works, let's look again at grid1:

Constraint propagation will at some point consider the square E5, in the center of the center box. It is in a row with the digits 4, 8, 3, 1, and in a column with the digits 7, 9, 6, 2, 1, 8. If according to strategy 1 we call eliminate(grid1, 'E5', d) for each of these digits, then we're left with only one possible digit, 5, for E5. Thus, we would next call eliminate(grid1, s2, '5') for each peer s2 of 'E5'. This would lead to the square three columns to the left, E2, only having one remaining possible digit, 2. Constraint propagation continues in this fashion.

The function constrain returns the result of initiating constraint propagation on a grid. So that the original puzzle is not mutated, we create a new constrained grid that initially has all possible digits for each square, but then is filled with the known digits from the original grid.

Many puzzles can be solved by constrain alone, for example:

But for other puzzles, constrain is not enough:

We see that some progress has been made: the original puzzle has 17 squares filled in, and after constraint propagation, 20 are filled in. But that leaves 61 squares to go. We could try to add additional constraint propagation strategies, but there are many strategies, each one complicates the code, and even if we implemented them all, we wouldn't be guaranteed they could solve any puzzle.

Search Strategy¶

We need a strategy that will search through all possibile solutions, systematically and efficiently, until the solution is found. (A well-formed Sudoku puzzle has exactly one solution).

A naive search can be slow. Consider a brute force search that tries every possible combination of digits. In the constrained grid2 above, A2 has 4 possibilities, {1679}, A3 has 5, {12679}, and if we keep going and multiply all the choices together, we get over 10³⁸ possibilities for the whole puzzle. Suppose we have a very efficient implementation that takes only ten CPU instructions to evaluate a position, and that we have access to next-generation computers with 1024–core CPUs running at 100 GHz, and let's say we could afford a million of them, and while we're shopping, let's also pick up a time machine and go back 13 billion years to the origin of the universe and start our program running. We can then estimate that we'd be almost 1% done with this one puzzle by now. Brute force is not the search you're looking for.

A smarter search strategy is to interleave constraint propagation and systematic guessing as follows:

• If the current grid contains a contradiction, don't try more combinations; return failure.
• If there are no unfilled squares in the puzzle, then stop and return the succesful solution.
• Otherwise choose some unfilled square, s.
• Guess that some digit d fills square s.
  • Call fill on s and d to initiate constraint propagation.
• Recursively search for a solution to the puzzle from there.
  • If the guess was right, we will get a solution.
  • If the guess was wrong, back up and guess a different digit.
  • Because we give up as soon as we get a contradiction, we examine far fewer possibilities than brute force search.

Here is the implementation:

There are two choices we have to make in implementing the search: variable ordering (which square do we try first?) and value ordering (which digit do we try first for the square?). For variable ordering, I used a common heuristic called minimum remaining values, which means that we choose a square with the minimum number of possible values. Why? Consider grid2 above. Suppose we chose B3 first. It has 7 possibilities, {1256789}, so we'd expect to guess wrong with probability 6/7. If instead we chose G2, which only has 2 possibilities, {89}, we'd expect to be wrong with probability only 1/2. Thus we choose the square with the fewest possibilities and the best chance of guessing right. For value ordering we won't do anything special; we'll consider the digits in numeric order.

Note we create a new copy of grid for each recursive call to search. This way each branch of the search tree is independent, and mutations to grid done by constraint propagation in one branch do not confuse other branches. When it is time to back up and try a different digit, we have the original unaltered grid ready to go.

We could call search directly, but I'll define the helper function solve(puzzles) to call constrain and then search on each puzzle, and then verify that the solution is correct with is_solution, and finally print the puzzle and the solution side by side:

We see that search is effective at solving the previously-unsolved grid2.

Computer scientists call this a depth-first search because it (recursively) considers all possible continuations from the grid with d in square s before it backs up and considers a different digit in s. Sudoku players call this the Nishio strategy, after professional puzzle player Tetsuya Nishio, although Nishio only applied it when there were just two remaining possibilities for a square. We can apply it with any number of possibilities; we can even find a solution for the completely empty puzzle where every square has 9 possibilities:

Verifying the Program¶

We had success in solving grid1, grid2, and empty, but we are left with some questions:

• Can the program solve any puzzle?
  • We'll test it on some more puzzles, taken from some files. The more we test, the more confidence we have.
  • Assuming no bugs, the program can solve any puzzle, but we haven't determined a bound on how long it would take.
• Are the components of the program correct?
  • We'll run some unit_tests. There should be more.
• How long does it take to solve a puzzle?
  • We'll do %time solve(puzzles).
  • For a more complete investigation of run times, see the Java version.

We can solve 10,000 puzzles, verifying that each solution is correct (but not printing them):

That took less than 3 milliseconds per puzzle, or over 350 puzzles per second. (The Java version does over 100,000 puzzles per second. It benefits from being able to run 20 threads in parallel, from using more efficient data structures, and from the Java JVM being more efficient than Python's bytecode interpreter.)

We can inspect the solutions for the ten allegedly hardest puzzles:

Why?¶

Why did I do this? As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect." Several people I know (including my wife) were victims of the attack, and I thought maybe this would demonstrate that they didn't need to spend any more time on Sudoku. It didn't work for my friends (although my wife has since independently kicked the habit without my help), but at least one stranger wrote and said this page worked for them, so I've made the world more productive. And perhaps along the way I've taught something about Python, constraint propagation, search, problem solving, and Sudoku.