Devlogs
Godoku v0.1.0
Posted November 23, 2023 by templewulf
#godot #sudoku #puzzle #update
Godoku v0.1.0
We jumped from v0.0.6 to v0.1.0, because this update is a big enough deal to warrant it. We've made breaking changes to some of the structures and classes to accommodate the new algorithm. We finally did it! 🎉
The previous algorithm was mostly randomized with some controls, but the new algorithm simulates the way a human player solves a puzzle. The consequences of this change are:
- Algorithmically -- on paper! -- it should no longer generate any unsolvable puzzles. In our testing, we never encountered any unsolvable puzzles 🤞
- The difficulty also went down again a bit. By changing the algorithm to simulate human solving to verify each puzzle, it can't produce any puzzles that are more complex than the solving techniques that have been specifically added.
- It's significantly faster at verifying a solvable puzzle than any other method we've attempted. This version solves in under 3ms on a last-gen CPU, whereas others took upwards of 20ms. That sounds like a tiny difference, but the verification has to run dozens of times per puzzle as different configurations are tested.
Writing a fast sudoku generator isn't *new* computer science, but we're very proud of how it came together. Please enjoy!