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.