## Sudoku and Exact Cover problems

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.

## Updating my AWS Lambda Sudoku Solver to generate new puzzles (part 1)

Having spent some time in the past building an implementation of Donald Knuth’s Algorithm X in Java to solve Sudoku Puzzles, I recently wondered what it would take to modify it to generate new puzzles.

If you missed my previous posts on this investigation, see:

It turns out having a working solver is part of the way there to implementing a puzzle generator, because you need to be able to check if a puzzle has a single solution, since valid puzzles only have 1 solution.

When I last wrapped my Solver as an AWS Lambda, I had taken the naive approach to call System.exit() in my Solver code if I detected there was more than 1 solution as a quick way to exit and not get stuck in a loop iterating over finding possible thousands of solutions for a grid that’s not a valid puzzle.

I went back and took another look at this and reworked it so I could pass an upper limit for number of puzzles, and changed the return type to return a List of solutions, and a flag indicating if there was a single solution or not. Latest commits on my repo have these changes, and I’m now ready to move on to building the puzzle generator. More updates coming soon.