I first developed my Sudoku game system back in 2005. Over the years thousands of people have played it and many have sent positive feedback. However, the one recurring issue since launch has been the quality of the computer generated grids – the quality was variable and often it would generate grids which had more than one possible solution (a bad thing in Sudoku circles).
It turns out that good, difficult Sudoku puzzles take a while to generate, solve and grade. So whereas the old system spat out grids on-the-fly, the new system has to generate puzzles in advance. Here’s roughly how it works…
- The system first generates a thousand or so puzzles with no particular restrictions. These are quick to generate (approx 30 puzzles per second) and tend to be fairly easy puzzles to solve.
- It then generates a thousand puzzles that require at least one advanced technique (beyond the usual naked and hidden pairs). These take much longer to generate (approx 4 puzzles per minute).
- Next, the system attempts to solve the puzzles using ‘human’ techniques (rather than brute force random guessing). This gives each puzzle a grade.
- Finally, the solutions are de-duplicated and everything is stuffed into a MySQL database where they can be ordered by the grade they’ve been assigned. This step is important, as some of the puzzles with no restrictions actually turn out to be really difficult, while some advanced technique puzzles actually turn out to be quite tame.
The database currently contains nearly 2000 unique puzzles, split into categories of Easy, Medium, Hard and Evil, based on their computed grade.