The New Sudoku Players' Forum

by **Afmob** » Tue Aug 06, 2013 6:09 am

I currently have no interesting in getting results for the difficulty of 18 clue minimals but if anyone is interested, here are the puzzles created by the last large parallel computation:

Hidden Text: Show

by **champagne** » Tue Aug 06, 2013 6:30 am

Afmob wrote:I currently have no interesting in getting results for the difficulty of 18 clue minimals but if anyone is interested, here are the puzzles created by the last large parallel computation:

It would not be so difficult to do that, but working more on the potential hardest, where so far the lowest number of clues is 20, I would not start the work with a small file. I am more interested in seeing what happens with 26 clues and started investigations in that direction.

Is there somewhere a collection of known 18 puzzles like for 18 puzzles ?

Website · by **denis_berthier** » Tue Aug 06, 2013 7:01 am

Afmob wrote:I currently have no interesting in getting results for the difficulty of 18 clue minimals but if anyone is interested, here are the puzzles created by the last large parallel computation

Thanks, I'll put these computations in my todo list.

[Edit]:

Actually, there were few puzzles and the computations were short:

max SER = 9.0
min SER = 1.2
mean SER = 2.64
sd(SER) = 1.67
kurtosis = 2.54

This confirms that the mean SER for the 18s is much below the mean value for the whole set of minimals: mean SER = 4.73, sd(SER) = 2.49

Website · by **denis_berthier** » Tue Aug 06, 2013 7:11 am

champagne wrote:I am more interested in seeing what happens with 26 clues

The mean SER and W rating for # clues around 26 (between 22 and 30) has been published 4 years ago (together with lots of other stats), based on the unbiased, uncorrelated collection of about 5.9 million puzzles produced by the controlled-bias generator. See p. 29 of the pdf available from this page http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995-135.html. You can also see my books or my Sudoku web pages.

by **champagne** » Tue Aug 06, 2013 12:23 pm

denis_berthier wrote:
champagne wrote:I am more interested in seeing what happens with 26 clues

The mean SER and W rating for # clues around 26 (between 22 and 30) has been published 4 years ago (together with lots of other stats), based on the unbiased, uncorrelated collection of about 5.9 million puzzles produced by the controlled-bias generator.

On my side, I am not at all interested in mean values but on what happens on the high ratings.

AFAIK, no puzzle below 20 clues has been published with a rating in the range of SER 11.
I have so far 13 puzzles rating SER 11 and more (maximum 11.3) with 26 clues, but this is a freshly opened area

by **Afmob** » Mon Aug 12, 2013 2:44 pm

You can also use the subset and superset method to compute the number of valid puzzles. So I gave it a try with the subset method and it's quite easy to do. I only had to delete the minimality test and I was good to go. An interesting value to compute is the percentage of minimal puzzles from all valid puzzles of a certain size. I used my former results to calculate that. Note that I didn't reuse random seeds this time, so I didn't get as many seeds per hours as usual.

Subset results:

Code: Select all: Computation time: 31x5 hours 1,973,700,000 samples 3,407,809 valid 28 hits 402,701,902 valid puzzles +----+-----------+------------+----------------+------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | Minimality | +----+-----------+------------+----------------+------------+ | 19 | 24 | 2.666e+03 | 2.635e+01 | --- | | 20 | 4492 | 3.438e+06 | 2.718e+00 | 93.979 % | | 21 | 254864 | 1.487e+09 | 6.109e-01 | 86.752 % | | 22 | 4711506 | 2.356e+11 | 2.554e-01 | 68.548 % | | 23 | 33060058 | 1.626e+13 | 1.478e-01 | 42.454 % | | 24 | 99380167 | 5.670e+14 | 1.017e-01 | 18.765 % | | 25 | 138948825 | 1.130e+16 | 7.780e-02 | 5.528 % | | 26 | 93632587 | 1.421e+17 | 6.424e-02 | 1.044 % | | 27 | 29301570 | 1.223e+18 | 5.678e-02 | 0.128 % | | 28 | 3407809 | 7.680e+18 | 5.412e-02 | 0.009 % | +----+-----------+------------+----------------+------------+

