Category: Kev’s Blog

Sudoku is an example of an Exact Cover problem and can be solved by picking a subset of candidate rows from the exact cover matrix that satisfy all of the constraints for the complete grid.

I explored building an implementation of Donald Knuth’s Algorithm X using Dancing Links as a Sudoku solver, which you can read more about here.

For a 9×9 Sudoku puzzle, a candidate grid has x possible candidates, by y constraints.

For a 9×9 grid using numbers 1 through 9, there are:

9 rows x 9 columns x 9 (values 1 through 9) = 729

… possible candidate values for the cells.

For 4 constraints applied to every cell in the 9×9 grid, there are

9 rows x 9 columns x 4 constraints = 324

… constraints to be met.

If you fill a grid where a 1 represents a met constraint by that candidate and 0 is unmet, if you zoom out far enough the table looks like this:

To see how a matrix like this is used together with Donald Knuth’s Algorithm X and Dancing Links, see my previous post here.