Other Software > Developer's Corner

Constructing a minimal Sudoku puzzle

<< < (4/4)

4wd:
Javascript version that runs in your browser: jsSudoku

It's generating puzzles almost immediately on my computer at any of the 5 difficulty levels.

Deozaan:
Javascript version that runs in your browser: jsSudoku

It's generating puzzles almost immediately on my computer at any of the 5 difficulty levels.
-4wd (July 29, 2021, 07:32 AM)
--- End quote ---

After looking through the source code for a few minutes, it appears to be generating the solution using an idea that occurred to me as a possibility sometime in the past couple of days.

It starts with a single, pre-generated solution, then applies random transformations to it fifteen times, which basically shuffles it in ways that maintain the legality of number placement. (In my own code, I was generating a random solution, then transforming it 100 times. This usually only took tens of milliseconds at most, but sometimes generating a random solution took hundreds of milliseconds. Meanwhile, transforming is always super quick to do, taking only up to a few milliseconds at most, but often finishing under 1ms.) So they skipped the slowest part of solution generation by starting with a solved puzzle and just transforming it.

Then, to create a puzzle out of the solution, it randomly removes a certain number of digits based on the difficulty level. That is to say:


* Trivial removes 22 digits, resulting in 59 givens.
* Easy removes 32 digits, resulting in 49 givens.
* Medium removes 42 digits, resulting in 39 givens.
* Hard removes 52 digits, resulting in 29 givens.
* Ultra removes 58 digits, resulting in 23 givens.
Like the python code wraith808 linked to, the result is obviously not necessarily a minimal puzzle. And in fact, all but Hard and Ultra difficulty result in puzzles that have so many givens that professional Sudoku puzzle creators would throw them out.

I also insist that the average number of clues hangs around 27 and is never more than 30. Nikoli, the inventor of the modern version of Sudoku states as part of his definition that the number of clues should not exceed 32.

[...]

Over a large run I get a set of puzzles where the number of clues is a bell-curve centered on 27.-https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf
--- End quote ---

But in the case of Ultra difficulty, which results in a puzzle with only 23 givens, it may be good enough considering the speed at which it does it. Many of the puzzles I've been generating the slow way have up to a few more givens than that.

So maybe I just need to drop the self-imposed requirement of having a minimal puzzle, since it seems there do exist other methods of generating a puzzle that is good enough in a much faster time.

Navigation

[0] Message Index

[*] Previous page