If there is more interest I can make a larger computation to get results for the 18 clue puzzles.

Website · by **denis_berthier** » Mon Aug 12, 2013 2:57 pm

Afmob wrote:An interesting value to compute is the percentage of minimal puzzles from all valid puzzles of a certain size. [...]
If there is more interest I can make a larger computation to get results for the 18 clue puzzles.

Having the percentage would be interesting for 18, 19 but also beyond 28. It seems to be quickly becoming very small.

by **dobrichev** » Tue Aug 13, 2013 7:50 pm

Afmob wrote:An interesting value to compute is the percentage of minimal puzzles from all valid puzzles of a certain size. ... If there is more interest I can make a larger computation to get results for the 18 clue puzzles.

I am interested in a chart with
a) the portion of the minimal from all solvable puzzles, regardless of the uniqueness,
b) the portion of the puzzles with unique solution from all solvable puzzles, regardless of the minimality, and
c) the product of the above,
against the number of clues.

For a) I expect the first non-one value at 9 clues - for 9 givens in a house, one is redundant. For 41 clues the value is still non-zero.
For b) the minimal non-zero value is at 17 and the maximal non-one value is at 77 = 81 - UA4.
What happens in between?

If a) and b) are independent (are they?) then c) should match the discussed distribution of the minimal unique puzzles. Each of the three distributions could be obtained from the rest two. Could this help in refining c) at the high-clue edge?

by **Afmob** » Wed Aug 14, 2013 5:00 am

dobrichev wrote:For a) I expect the first non-one value at 9 clues - for 9 givens in a house, one is redundant. For 41 clues the value is still non-zero.

You can even find smaller size cases where there is non-minimality like this one (just the first band):

Code: Select all: *-----------* |...|...|..1| |...|..1|...| |123|...|...| *-----------*

I might give your questions a try but I'm not sure if the distribution of minimal puzzles between solvable puzzles is the same as the distribution of minimal puzzles between uniquely solvable puzzles.

by **dobrichev** » Wed Aug 14, 2013 10:05 am

Nice example, thanks!
The distributions obviously are not the same, at least because for the same example the minimal/unique ratio is not applicable.

by **Afmob** » Sat Aug 17, 2013 7:16 am

Following dobrichev's suggestion I used the subset/superset method to get the number of minimal (but not necessarily valid) puzzles. I planned to post this earlier but my first tries of programming led to messed up results.

First some terminology: I call a puzzle weakly minimal if it is minimal but not necessarily valid as in having mulitple solutions. If a puzzle is minimal I also assume that it is valid. So every minimal puzzle is also weakly minimal but not vice versa.
Both the subset and the superset method are rather slow in regards to counting weakly minimal puzzles in the main part of the distribution but get faster for the tails. In the following computations I used the same 10,000 unbiased grids and only regarded puzzles between sizes of 24 and 28. The ratio column describes the percentage of puzzles having at least one solution having also the property that is counted.

Valid puzzles using the subset method

Code: Select all: Computation time: 1 hour 486,455,738 samples 834,202 valid 24 hits 89,098,618 valid puzzles +----+-----------+------------+------------+------------+ | Cl | Count | E(nr/grid) | E(rel err) | Ratio in % | +----+-----------+------------+------------+------------+ | 24 | 24279017 | 5.610e+14 | 0.21 % | 2.438e-04 | | 25 | 33938031 | 1.119e+16 | 0.16 % | 2.130e-03 | | 26 | 22880622 | 1.409e+17 | 0.13 % | 1.244e-02 | | 27 | 7166746 | 1.213e+18 | 0.11 % | 5.262e-02 | | 28 | 834202 | 7.627e+18 | 0.11 % | 1.715e-01 | +----+-----------+------------+------------+------------+

