sudoku
sudoku copied to clipboard
Emerentius
Generate Sudokus
It's a common requirement to set the difficulty of the generated sudoku. Given that humans use other strategies than the very fast backtracking it's likely better to estimate difficulty by applying the same deductions.
Generating a random sudoku until it can be solved by some set of strategies seems like a good first step. Generation of trivial sudokus can be stopped by requiring some strategies to be used at least once. With this approach, generation of harder sudokus is blocked on #2.
- [x] Generate random sudokus
- [ ] Generate sudokus passing some grading threshold
hello @Emerentius any update on this, would love to generate sudoku with various difficulty levels.
That's pretty much blocked on the definition of a difficulty scale and the expansion of the strategy solver. I haven't been spending much time on the library recently. There is no objectively correct way to do this. For example, two of the more prominent sudoku softwares are Hodoku and SudokuExplainer and both use different difficulty scales.
I am reluctant to define my own scale. I think this should be up to the library user. The standard way of generating a sudoku of some difficulty level is pretty much just brute force rejection sampling:
let sudoku = std::iter::repeat_with(Sudoku::generate)
.find(|sudoku| difficulty(sudoku) >= my_desired_difficulty)
.unwrap();
SudokuExplainer assigns a numeric difficulty to each strategy and the difficulty of a sudoku is the maximum of the difficulty of the strategies that were used in its solution.
Hodoku assigns both a difficulty level ("Easy", "Medium", "Unfair", etc) and a numeric score to each strategy. It rates the difficulty of a sudoku as the maximum of the levels of the strategies used in the solution (much like the difficulty score in SudokuExplainer) and the numeric score is just summed up. Hodoku's scoring and solution strategies are also configurable.
The common theme is that the difficulty is derived from the solution steps. The StrategySolver must expose the required information for that.
With the current state of the library, one could implement the SudokuExplainer grading up to a difficulty level of roughly 5. Anything higher requires more strategies to be implemented in the strategy solver. I believe the SudokuExplainer grading goes up to ~11.
probably would love this to be coming in near future though. love this work. waiting for the grader as well.
hey @Emerentius i see there is been progress in the generation, can you help me with generation how to generate and grade?