Solving Sudokus

Solving Sudokus with a program is different than solving them by hand. You do not have to spend hours learning all the strategies used by humans. Since computers are fast, you can simply brute-force the solution. However, soon you realize that you require some optimization.

Basic Input

Sudoku is a game in which no number can be repeated in a cell within the same grid, row or column. This rule helps us to narrow the number of possible solutions significantly. Therefore, it is important to keep a record of values we can use in a cell. Let us imagine we would like to place a value X=5 in a cell in the 6th row in the 6th column in an empty Sudoku. All other cells are empty. The following example shows where we could place the value X in other cells in next steps. So ‘1’ represents cells where X could be placed or is already placed, and ‘0’ represents where X cannot be placed anymore.


111|110|111
111|110|111
111|110|111
-----------
111|000|111
111|000|111
000|001|000
-----------
111|110|111
111|110|111
111|110|111

We can assign values, and query if we can use a value for a cell by using the Sudoku class functions. We can also mark a value as not valid for a cell.

Solvers

The first thing that comes to mind when solving a Sudoku with a computer is to try every possible value for each cell until you solve a puzzle. It is the easiest approach. It is just a few lines of code, and you get a result eventually (given you have an eternity to get there). In my Sudoku library, the SudokuDeterministicSolver class does just that, and it works on a lot of puzzles. However, sooner or later you find a puzzle that takes a long time to be solved. Even some of the test Sudokus I have made available take a rather long time to be solved with this approach. That is why it was necessary to do things differently.

In the SudokuPossibilityBasedSolver class, I first check how many values are valid candidates for each cell. I start with the cells that have the least number of possible candidates. Once I have used up all the possibilities for a cell, I return zero to indicate that the combination of tested values cannot produce a solution. This works much faster because since I am trying the cells with less possible values first, it is more probable I fail or succeed sooner. I am not the first one to use this approach, and I would like to recommend Peter Norvig’s article on solving Sudokus. The author goes into much more detail and demonstrates in numbers how this method performs.

Finally, I wrote a SudokuHumanSolver class. It uses some basic methods used by humans to solve Sudokus. I have included a search for unsolved values that have only one possible position in a grid, row, or column. I have also implemented the locked candidates method for grids, rows, and columns. Lastly, I made an attempt at X Wing and Skyscraper solving methods.

Solving Speed

I have tested the SudokuPossibilityBasedSolver on the hard and hardest sudokus from Peter Norvig’s website and repeated the experiment ten times. I think the big difference in results is due to the difference in hardware. However, the results show that this approach is valid.

After that I have tested each of the solvers on the easy sudokus generated by my library:

It becomes very apparent how much slower the deterministic solver performs.

Library

Feel free to check out my code on github.

Leave a Reply

Your email address will not be published. Required fields are marked *