Weakly minimal puzzles using the superset method

Code: Select all: Computation time: 1 hour 2,385 samples 506 weakly minimal 24 hits 5,080,860 weakly minimal puzzles +----+-----------+------------+------------+------------+ | Cl | Count | E(nr/grid) | E(rel err) | Ratio in % | +----+-----------+------------+------------+------------+ | 24 | 506 | 4.891e+19 | 3.95 % | 2.122e+01 | | 25 | 16227 | 6.274e+19 | 4.08 % | 1.194e+01 | | 26 | 202541 | 6.024e+19 | 4.50 % | 5.321e+00 | | 27 | 1212915 | 4.008e+19 | 5.36 % | 1.738e+00 | | 28 | 3648671 | 1.723e+19 | 5.97 % | 3.873e-01 | +----+-----------+------------+------------+------------+

Minimal puzzles using the subset method

Code: Select all: Computation time: 1 hour 458,667,079 samples 786,212 valid 28 hits 6,302,013 minimal puzzles +----+-----------+------------+------------+------------+ | Cl | Count | E(nr/grid) | E(rel err) | Ratio in % | +----+-----------+------------+------------+------------+ | 24 | 4297196 | 1.055e+14 | 0.17 % | 4.576e-05 | | 25 | 1771000 | 6.195e+14 | 0.19 % | 1.179e-04 | | 26 | 225476 | 1.472e+15 | 0.34 % | 1.301e-04 | | 27 | 8261 | 1.484e+15 | 1.30 % | 6.432e-05 | | 28 | 80 | 7.758e+14 | 11.18 % | 1.744e-05 | +----+-----------+------------+------------+------------+

Minimal puzzles using the first two tables

Code: Select all: +----+------------+------------+ | Cl | E(nr/grid) | Ratio in % | +----+------------+------------+ | 24 | 1.193e+14 | 5.173e-05 | | 25 | 1.337e+15 | 2.543e-04 | | 26 | 7.494e+15 | 6.619e-04 | | 27 | 2.109e+16 | 9.145e-04 | | 28 | 2.954e+16 | 6.652e-04 | +----+------------+------------+

While the estimation in the last table is pretty good for 24 clues it gets worse with increasing number of clues, so even though the error estimates for the first tables aren't that good I don't think that we can use this method to get an estimate for the number of high clue minimal puzzles.

by **Afmob** » Fri Aug 30, 2013 3:46 pm

Being on vacation, I have some CPU time to burn, so I thought about improving the current results. First, I'll try to improve the estimate for the number of 18 clue minimals. The computations will run until 16th of September. I expect to get more than 1.3 million samples and the relative error should be below 2.5%.

Superset results

Code: Select all: Computation time: 31x17 days 1,310,492 samples 1,310,492 size 3 subsets 4,386 valid minimal puzzles +----+-------+------------+----------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | +----+-------+------------+----------------+ | 18 | 4386 | 3.499e-01 | 2.177e+00 | +----+-------+------------+----------------+

The second computation will estimate the number of weakly minimal puzzles having at least 28 clues. The superset method (and the subset method) is rather slow for low clue weakly minimal puzzles but is quite fast if we start with large subsets. I expect to find some 38 clue weakly minimal puzzles and to get a relative error for 37 clue puzzles between 30 and 40 %.

Superset results

