Sudoku Solver (Part 1b) - Improve solver speed
What happened?
So after publishing my last article, I did some research and found some great information online about solving Sudoku (specifically, solving hard Sudoku puzzles as fast as possible).
I was very happy with my solver that could solve one of the 9 million sudoku puzzles (from Kaggle) in an average of 131μs; however, this was not even close to good enough on the scale of what was possible. In terms of a computer vision application, this performance level is most likely adequate; however, after reading about the possibility of much better performance, I was nerd-sniped and decided I needed to improve my code.
But instead of doing that, I got a bit overwhelmed and walked away from the problem (for two months).
After a few months of playing around with Open AI (more articles on that in the future), I have returned to the Sudoku CV project. Let’s dig in.
Stack Exchange - Code Golf
Stack Exchange is a collection of communities on various topics. Generally, it covers a lot of technical topics and started with Stack Overflow. Basically, this is where people go when they have no idea how to do something with a computer and they need someone smarter than them to tell them what to do.
The Code Golf community is where those smart people go when they want to feel inadequate.
Per this Stack Exchange post from 2019, there are extremely difficult sudoku puzzles called “17-clue puzzles.” These hard puzzles are considered to have the theoretical minimum number of clues that yield only a single solution. In that post, there is a link to where you can find 49,151 puzzles and the challenge is to solve these most-difficult puzzles as fast as possible.
The file is easy to parse:
- Line 1 - How many puzzles are in this file?
- Line 2+ - 81 characters (0 to 9) describing the sudoku puzzle.
There are some additional rules in the code golf problem statement, for example, you can’t create a file that has the solutions to the puzzles, write a parser, and then call that your code. The point of the exercise is to write a fast solver.
The best solver tdoku, hereafter “the fast code”, solved that collection of puzzles in 200ms, an average puzzle solution in only 4μs. My code, when run against these harder problems solves these puzzles on average in 789μs. For my code, this is a huge slowdown from the average case Kaggle puzzle (6x slower) and almost 200x slower than the best-case tdoku solver, so there is a significant amount of work to be done in my code. See the table below.
| Version | Date | Puzzles | Total(s) | Per Puzzle(μs) |
|---|---|---|---|---|
| Tdoku | 2019-08-29 | 49151 | 0.201s | 4μs |
| Mine | 2023-06-11 | 49151 | 38.8s | 789μs |
What do I do next?
I figure I have a few ways I can approach this problem and I have listed them in order of practicality.
| Ignore | For CV, at 30fps, 789μs could solve each frame of video 42 times. This is a premature optimization. | |
| Steal | I can copy-paste the fast code and be happy that I got it to run. | |
| Learn | I can read the fast code and try to understand what they are doing and then imitate it. | |
| Innovate | Use the metric of 4μs as an inspiration to revisit the problem, but with my own novel approach. |
So my intuition tells me that I am probably going to do the last option, which is definitely the slowest, most unnecessary, and creates a lot of wasted effort on my part.
But why?
Do you find yourself doing that as well? I do this all the time. I have a toxic behavior where I want to solve the problem “on my own.” I, quite arbitrarily, decide that I’m going to do certain things on my own and I can be quite irrationally stubborn about it. It seems to be a silly behavior that creates a type of Lean waste known as Over Production. I seem to always want to spend a significant amount of effort to create something that already exists so that I can put my stamp of individuality on it.
On the other hand, the overall purpose of this project is to create a computer vision project that solves a sudoku puzzle. That project idea is itself a duplication of work that already exists, so I would save even more time by not doing anything at all.
So I have to balance a few truths:
- I started doing this project to learn about computer vision.
- However, I don’t have any specific agenda at all except to learn, so it isn’t much of a distraction to work on a fun optimization problem along the way.
- However, I didn’t desire to be innovative at all, my primary goal was learning, so I’d rather just learn what someone else has already done.
Imitate (i.e. Learn)
Ok, let’s dig into the tdoku code, figure out what on Earth they are doing to be so fast and imitate a similar solution in C# and benchmark.
More to follow.
Thanks for reading part 1b of my quest to build a CV sudoku solver. You can find the code on my github.