Chris White's Homepage

Home

| Research |

Teaching |

Contact

Sudoku Solving via $\ell_{1}$-minimization

>> THE IDEA
>> THE SOLVER (direct link to the solver application here)

Sudoku is a very popular number puzzle where the goal is to fill in the given 9 x 9 grid with digits 1-9 subject to the following rules:

Every row must contain one and only one instance of each digit 1-9
Every column must contain one and only one instance of each digit 1-9
Each of the nine basic 3 x 3 squares must contain one and only one instance of each digit 1-9

Typically, solving a Sudoku puzzle involves a set of of complicated logical maneuvers.

Most computer-based Sudoku solvers program these logical constraints and do searches to fill in the initial grid. This typically works, but for harder puzzles this can take a long time. Here I will present a method for solving Sudoku puzzles that treats easy puzzles on an equal footing as the hardest Sudoku puzzle. The method uses some of the basic ideas from the mathematical field of Compressive Sensing. [NOTE: If you're interested in learning more please see the paper by Babu, Pelckmans, Stoica, and Jian available here.]

>> THE IDEA

Observe that a solved puzzle can be broken down into 9 different grids - each grid tells us the locations of a given digit (see the figure below - caveat: graphics aren't my thing).

A solved Sudoku broken down into "indicator grids"
What does it mean for this collection of 9 grids to satisfy the rules of Sudoku? Well, we can phrase the row constraint as follows:

For each "indicator" grid as in the figure, the entries in every row must sum to 1

Similarly, the column constraint requires:

For each "indicator" grid, the entries in every column must sum to 1

The square constraint should be obvious now:

For each "indicator" grid, the entries within each basic 3 x 3 square must sum to 1

You might think we are done with the constraints at this point, but you would be wrong! If we found a single grid which satisfies the above constraints and then duplicated it 9 times, we would still satisfy all the constraints -- but clearly this collection of grids does not correspond to a solved Sudoku puzzle! Because we have changed the formulation, we need to make explicit a constraint which was implicit in the first formulation, namely:

The locations of the 1's in each pair of indicator grids must be disjoint (i.e., distinct)

Now that we have modeled a filled in Sudoku puzzle, we take one last mathematical step: each grid can be thought of as a list of 0's and 1's, as long as we have an agreed upon procedure for reconstructing the list as a grid. Thus we will take each grid and expand it by row to get a vector of length 81. We now concatenate each vector to get a "solution" vector of length 81*9 = 729.

One last question remains in the basic setup: if we are given an intial set of values (like you get in the newspaper), how do we enforce that our solution vector agrees with the initial set of values? Answer: we take the partially filled in grid, and expand it into a vector of length 729 containing only 0's and 1's as described above. If $I$ is the vector obtained from the initial puzzle, and $x$ is the solution vector we are looking for, requiring $\langle I,x \rangle = \|I\|_{1}$ guarantees they will agree.

We have just described a set of conditions that can be succintly written as:

$\Sigma_{j=1}^{9} x_{ijk} = 1, \forall i,k = 1,2,...9$

$\Sigma_{i=1}^{9} x_{ijk} = 1, \forall j,k = 1,2,...9$

$\Sigma_{(i,j)\in\text{box}} x_{ijk} = 1, \forall k=1,...9$

$\Sigma_{k=1}^{9} x_{ijk} = 1, \forall i,j=1,...9$

$\langle x, I \rangle = \|I\|_{1}$

$x_{ijk}\in\{0,1\}$
where we intrepret $x_{ijk} = 1$ as indicating that digit $k$ is located in the $(i,j)$-th position in the Sudoku grid (the box constraints can be written more explicitly, but I'll leave that as an exercise for the reader).

Now, we have just described a problem with the following properties:

It is an underdetermined linear system (325 constraints vs. solution vector of length 729).
The solution vector is sparse (i.e., contains few non-zero entries)
The solution vector should consist entirely of 0's and 1's (integer entries)

Thus, using Compressive Sensing (read: $\ell_{1}$-minimization) to deal with the sparsity and a branch-and-bound Simplex algorithm to deal with the integrality, we arrive at an algorithm for solving Sudoku puzzles (more details at a future date).

>> THE SOLVER

The current web implementation of the solver can be found here. It was coded up quickly so I could put it online, so if you find any errors or bugs, please e-mail me at cwhite [at] math.utexas.edu. The formatting works best in Google Chrome or Safari - for some reason Firefox makes the puzzle rectangular. I am currently working on a Java version.