Code: Select all: Computation time: 17 days 8,435,339,866 samples 34,675,000 weakly minimal 28 hits 1,705,488,490 weakly minimal puzzles +----+-----------+------------+----------------+-----------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | Ratio*100 | +----+-----------+------------+----------------+-----------+ | 28 | 34675000 | 1.828e+19 | 1.695e-02 | 4.111e-01 | | 29 | 260569261 | 4.738e+18 | 2.050e-02 | 5.828e-02 | | 30 | 594409232 | 7.205e+17 | 3.006e-02 | 5.114e-03 | | 31 | 542556154 | 6.364e+16 | 5.040e-02 | 2.746e-04 | | 32 | 223603748 | 3.279e+15 | 9.586e-02 | 9.052e-06 | | 33 | 44834730 | 9.961e+13 | 2.081e-01 | 1.852e-07 | | 34 | 4587077 | 1.798e+12 | 5.214e-01 | 2.369e-09 | | 35 | 246108 | 1.930e+10 | 1.510e+00 | 1.893e-11 | | 36 | 7077 | 1.233e+08 | 5.001e+00 | 9.466e-14 | | 37 | 102 | 4.323e+05 | 2.139e+01 | 2.729e-16 | | 38 | 1 | 1.115e+03 | 1.000e+02 | 6.080e-19 | +----+-----------+------------+----------------+-----------+

As always, I'll update the tables from time to time.

by **Afmob** » Wed Oct 02, 2013 7:02 pm

While I haven't made progress with improving the superset method, I started two computations to get the number of minimal clues for 2x4 Sudokus. What is interesting about this is that we know the number of 14 clue minimal puzzles (see here). The 1,673,187 essentially different (ED) grids have 8,536 14 clue minimal puzzles of which 8,280 are ED. Like Denis I don't use a random grid generator but I just run through all ED grids multiple times. That way we should get an estimate of 5,102e-03 14 clue minimals per grid. Note that by using all ED grids instead of a random grid generator I introduce a small approximation error since the ED grids do not have the same number of isomorphic grids.

Subset results:

Code: Select all: Computation time: 15x5 days 113,239,622,973 samples 2,272,264,506 valid 24 hits 52,861,103,785 valid minimal puzzles +----+-------------+--------------+----------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | +----+-------------+--------------+----------------+ | 14 | 22 | 4.740e-03 | 2.132e+01 | | 15 | 83024 | 8.945e+01 | 3.943e-01 | | 16 | 24071822 | 1.412e+05 | 3.301e-02 | | 17 | 1093291951 | 3.848e+07 | 9.040e-03 | | 18 | 10476564748 | 2.476e+09 | 4.645e-03 | | 19 | 24223804651 | 4.389e+10 | 3.226e-03 | | 20 | 14544075578 | 2.371e+11 | 3.012e-03 | | 21 | 2388188309 | 4.283e+11 | 4.528e-03 | | 22 | 109663931 | 2.819e+11 | 1.387e-02 | | 23 | 1356054 | 7.321e+10 | 9.731e-02 | | 24 | 3695 | 8.179e+09 | 1.645e+00 | +----+-------------+--------------+----------------+

Superset results:

Code: Select all: Computation time: 15x5 days 71,980,504,740 samples 3,639,113,023 weakly minimal 21 hits 84,877,654 valid minimal puzzles +----+-----------+--------------+----------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | +----+-----------+--------------+----------------+ | 21 | 750516 | 4.286e+11 | 1.154e-01 | | 22 | 10866369 | 2.821e+11 | 4.033e-02 | | 23 | 32438143 | 7.322e+10 | 2.783e-02 | | 24 | 28991018 | 8.180e+09 | 3.146e-02 | | 25 | 9888802 | 4.464e+08 | 5.547e-02 | | 26 | 1680594 | 1.459e+07 | 1.650e-01 | | 27 | 218815 | 4.222e+05 | 7.587e-01 | | 28 | 39027 | 1.882e+04 | 2.545e+00 | | 29 | 4241 | 5.643e+02 | 5.850e+00 | | 30 | 121 | 4.830e+00 | 1.801e+01 | | 31 | 8 | 1.030e-01 | 4.330e+01 | +----+-----------+--------------+----------------+

The computation will end after 5 days. I'll occasionally update the tables.

by **Afmob** » Mon Aug 17, 2015 11:29 am

