SudokuSolver Forum

Some thoughts on generating Sudokus having a symmetrical pattern.

Based on the programming of my generator helper, here is how I probably would go about mass generating Sudokus having a symmetrical pattern.

According to Wikipedia there are 6,670,903,752,021,072,936,960 Sudoku solution grids when all kinds of symmetries such as rotation, reflection, relabelling, etc are counted. On problem I had to figure out for my generator helper was how to stellar fast randomly generate any of the 6,670,903,752,021,072,936,960 possible Sudoku solution grids. For a 9x9 grid with some givens I also need to very fast randomly generate one of the possible solutions for this 9x9 grid. I am now able to do both within microseconds.


Generating vanilla Sudokus having a symmetrical pattern ala http://www.fiendishsudoku.com.
I would need two programs. One for generating patterns. Every pattern generated would be converted to a string of its cell numbers separated by dashes. Today’s pattern would be: 1-5-9-12-14-15-21-25-26-29-37-38-41-44-45-53-56-57-61-67-68-70-73-77-81. This would allow easy detection of duplicates and storing in a database. A string of two digit cell numbers could also be used: 01050912141521252629373841444553565761676870737781.

The second program would be the pattern picker, Sudoku solution grid picker and logical solver. First is a set of pattern picked from the database, for instance 10 different ones. The database knows how many times each pattern has been used successfully (all five difficulties Easy, Moderate, Hard, Evil and Fiendish was generated for it), so that preferably never used patterns would be picked.

Then is a Sudoku solution grid generated. For each pattern Sudoku are the solution digits in the cells matching the pattern picked as givens and the Sudoku is solved using the logical solver. For each Sudoku is the result either Easy, Moderate, Hard, Evil, Fiendish or Unsuitable. With a fast and good solver all 10 Sudokus would be rated within one second, especially since techniques harder than X-Wing are not used. This continues in a loop until all five difficulties have been generated for a pattern. For the successful pattern is the result (5 Sudokus with five difficulties) stored and it is replaced with another pattern from the database and the loop continues.


Generating Samurai Sudokus having a symmetrical pattern ala http://www.samurai-sudoku.com.
Again I would use two programs. One for generating patterns, and one for picking patterns, picking solution grids and doing logical solving.

For a Samurai the program would only pick one pattern at a time. Then generate a Samurai solution grid, first the centre 9x9 grid and then the four outer ones, since for each of the four outer ones the 9 givens in the overlapping nonet must be included. The solution digits in the cells matching the pattern are picked as givens and the Samurai is solved using the logical solver. The result is either Easy, Moderate, Hard, Evil, Fiendish or Unsuitable. If the result is not Unsuitable a puzzle was successfully generated. In a loop the program could continue with the same pattern for generating various difficulties or a new pattern could be picked every time a suitable solution was found for a pattern.

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

The way I go:

1. Fill in a solution
2. Choose some symmetry
3. Start with all cells as givens, unless they are in overlapping areas
4. No givens are required at start
5. Choose at random some given not required. To avoid clusters of givens, choose among cells having most adjacent givens.
6. Remove this given and any symmetrical ones. Updating the number of adjacent givens.
7. Check the puzzle still has a unique solution. If not, the given(s) are required. I also check here this does not yield too many guesses or too few givens.
8. Repeat from 5. until all givens are either removed or required.
9. Finally, check the number givens and guesses are within the ranges specified. If not, restart from 1.

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

Nice algorithm! But you are not mass generating Sudokus or?
Would be nice if a difficulty could be chosen in JSudoku.

To me this sounds like a contradiction

In my generator helper I calculate a set of dispensable clues for each 9x9 grid. A dispensable clue is a clue that can be deleted so that the 9x9 grid regarded as a vanilla Sudoku will still have one solution only. For every iteration I then in every 9x9 grid select a dispensable clue as discardable. It is the dispensable clue having most buddies with a given.

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

I know, but I don't have any rating yet. This would also require using the logical solvers at each step.


I use a set of cells tagged as "required given". It's empty at start. It gets filled with givens required to have a unique solution. Refer to the end condition 8.

Note. Ruud seems to use the same approach as me for vanilla sudoku. See: http://www.setbb.com/sudoku/viewtopic.p ... rum=sudoku


I do not understand the difference between "dispensable" and "discardable".

For overlapping puzzles, I work on the whole puzzle (all sub-grids), taking into consideration inter-grid relations.
The main problem for me is filling a solution for overlapping puzzles which sometimes wander in waste-land... I guess it's due to some contradiction which takes very long to detect. I may try the way you suggested, starting filling the sub-grid having most overlapping cells (center of samurai, clueless), and then filling the rest. Anyhow, I would still have the very same problem with some "exotic" diagonal variants, like Argyle, Bold-X...

Note: I made some Q&D tests with a pattern based generator. I noticed very few random grids are valid. I believe the generator should include something to prevent dealdly patterns (UR...) in the ungiven cells.

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

Which is slower I presume?

For a 9x9 grid the discardable clue is one of the 9x9 grid's remaining dispensable clues. It is the dispensable clue having most buddy cells containing a given.

... or a Shogun, a Shaolin, a DOAG, etc.

I am working on an algorithm for generating valid code (9 givens) for all overlapping nonets. With valid code I mean code so it is possible to generate a legal Sudoku for all grids.
I have programmed the bare skeleton for the recursive walker and backtracker, but still need to put on some flesh.

The basic algorithm is:

1. Sequentially do a grid at the time and generate valid code for all overlapping nonets, i.e. generate a random solution for the complete grid including existing givens in one or more overlapping nonets and then remove the code in all cells except those in overlapping nonets.
2. If I have to redo the code for a nonet already having code, I signal all the grids having this nonet as a member and if necessary redo the code for theese grids (backtracking).
3. After an overlapping nonet has been visited by its second member grid, the code in that nonet is locked, i.e. not more changeable.

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]