Remix.run Logo
▲ alpaca128 2 hours ago

Just yesterday I finished my small sudoku "game" including generator in Odin and it was such a fun project. Not major by line count but optimizing it to generate a new puzzle in <100 ms was a fun exercise.

For anyone curious, I generate the sudokus by first randomly filling an empty grid in a way that follows the sudoku rules, then emptying random cells where doing so doesn't make the solution ambiguous (a sudoku has exactly one valid solution). The first step to fill the grid works almost exactly like a normal backtracking solver but going through the cells in random order, and for a major speed boost the backtracking is far more aggressive (always resetting half the progress so far instead of just going back one step). Checking if a sudoku has multiple solutions is again normal backtracking but only exiting at the second time it finishes or after going through all combinations. The rest is modern computers being fast and limiting the number of iterations to avoid the super slow worst cases.