re: Coming Back to Old Problems: How I Finally Wrote a Sudoku Solving Algorithm VIEW POST


Amazing, the sudoku part almost exactly mirrors my experience.
I first wrote it in javascript, with sets of possible numbers for every cell and human-like non-destructive transforms being applied (only answers we are sure about). There were quite a few different transforms, because I picked a modified version of Sudoku which had these additional blob sum constraints, which were interesting because they were indeed sums and not sets of the [1,9] range.
For the UI, it used Vue, but really the renderer was mostly handwritten svg. It solved the lesser difficulties, but then I got bored.
Later, I stumbled upon someone quoting the backtracking algorithm as described in wikipedia. So I implemented it in Rust, with the additional constraints. The first time I wrote it, it solved them all in negligible time. I also tried it 3x4 and 4x4 boards. 4x4 gave noticeable time, and anything above 4x4 took too long to run.
Perhaps applying human-like transforms is computationally valuable at bigger board sizes to reduce the iteration space dramatically.
Maybe I'll still port those, or make the rust code an API or a WASM embed to the UI. Probably not though.

code of conduct - report abuse