Naive Sudoku
Recently I helped my brother rewrite a sudoku solver he had been hacking on. His original implementation did some smart look-ahead to determine quickly which cells of the puzzle could be inferred from surrounding columns, rows, and regions. We were curious, though, to see how this would compare to a naive solver. Our naive solver can only decide what number to put in a cell based on its own row, column, and region (3x3 square).
The premise of our naive solver prohibits leveraging inference about a cell’s possible options beyond what can be inferred the rules of the game:
- Number can appear only once on each row
- Number can appear only once on each column
- Number can appear only once on each region
This means we cannot use look-ahead strategies like x-wing, which are popular methods implemented in other solvers. Again, our constraint is simply to understand and compare differences between sophisticated solvers and a certain form of brute-force solver.
The first piece of our solver is a class to hold the game board which is a 9x9 matrix of cells. The board has a validation function to determine if the board is valid according to the rules stated above. Each Cell object holds an array of values called ‘options’, which contains the possible options 1 through 9 for the eventual value of that cell. When a cell’s value is set, it removes that value from the option set of each cell in its row, column, and region. The solver works recursively, picking the cell with the least number of options and setting it’s value, and continuing to guess values until it either solves the puzzle or exhausts its options in a given possibility tree.
As we were designing the solver, my brother asked if we should take a shortcut
by analyzing the board to determine if there are any cells which are the only
cell in a row, column, and region containing a specific option. This means that
if a cell has the value 9 in its option set, for instance, and no other cell
in its row, column, or region has the option of 9, we can set that cell to 9.
This would be a really straightforward idea to implement, but eventually we
determined that it goes against the ethos of our naive solver experiment,
because it’s still a form of look-ahead.
Ultimately, the solver we designed only cares about board validity, not impossibility. Look-ahead allows a solver to predict dead-end possibility trees before testing them, whereas our solver has one optimization which is to choose the cell with the fewest options before it starts making guesses.
I haven’t created an exhaustive comparison between our solver and any other solvers, but on my 2014 Macbook Pro, our solver has completed any sudoku we’ve thrown at it in under 12 seconds.