Solving Any Sudoku Puzzle¶

The rules of Sudoku are simple and finite: fill in the empty squares in the puzzle so that each column, row, and 3×3 box contains all the digits from 1 to 9 with no repeats. For example:

Puzzle	-	Solution

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

• The original 2006 version of this program; it has some obsolete Python idioms.
• A Java program for Sudoku that is less clear but faster, solving over 100,000 puzzles per second.
• A Python program for Star Battle, a related fill-in-the-grid puzzle.
• A Python program for KenKen, a related fill-in-the-grid puzzle.

Sudoku: Implementing Basic Concepts¶

Here are the key concepts and the Python implementation choices I made. Types are in Uppercase and constants in lowercase:

• 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).
• 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', ...}.
• Boxes: the 9 boxes are 3×3 squares within the grid (outlined with heavy black lines in the diagram).
  • all_boxes is a list of all 9 boxes
• Unit: a unit is a row, column, or box; each unit is a tuple of 9 squares.
  • all_units is a list of all 27 units.
  • units is a dict such that 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 is a dict such that peers[s] is a set of 20 squares that are in some unit with s.
• None: If a puzzle has no solution, we represent that with None.
• Picture: for input and output, a string is used to describe the grid (details described below).
• Solution: A grid is a valid solution to a puzzle if every unit is filled with all nine digits, one to a square, with no repeats, and each square that was filled with a digit in the puzzle has the same digit in the solution.

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 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  . 

Constraint Propagation¶

Sudoku players know these two key strategies:

1. If a square has only one possible digit, then eliminate that digit as a possibility for each of 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 it turns out 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 None 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 an eliminate in other squares, which can in turn cause a fill of yet another square, and so on.

The function constrain starts the whole process off. We initialize a new grid, result, (so that the original puzzle is not mutated), where result is filled with the known digits from the original grid.

Here is the code:

Input and Output: Pictures and Grids¶

To show how constraint propagation works, we will need to read in a string representing a puzzle (what we call a Picture), convert that picture to a Grid, apply constraint propagation, convert the solution back to a picture, and display the picture. 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, but are optional (and ignored) on input.
• An uncertain square is represented by a DigitSet in braces, e.g.: {123}.

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

In a grid, filled squares (like A1, the upper left corner of grid1) have one possible digit, and unfilled squares (like A9, the upper right corner of grid1) have all 9 possible digits:

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.

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

But for other puzzles, constrain is not enough:

We see that some progress has been made: the grid2 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.

It is too slow to do constraint propagation first and then search. A smarter strategy is to interleave constraint propagation and search as follows:

• If a previous step of the search on this branch returned None, then pass the None along.
• If there are no squares with multiple possibilities in the puzzle, then return the completed grid.
• Otherwise choose one of the not-yet-determined squares, s.
• For each digit d that could possibly fill square s:
  • Initiate constraint propagation by calling fill on s and d and a copy of the grid.
  • 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, continue on to the next digit d.

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(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.
  • Theoretically, the program should be able to 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 to give us some confidence/ There should be more tests.
• How long does it take to solve a puzzle?
  • We can measure that with the %time magic command.
  • 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.)

The ten allegedly hardest puzzles also take about 3 milliseconds per puzzle on average:

We can see the puzzles and their solutions:

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.

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.