Digdoku
Posted
I randomly had the idea that it would be interesting to “dig into” all possible Sudoku puzzles. So I created Digdoku. The landing page is an “empty” puzzle, each link leads to a puzzle with one additional square filled. Values that are not possible are excluded. So you can never get an invalid puzzle by clicking links (but you can by editing the URL).
The concept is simple. Basically for every unset cell it attempts to solve the puzzle with every number from 1-9. If any solution is found that value is possible, otherwise it is omitted.
This “eager” removal of impossible values means that it functions as a solver as well. By the time you click all of the provided squares (or often sooner) there will be only one possible grid, and it will be revealed.
However, implementing this simple solution is fairly slow. So some optimizations were necessary. These are primarily around skipping options that are easily determined to be impossible or were already found to be possible. The solver is still mostly a brute-force depth-first solver with some very basic rules put on top (such as eliminating duplicate values in a box/column/row group and if a value can only be in one place as a group it must be that).
The slowest case I am aware of takes about 100ms on my desktop. It could almost certainly be much faster, I suspect another order of magnitude would be fairly easy to achieve. But in the first version some cases took over six minutes, so I’m calling it good enough for now.
One downside is that the URL only keeps minimal state, so a lot of options need to be re-eliminated every step of the way. Maybe compiling to WASM and running an incremental solve client-side would be better. Might be something interesting to try. It would also avoid the risk that my single-core VPS gets overloaded if this gets popular. I do have caching enabled, but I suspect after a few clicks hits will become quite rare.
There is also something about a simple HTML response that I am very fond of. Theoretically you could pre-render every possible grid into a static site. But according to Wikipedia there are 6.6e27 valid Sudoku grids, so I’ll hold off on the pre-render for now.