How to create a sudoku starting from a solution

Everything about Sudoku that doesn't fit in one of the other sections

Re: How to create a sudoku starting from a solution

Postby 1to9only » Thu Nov 05, 2020 5:46 pm

I modified SudokuExplainer to use a solved Sudoku as solution grid to generate a new random Sudoku.
I left a command line version of this running overnight, it ran for about 12 hours or so, generating about 200k Sudokus!
Code: Select all
...2....48..........3..1.25...41..63.....29.7.4..9....58....731....7....6..12..5. 26 ED=9.2/1.2/1.2  74,941st
..6....7....7..1..9...4...529.4.......1.5.9..7..3..2...8.96...1.1.......6.7..84.. 25 ED=9.3/1.2/1.2 158,163rd

SudokuExplainer checks a Sudoku has a unique solution by (bruteforce) solving the puzzle twice as follows:

solution 1:
Code: Select all
- solves all singles
- pick 1st cell with least number of candidates, e.g. r1c2
- try lowest to highest value candidate, e.g. r1c2, try 2, 8 then 9
- check grid can still be solved and has one solution
- else restore candidate and try next lowest candidate
- loop until solved

solution 2:
Code: Select all
- solves all singles
- pick 1st cell with least number of candidates, e.g. r1c2
- try highest to lowest value candidate, e.g. r1c2, try 9, 8 then 2
- check grid can still be solved and has one solution
- else restore candidate and try next highest candidate
- loop until solved

if solution 1 = solution 2, then the solution is unique.
if solution 1 is not equal to solution 2, then the Sudoku has multiple solutions.

SudokuExplainer creates a random solution grid by passing an empty grid to above solver [solution 1] with an index tweak:

random solution grid:
Code: Select all
- solves all singles
- pick 1st cell with least number of candidates, e.g. r1c1
- try a random offset to pick lowest to highest value candidate, e.g. r1c1, 123456789[random offset]
- check grid can still be solved and has one solution
- else restore candidate and try next lowest candidate
- loop until solved

SudokuExplainer generates a random Sudoku as follows:

- shuffles a list of cells into a random list of cells, e.g. 1-81 into e.g. 21,54,7,32,...

- process list starting from a random index, remove one (no symmetry) or more (symmetrical) given(s), e.g. cell 48 = 0
- check grid can still be solved and has one solution [as above]
- if grid cannot be solved, restore cell and repeat with next from list
- if grid is solved, restart process from list starting from another random index

- repeat above, until list of cells [81] processed with no new grid produced
- rate the grid, if rating not in requested range, repeat all of above

To show the Sudoku is minimal:

- remove a given from the Sudoku, and test if this has a unique solution [as above]
- try all givens, one at a time - if none have a unique solution, then Sudoku is minimal

SudokuExplainer does not check for minimal grid when generating, just for unique solution.
.
1to9only
 
Posts: 2127
Joined: 04 April 2018

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Thu Nov 05, 2020 7:48 pm

Mauriès Robert wrote:
m_b_metcalf wrote:By testing for uniqueness at each step, and restoring any clue(s) whose removal causes the candidate puzzle not to have a unique solution.

Thanks Mike. It's a tedious job. Do you do this with a solver or by hand?

We have computers to deal with these tedious tasks! M.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Re: How to create a sudoku starting from a solution

Postby Hajime » Thu Nov 05, 2020 8:04 pm

That is very informative, 1to9only.
The "random solution" is about the same I use.
The lowest to highest versus highest to lowest and than a check if the solutions is the same is pretty smart and works fast using only brute force method.
But at the end you have to determine the ED, so all methods need to be executed if necessary for this puzzle, isn't?
User avatar
Hajime
 
Posts: 231
Joined: 20 April 2018
Location: Netherlands

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Thu Nov 05, 2020 8:04 pm

For the sake of completeness, there are several checks on whether a candidate puzzle has multiple solutions that can be made without having to invoke any solver whatsoever:

1) if the remaining clues share a total of fewer than eight distinct values;

2) if the removal of a clue would leave an unavoidable set uncovered.

For instance, in the solution grid of this thread there are U4s at r59c12, r29c23, r17c78, r15c89, r12c39, r13c16, r78c57, r89c17 and r79c49 (at least).

There are also fast checks on minimality which I don't have time to type in just now.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Re: How to create a sudoku starting from a solution

Postby 1to9only » Thu Nov 05, 2020 9:26 pm

Hajime wrote:But at the end you have to determine the ED, so all methods need to be executed if necessary for this puzzle, isn't?

This is correct, for the generator to determine if the puzzle difficulty (ER) is within the difficulty requested.
Code: Select all
Easy     1.0-1.2
Medium   1.3-1.5
Hard     1.6-2.5
Fiendish 2.6-6.0

In recent SudokukuExplainers I've tried tweaking (speeding up!) the analyseDifficulty() function:
- if an Easy/Medium/Hard puzzle is requested, techniques rated 2.6-2.8 (Pointing/Claiming) and above are not attempted, returning ER=20.0 instead.
- if a Fiendish puzzle is requested, no chaining technique is attempted, returning ER=20.0.

I also end up rating the puzzle a second time to get ER/EP/ED before saving to file.
This process (having to rate a puzzle twice) slows generation a bit for high-rated puzzles.
.
1to9only
 
Posts: 2127
Joined: 04 April 2018

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Fri Nov 06, 2020 8:48 am

m_b_metcalf wrote:There are also fast checks on minimality which I don't have time to type in just now.

Now I'm back and the two fast checks for minimality are:

1) check no value occurs more than 6 times, or

2) more than 4 times if they're on intersecting horizontal and vertical bands.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Fri Nov 06, 2020 9:51 am

urhegyi wrote:I created this solution today. Are there rules to consider when starting to remove clues to create sudoku's with different hardness levels based on this.

I've just noticed that your grid also has the X property. This allows the generation of X-sudokus like these (symmetrical):
Code: Select all
..62.9.7......5.......4..2.........3.61...94.7.........8..6.......5......3.1.84..   ED=9.9/9.9/7.8   
1.62.93......3.............2.8....63..1...9..74....2.8.............7......71.84.9   ED=10.4/10.4/2.9
1...8..7....7..1.6.........2......6...18.29...4......8.........4.9..3....3..2...9   ED=10.6/10.6/4.3
1..2...7.8..7....6.............1.5...61...94...5.9.............4....3..2.3...8..9   ED=10.7/10.7/2.9 X-sudokus

and these (asymmetrical and minimal):
Code: Select all
...28.............9....1.2...84......6..52...74..9...8.......3....5..6.....1.....   ED=9.9/1.2/1.2   
..62..3.4........6.....1.2..98........1..2...74.......5....4.3......3..2.....8.5.   ED=10.8/1.5/1.5  X-sudokus
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Mon Nov 09, 2020 3:58 pm

m_b_metcalf wrote: This allows the generation of X-sudokus like these...

See here for a follow-up. M
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Re: How to create a sudoku starting from a solution

Postby champagne » Mon Nov 09, 2020 8:18 pm

I enter late in this discussion, but unless I missed a point, I did not see here anything else than a random generator as basis to produce solutions out of a given solution grid.

The most efficient process is without any doubt to rely on a list of unavoidable sets.

Then you have still several ways to implement it.

Our friend "Blue" proposed a very efficient process based on valid solutions for a given band "gangster". This is now the agreed best way to extract 17 clues puzzles from a solution grid.

Based on this process, you can easily produce puzzles in the range 20_23 clues where you can have the best chance to produce hard puzzles.

EDIT and this can be an exhaustive process if needed
champagne
2017 Supporter
 
Posts: 7166
Joined: 02 August 2007
Location: France Brittany

Re: How to create a sudoku starting from a solution

Postby JPF » Tue Nov 10, 2020 1:04 pm

Finding from a solution grid the puzzles with the highest -SE- rating seems to me a good challenge.

Here is my first proposal:
Code: Select all
.5..8...482.7...9...3..18.........6..6.85...7..5..62.....9...31..9..36......2....  ED=9.4/9.4/2.6
1..2..3....4..5.9..7.6....5......5.......2.4.7...9...8.8..6...1..9..3...6..1....9  ED=9.4/1.2/1.2
.5..89.....4.351..9..6...2..98...5..3......4...5..6.........7.14..5...8...7.2...9  ED=9.4/1.2/1.2
.5.2..3....4..5.9.9...4...52...1..63..1..2..7.4.3..2..........1...5..6..6.7..8...  ED=9.4/1.2/1.2
..6..9...8...3.....7.6......9..1.5....1..2.4.7...9...8..2..4.3.4...7...2.3.1....9  ED=9.4/1.2/1.2


EDIT:
Code: Select all
.5..8......47..1..9....1..5.9.....6.3....2..77.53......8..6..3....5....2..71..4..  ED=9.5/1.2/1.2


JPF
JPF
2017 Supporter
 
Posts: 4397
Joined: 06 December 2005
Location: Paris, France

Re: How to create a sudoku starting from a solution

Postby m_b_metcalf » Tue Nov 10, 2020 6:41 pm

Can't beat your ERs, but I found these EDs:
Code: Select all
...2....4.....51....36.1.2..98....633...5...774....21..8.9.47....95.....6....8...   ED=8.5/8.5/7.6
....8.....2.7...96..3..1.....84..56.3.......7.45..62.....9..7..41...3.8.....2....   ED=9.0/9.0/6.6
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11320
Joined: 15 May 2006
Location: Berlin

Previous

Return to General