The New Sudoku Players' Forum

by **dobrichev** » Wed Jul 31, 2013 9:26 pm

These are the corrected counts for the grid with 20 17s

Code: Select all: 20 17 294 18 32748 19 12141180 20

by **coloin** » Wed Jul 31, 2013 11:14 pm

Estimated counts for minimal puzzles in the 20-17 grid...........

Code: Select all: +----+-----------+--------------+------------+ | Cl | Count | E(nr/grid) | E(rel err) | +----+-----------+--------------+------------+ | 17 | 24 | 2.1983e+001 | 39.97% | | 18 | 56 | 2.9844e+002 | 26.96% | | 19 | 963 | 3.2332e+004 | 6.60% | | 20 | 52345 | 1.2107e+007 | 0.83% | +----+-----------+--------------+------------+ [blue]

I am very relieved that the results fit very easy within the rel. error ...... !

this has implications now for the total number of 18-puzzles - Afmob may well be right !

C

Website · by **denis_berthier** » Thu Aug 01, 2013 1:39 am

Afmob wrote:As for the results, one can often find situations where one method is better than the other and vice versa.

For high numbers of clues, subset is "probably" better.
In all the other cases, I can't see how subset or superset could be better if you didn't erroneously discard the sampling errors due to your small numbers of complete grids. Starting from only 100k (subset) or 10k (superset) grids sets a bound on the precision of any calculations you can do; the level of precision claimed for your error estimates is much below this lower bound and therefore not valid.

Afmob wrote:For example if I look at the relative error for the number of 22 clue minimals you got a relative error of 1.23% and blue got about 0.05% which is a major difference. Note that I choose blue's results since they have no sample error and the computation time is not as large is mine was.

As I said in my previous post, if we concentrate on low clues, the controlled-bias generator can be made drastically much faster by increasing the number of clues deleted from the start without checking if the resulting puzzle is minimal.

by **Afmob** » Thu Aug 01, 2013 3:56 am

denis_berthier wrote:Starting from only 100k (subset) or 10k (superset) grids sets a bound on the precision of any calculations you can do.

Please read my post again. I did not only use 100k or 10k grids but about 60.2 billion (subset) and 2.1 billion (superset) different random unbiased grids otherwise I wouldn't have made this large computation. The only sample error I introduce is that I use each grid 10 times so that the generator takes up only a small amount of the computation time.

by **blue** » Thu Aug 01, 2013 4:02 am

Hi Denis,

denis_berthier wrote:
Afmob wrote:For example if I look at the relative error for the number of 22 clue minimals you got a relative error of 1.23% and blue got about 0.05% which is a major difference. Note that I choose blue's results since they have no sample error and the computation time is not as large is mine was.

As I said in my previous post, if we concentrate on low clues, the controlled-bias generator can be made drastically much faster by increasing the number of clues deleted from the start without checking if the resulting puzzle is minimal.

I'm not sure how low you mean when you say "low clues", but if we focused on the size 22 estimate, the upper limit on the speed that you could achieve using the controlled bias method, is the speed that you would get by choosing random size 22 subgrids of random grids, and checking them for being valid puzzles. Note: I'm ignoring the time to check whether the valid cases are also minimal, which is negligible in comparison, and also the time to generate the random samples.
From the number of minimal 22's per grid, you can calculate the average number of (grid, size 22 subgrid) samples that you need to test before finding a valid 22. It''s choose(81,22)/(1.6 * 10^11), or about 230,000,000 samples. In order to get an relative error of 0.05% in the estimate (one part in 2000), you would need to run until you had 2000*2000 = 4,000,000 "hits". The required number of samples then, would be around 9.2 * 10^14. If you said that you could check 120,000 22's per second, for being valid puzzles, the total time required, would be around 2.1 million CPU hours. With my "(size 30) subset method" code, it took 300 hours to get that degree of precision. If a 1% relative error was acceptable, then both times would drop by a factor of 400, but the ratio would remain the same.

Regards,
Blue.

Website · by **denis_berthier** » Thu Aug 01, 2013 4:13 am

Afmob wrote:
denis_berthier wrote:Starting from only 100k (subset) or 10k (superset) grids sets a bound on the precision of any calculations you can do.

Please read my post again. I did not only use 100k or 10k grids but about 60.2 billion (subset) and 2.1 billion (superset) different random unbiased grids otherwise I wouldn't have made this large computation. The only sample error I introduce is that I use each grid 10 times so that the generator takes up only a small amount of the computation time.

OK, I had overlooked this part of your post.

However, my main objection, relative to the high inefficiency of the method for computing the mean of other random variables still holds.

Website · by **denis_berthier** » Thu Aug 01, 2013 4:45 am

Hi Blue,

blue wrote:
denis_berthier wrote:
Afmob wrote:For example if I look at the relative error for the number of 22 clue minimals you got a relative error of 1.23% and blue got about 0.05% which is a major difference. Note that I choose blue's results since they have no sample error and the computation time is not as large is mine was.

As I said in my previous post, if we concentrate on low clues, the controlled-bias generator can be made drastically much faster by increasing the number of clues deleted from the start without checking if the resulting puzzle is minimal.

I'm not sure how low you mean when you say "low clues", but if we focused on the size 22 estimate,

I consider 22 as extremely low: 4 standard deviations below the real mean. But, your interpretation of low is explainable in the context of the above discussion.

In one of the last posts p. 43 of the pdf in the "real distribution" thread, I wrote that choosing a random grid (time ~0), randomly deleting 81-n candidates (again time ~0) would produce a minimal puzzle once in 2.2946e+08 cases for n=22 (which coincides with your estimate).
So, in this extreme case, you're probably right.