I did another multicore-computation to get a better estimation for the number of minimal 26+ clue puzzles. The most noticable difference to the previous computation is the number of minimal 36-clue-puzzles which seems to be larger than expected but the real size is still hard to tell with the relative error being about 37%.

Superset results:

Code: Select all: Computation time: 31x12 days 50,879,850,000 samples 2,863,163,907 minimal 26 hits 1,680,444,669 minimal 26 hits passing UA4 test 76,739,006 valid minimal puzzles +----+------------+--------------+----------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | +----+------------+--------------+----------------+ | 26 | 66522 | 1.480e+15 | 3.877e-01 | | 27 | 1847689 | 1.523e+15 | 9.964e-02 | | 28 | 12258173 | 7.216e+14 | 4.879e-02 | | 29 | 27223658 | 1.658e+14 | 3.767e-02 | | 30 | 23981886 | 1.947e+13 | 4.156e-02 | | 31 | 9374091 | 1.228e+12 | 6.296e-02 | | 32 | 1791689 | 4.400e+10 | 1.303e-01 | | 33 | 184308 | 9.600e+08 | 3.688e-01 | | 34 | 10650 | 1.305e+07 | 1.374e+00 | | 35 | 331 | 1.043e+05 | 7.066e+00 | | 36 | 9 | 7.879e+02 | 3.685e+01 | +----+------------+--------------+----------------+

Another reason was that I made some improvements to my code which are as follows:
- Less calls of RNG:
To get a random subset of a sample I used the Knuth shuffle to get a random permutation of 81 numbers which invoked calling the RNG 80 times per sample. But then I realised that I only needed 26 random, pairwise different numbers with the order of the not chosen numbers being irrelevant. The original shuffling algorithm can easily be modified to do that which invokes calling the RNG only 26 times (instead of 80 times!). I should have realised this back in 2013. :shock:

Note that this can (and should!) also be used for the subset method or the CB generator.
- Adding UA4 test:
A known problem of the superset method is that most of the weakly minimal subsets do not contain any minimal, valid supersets. I did some tests and realised that there were a lot of cases where an UA could not be hit since adding a clue to the subset led to loss of weakly minimality. So before getting all (or up to 10,000) solutions of the weakly minimal subset I get all unhit UA of size 4 and check whether there's an UA which cannot be hit due to loss of minimality. This leads to a speedup of about 10% for 26-clue subsets. The speedup becomes larger with smaller subsets.
- Faster solver for checking weakly minimality:
Most computing time is spent with checking for minimality, so the better the solver the faster the superset method. I had used JSolve (and still use it for getting all solutions) but I recently switched to ZhouSolver after modifying it. This made the program run twice as fast, so definitely a major improvement! Note that it wasn't used in this computation, so the results could be improved without spending more CPU time.

I'll later (probably in a couple of days) make another post to show the impact of the improvements with regards to the subset size.

by **eleven** » Mon Aug 17, 2015 8:26 pm

Afmob,

thanks for the new data and the explanations.
It is always surprising for me, how much faster even already optimized computations can be done.

I noticed that your last 2 results for the 36's don't overlap within the relative errors. How are they defined ? Is it the standard deviation ?

The New Sudoku Players' Forum

Counting minimal puzzles: subsets, supersets, etc.

Difficulty of 18 clue minimals

Re: Difficulty of 18 clue minimals

Re: Difficulty of 18 clue minimals

Re: Difficulty of 18 clue minimals

Re: Difficulty of 18 clue minimals

Counting puzzles

Re: Counting puzzles

Re: Counting puzzles

Minimality of multisolution puzzles

Re: Counting minimal puzzles: subsets, supersets, etc.

Counting weakly minimal & valid puzzles

Counting minimal & weakly minimal puzzles

Counting minimal 2x4 puzzles

Re: Counting minimal puzzles: subsets, supersets, etc.