The New Sudoku Players' Forum

[1to9only]

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.
.

[m_b_metcalf]

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.

[Hajime]

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?

[m_b_metcalf]

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.

[1to9only]

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.
.

[m_b_metcalf]

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

[m_b_metcalf]

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

[m_b_metcalf]

This allows the generation of X-sudokus like these...

See here for a follow-up. M

[champagne]

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

[JPF]

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

[m_b_metcalf]

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

[lauria]

One exposes oneself to the risk of generating puzzles with multiple solutions.

[coloin]

One exposes oneself to the risk of generating puzzles with multiple solutions.

well i think the programs that we use indeed specifically test for validity
and it is a good challange - several million puzzles later and a very concerted effort it took to find only one 9.5, no attempt for symmetry but several almost diamonds

Code: Select all

....8...4.2.7..1....36.1...29......3....5...7.45...2.....9..7...195...8.6....8.5. ED=9.5/1.2/1.2       C25.m
1..28...4.2.7..1....3.......9...75.336..5...7......21....9..7...195...8.6....8... ED=9.4/9.4/7.1       C26.m
1...8...4.2...51....36......9...75.3....5...7.4....21....9..7...19.....26...28... ED=9.4/9.4/3.4       C25.m
....8...4.2.7.51....3..1.....8....6336......77.5....1....9.47....95...8.6.7.2.... ED=9.4/9.4/2.6       C26.m
...28...4.2.7..1....3..1....9......3....5.9.7.45...2..5..9.47...195...8.6....8... ED=9.3/9.3/9.2       C26.m
....8...4.2...51....36.1..5.9....5.33...5...7.45...21....9..7...19..3..26....8... ED=9.3/9.3/9.1       C27.m
...2....482...51....36.1....9.4...6.3...5...7..5...2.....9.47...1..7..8.6.......9 ED=9.3/9.3/9.0       C25.m
....8...4.2.7...9...3..1...29......33...5..4..45...2.....9.47.1.195...8.6....8... ED=9.2/9.2/9.1       C26.m


[1to9only]

From a Nov 05, 2020 post in this thread:

Hi all,
By creating puzzles by removing candidates from the same solution, one exposes oneself to the risk of generating puzzles with multiple solutions. How do you proceed to guarantee uniqueness?
Robert

One exposes oneself to the risk of generating puzzles with multiple solutions.

So I much doubt this piece of automated silicon knows the meaning of the above sentence. See also: here.

[urhegyi]

Your new option in sudokuexplainer "use solution" works fine and can be used for this purpose.
Is there also a way to invoke the generator from the command line?
I think of a get-set solution grid, get-set enabled solver methods, nr of solutions to generate and finally the file path to redirect the output.
Same question for the jigsaw version, but with a shape layout as input and eventually a predefined solution grid.
I experimented with invoking the serate utility from within a java program and like to do the same with the solver and generator to.
The aim is to generate a large batch file that can be used to filter out some interesting candidates in an automated way.
Is there any documentation about the parameters and public methods that can be used?

Hidden Text: Show

Code: Select all

import java.io.*;
class Batch {
   
   /**
    * Method main
    *
    *
    * @param args
    *
    */
   public static void main(String[] args) {
      // TODO: Add your code here
      Runtime rt = Runtime.getRuntime();
    try {
        String path = "C:\\Users\\Peter\\Documents\\";
        String InputPath=path+"jigsaws.txt";
        String OutputPath=path+"output.txt";
        String ProgramPath=path+"SudokuJigsawExplainer.jar";
        String test="java.exe -Xrs -Xmx500m -cp "+ProgramPath+" diuf.sudoku.test.serate --input="+InputPath+" --output="+OutputPath;
        rt.exec(test);

    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
   }   
}