Indeed, I've never been very interested in the extreme values*, the main purposes of my brief incursion into the domain of puzzle generation being to compute the distributions of various random variables - a goal for which the subset/superset method is totally unfit.
For me, as it is only very weakly correlated with the difficulty of a puzzle (by whichever method you measure it), the number of clues has never been a goal in itself.

(*) but I appreciate that we now have good results for them, thanks to you and Afmob.

by **Red Ed** » Thu Aug 01, 2013 8:46 am

denis_berthier wrote:... to compute the distributions of various random variables - a goal for which the subset/superset method is totally unfit.

A fairer summary would be that subset/superset methods are advantageous in the computation of "cheap" random variables, whereas path probing (controlled bias generation) is advantageous for "expensive" random variables. Further, subset/superset methods are especially powerful in the tails of the distribution, whereas path probing is competitive (or better if the random variable is sufficiently expensive) around the centre or in computation of the overall mean.

I would recommend the continued use of subsets/supersets in this thread, given that the focus here is on the whole number-of-clues distribution.

Website · by **denis_berthier** » Thu Aug 01, 2013 9:35 am

Red Ed wrote:
denis_berthier wrote:... to compute the distributions of various random variables - a goal for which the subset/superset method is totally unfit.
A fairer summary would be that subset/superset methods are advantageous in the computation of "cheap" random variables, whereas path probing (controlled bias generation) is advantageous for "expensive" random variables.

No. Once more, this is ignoring the difference between generating a sample and using it.
Generation is a one shot business. And, considering the numbers of puzzles generated by each method, I'd say that this business is over (and indeed much beyond what's useful) as long as distributions of RVs are concerned.
Use has to be repeated for every RV.
The 500x computation time ratio is true of "cheap" random variables as well as of "expensive" ones. When you have to repeat a computation billions instead of millions of times, it is never "cheap".

Red Ed wrote:subset/superset methods are especially powerful in the tails of the distribution

OK. And it's great to have these results (even though they are useless for the previous purpose).

by **Red Ed** » Thu Aug 01, 2013 10:54 am

denis_berthier wrote:Generation is a one shot business. And, considering the numbers of puzzles generated by each method, I'd say that this business is over (and indeed much beyond what's useful) as long as distributions of RVs are concerned.

Fair enough, although to my taste it's not over because, for example, I'm interested in estimates for the total number of 18s and 35s+.

by **Afmob** » Fri Aug 02, 2013 10:53 am

I've started another large parallel computation which will run for 3 days. The goal is to find a better estimate for the number of 18 clue minimals. At first the idea was to use eleven's idea and check some random grids for all 18 clue minimals which is the same as the superset method starting with an empty subset. The problem with this approach is that we would only use a small number of samples (< 10,000) and that the time to analyze a sample can vary between minutes and hours.

But if the method is similar to the superset method why not use a larger starting subset to increase the number of samples? So I did this, tested several starting sizes (between 2 and 5) and took the one with the best results after 12 hours which was 3. We should get more than 200,000 samples.

To get some minimal UA I did not compute the solutions of the subset but I just took the solution grid and looked for UA by removing tuples of numbers and boxes. Also this time I don't check for minimality at every level but only when a valid puzzle has been found. Furthermore I stop adding numbers after 18 clues.

Superset results:

Code: Select all: Computation time: 31x72 hours 235,091 samples 235,091 size 3 subsets 814 valid minimal puzzles +----+-------+------------+----------------+ | Cl | Count | E(nr/grid) | E(rel err)*100 | +----+-------+------------+----------------+ | 18 | 814 | 3.620e-01 | 5.813e+00 | +----+-------+------------+----------------+

I will update the table on a daily basis. I expect to get the relative error below 5% but I don't expect to find a 17 clue minimal.

by **Red Ed** » Fri Aug 02, 2013 4:34 pm

Can we change terminology a bit?

initial subset

seed pattern

seed

The more interesting posts I read, the more I realise that "(initial) subset" risks confusion with the subsets/supersets that are generated from it.

by **Afmob** » Mon Aug 05, 2013 8:21 am

The 18 clue computation has just finished.

The number of 18 clue minimals is even smaller than I've imagined. Sadly, I didn't get the relative error below 5% but that is due to some large clusters like this one:

Hidden Text: Show

Doing this kind of computation to get an estimate for the number of 17 clue minimals won't be useful since we would only get 1 or 2 minimals (if any at all), so the relative error would be way too large.

by **eleven** » Mon Aug 05, 2013 11:51 am

Nice to see, that my 2 billion estimate was that good

Website · by **denis_berthier** » Tue Aug 06, 2013 5:35 am

#clues vs difficulty

Hi, Blue & Afmob

It is known that there is no relation between the number of clues and the difficulty of a puzzle, in the sense that the correlation coefficient between the number of clues and the SER or W rating is about 0.12 (which is generally considered as no meaningful correlation). (See the pdf pages in the "real distribution" thread.)

However, It is also known that:
- the 17s are generally easier than the mean,
- the mean number of clues for the hardest is less than the mean.
(This isn't contradictory with the above, as none of these collections can play any role in computing the correlation coefficient: they are much too small wrt to the whole set of puzzles.)

What can you say about the mean SER for the 18s obtained from your computations ?

More generally (but this may be a huge computation, due to correlation), how does the mean SER or the SER distribution vary with the #clues far from the mean ?

The New Sudoku Players' Forum

Counting minimal puzzles: subsets, supersets, etc.

20x17 #puzzles corrected

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

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Re: Comments on my computations

Parallel superset computation

Super seeds supercede *sets subsets

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

#clues vs difficulty