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.