Sudoku Solver (Part 1) - Puzzle Solver and Generator
Overview
For my first task, I need to create a base library that understands the Sudoku game.
This library will allow you to create a board with the current state, solve a board, provide a hint, generate a puzzle of a given difficulty.
Once I have done those base operation, I will need to create a way to persist a board. I will use a flat file system, so I will need a serializer/de-serializer.
I also have discovered an awesome library of 9,000,000 sudoku puzzles and their solutions on Kaggle. It was well reviewed, so I will use that to benchmark my solver strategies.
I will slap some unit tests on the whole mess and then move on to the next phase.
Results
At this point, the solver was based on heuristics alone and no search or backtracking.
I was able to run the solver through the 9 million tests provided by a dataset on Kaggle.
The, roughly, 1.4GB file took about 8.8 seconds just to open and read each line. The first version of my code took an additional 807 seconds for my code to solve the puzzle set. Results summarized below, but there was definitely some clean-up work to do as I didn’t support backtracking. (2023-03-24)
Once I added support for backtracking in addition to heuristics (2023-03-27), the algorithm went from returning a single result to a collection of results. For the purposes of testing speed, I stop when I find one solution to the puzzle. In addition to testing if my solution is a valid solution, I also compared my solution with the solution provided by my test data, so it does appear all the puzzles in the Kaggle dataset only have a single solution.
| Version (Date) | Puzzles | Total(s) | Per Puzzle(μs) | Failures | Percentage |
|---|---|---|---|---|---|
| 2023-03-24 | 9mil | 807s | 89μs | 172,790 | 1.92% |
| 2023-03-27 | 9mil | 1176s | 131μs | 0 | 0.00% |
Obviously, I had to improve from only heuristics since almost 2% of the puzzles in the dataset were not solved by the code as written. The average time per puzzle increased by adding backtracking, since if a puzzle is not solved by heuristics, it was a more difficult puzzle and required deductive guessing + backtracking.
I can probably improve this more, but I am happy with that performance.
Review of how I designed the Puzzle
I noticed much of the sudoku solver content online uses a very straight-forward approach to solving sudoku. Each cell is of a 9 digits (or an designator for empty - like zero). There are three collections that track the used digits for the row, column, box.
Based on the choice of collection, this approach is based on a key lookup (i.e. is the digit N already in the set Row, Column, Box). You are going to make a choice to use a dictionary, or hashset or list, but whatever you choose, a typical puzzle will require that method to be call a significant amount of times.
I assumed this would be slower, without evidence, than using bit operations, I went for a more involved approach. I coded a naive backtracking method to performance compare with my method. I had to halt execution after 45 minutes of execution on a single puzzle (picked for its difficulty). This is not a fair comparison given I picked a very difficult puzzle and I’m certain I did not optimize the collection lookups carefully enough.
Since I don’t have a great alternative benchmark, I can’t conclude my approach is faster and therefore I must conclude that the code I wrote is unnecessarily complicated.
For this reason, Please don’t follow any of the advice I list below.
The way I designed my sudoku was to imagine each cell as a bit mask as follows:
| Digit | Bit Mask |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 8 |
| 5 | 16 |
| 6 | 32 |
| 7 | 64 |
| 8 | 128 |
| 9 | 256 |
Every cell has two properties:
- the value of the cell (if solved; otherwise, 0).
- the annotation of the cell (the intersection of all possible digit masks)
- if this value is zero, there is a contradition.
- if this value is equal to 512 (2 ^ 9), then the value of the cell will not be zero.
- if this value is exactly equal to a bit mask, then the cell should be considered solved.
- if this value is any other value, the disjunction of the annotation and any bitmask will be non-zero if and only if the digit represented by that bitmask is possible.
Also, the digit value is not stored in the cell (1), but rather the bitmask of the digit is stored. This allows easier bit operations when determing what values are possible and for updating annotations of linked cells.
As an example, if a cell has the value of 64, then that cell must have an annotation of 512 (indicated it is solved) and the digit of that solved cell would be 7.
As another example, if a cell has a value of 0, and an annotation of 96 (32 + 64), the cell would be unsolved and the digits 6 or 7 would be possible.
Using bit masks made it easy to set other rows, columns, boxes, and linked cells as masks propagate through the solution with the need for hashsets or dictionaries.
In addition, I have a few row, column, and box annotations to hold the possible values and links connecting each cell to whom it constraints. There are always 20 of these links - 8 row, 8 column, 4 box. (see figure).
// -------- -------- --------
// | 09 | |
// | 10 | |
// | 11 | |
// -------- -------- --------
// | 17 12 18 | |
// 01 02 03 | 04 XX 05 | 06 07 08 |
// | 19 13 20 | |
// -------- -------- --------
// | 14 | |
// | 15 | |
// | 16 | |
// -------- -------- --------
I also created a few arrays to stored precomptued numbers:
- Array mapping indexes of digit 0 to 9 to their power of two.
- Dictionary mapping powers of two to the digits 1 to 9.
- Array mapping an index to the number of bits turned on in that number.
Heuristics and Backtracking
Regardless of the above methods, I believe most of the speed comes from the use of heuristics. I was inspired from this post on Sudoku solving, specifically the use of preemptive sets.
My implementation of a backtracking algorithm is the most obvious implementation with the exception that before making a guess, I start with the cell with the fewest possible digits remaining. Again, this feels intuitively correct, but I have no benchmarks.
The solver seems to be fast, but I don’t know if my work was necessary for performance or I made it more complicated for no reason.
I’d have to write a bunch of alternative solvers and benchmark.
Puzzle Generator
The two remaining challenges for me are puzzle generation and difficulty assessment. These two features have absolutely nothing to do with computer vision goal of this project, but I figured since I was writing the code, I may need this feature some day.
The constraints:
- The generated puzzles must only have one solution.
- The generated puzzle should be close to the difficulty assessment.
Fortunately, after building my solver, I noticed that if I provide an empty grid to the solver, it will find a solution in approximately 150μs.
The fact that this worked so quickly gave me an idea for generator.
First, I need to find any solution. Here is my approach:
- Choose an unsolved square and set it to a random valid digit.
- Ask my solver to search for solutions, but return no more than two.
- If it finds none, start over.
- If it can only find one, then stop.
- If it finds two, then repeat step 1. This algorithm should be able to generate a unique random puzzle quickly. In practice it was clocking at about 300ms. I can definitely make this faster.
Unfortunately, I now have a random, but valid sudoku solution, but no idea how to generate a puzzle of a specified difficulty from that solution. I’ll need to experiment with this, but I think for now I need to move on to the next part of this project.
Summary of Work Remaining for Part 1
- Puzzle Generator (with difficulty)
- Hint Generator
I have also decided not to focus too much on performance improvement at this stage. At 131μs per puzzle, this is fine for this portion of the overall system. I imagine my bottlenecks will be in CV processing.
You can find the code on my github.