## The Sudoku grey zone

Advanced methods and approaches for solving Sudoku puzzles

### Distribution of clues in the grey zone

Distribution of clues in the grey zone

This question arose in another thread.

I haven't defined the grey zone in a very precise way. Depending on how I make it more precise, SER >= 9.0 or W>=9, different calculations can be done but, as long as the number of clues is concerned, they don't lead to significantly different results.

If I consider the whole collection of 5,926,343 puzzles generated by the controlled-bias generator, 1258 have their W rating >= 9.
The raw distribution of clues for them is as follows:

Code: Select all
`nb-clues   nb-instances  %19         020         021         022         023         22            1.724         106           8.425         306           24.326         415           33.027         288           22.928         102           8.129         17            1.430         2             0.231         032         033         034         035         0mean= 25.97standard-deviation= 1.20`

If I consider only the the first 3,037,717 for which I had computed the SER, 5615 have their SER >= 9.0. The raw distribution of clues for them is:

Code: Select all
`nb-clues   nb-instances    %19         020         021         022         2               0.0423         46              0.824         416             7.425         1319            23.526         1915            34.127         1380            24.628         440             7.8329         90              1.630         7               0.131         032         033         034         035         0mean= 26.05standard-deviation= 1.15`

For comparison, I recall the data for the whole cb-sample (see p.43 of the pdf in the "real distribution" thread):

Code: Select all
`nb-clues  nb-instances     %               20        2                3.7e-05         21        164              0.0027          22        6,651            0.1124          23        110,103          1.858         24        704,089          11.88        25        1,814,413        30.62         26        2,002,349        33.79         27        1,007,700        17.00         28        247,259          4.172         29        31,449           0.531         30        2,088            0.0352       31        74               0.00125       32        2                3.37e-05     mean= 25.67standard-deviation= 1.12`
denis_berthier
2010 Supporter

Posts: 1253
Joined: 19 June 2007
Location: Paris

### W and gW ratings in the grey zone

W and gW ratings in the grey zone

Long ago, I've shown that the W and gW ratings are rarely different when the W rating is finite and, when they differ, the difference is small (W-gW = 1 or 2).
Indeed, for the 5,926,343 puzzles I generated with the controlled-bias generator (all of which have finite W), there was a difference in only 0.23% cases.
In this post, I'll use raw stats for the cb-collection (I won't compute unbiased stats from them) - but this is OK as I'm only interested in orders of magnitude.

If I define the grey zone as the set of puzzles with W >= 9 (*), then the grey proportion in the above collection is only 0.021%. But this is still 1258 puzzles, enough to do some stats.
* a definition stricter (**) than what I first proposed in terms of SER >= 9, and more consistent with my approach.
** Strictly speaking, it is stricter on the lower side but broader on the upper side (no SER < 10.5 restriction here), but this will play no role here. In particular, this includes puzzles not in T&E(1), but these are still rarer (about 1 in 30,000,000 puzzles, i.e. about 0.016% of the grey puzzles) and they can therefore play no significant role in the global stats for the grey zone.

Now, we can ask: how often do the W and gW ratings differ in the grey zone? As the grey zone is a very small subset of the minimal puzzles, the result could be very different from that obtained for the whole collection.
And it is indeed very different: 31.8% (instead of 0.23%).
That it is larger is not really surprising, as the possibilities for extending a partial chain with a right-linking g-candidate when it can't be extended with a candidate increase with the length of the partial chain. The new thing is, the difference is now quantified.
What doesn't change is the maximum difference between W(P) and gW(P) for a puzzle P: 2.
As any rating system, the W and gW ratings can only be meaningful only statistically and a small difference in rating is not very meaningful. This entails that, even in the grey zone, the W rating remains in the mean a good estimate of the difficulty of a puzzle.

How does this result change if we consider a still stricter subset, i.e. W>=10 (0.0062% of the cb-collection)? We get 30.1%, not significantly different, considering the small size of the resulting sample.
denis_berthier
2010 Supporter

Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext