The Hidden Logic of SudokuDenis BerthierOnline SupplementsClassification results 
© Denis Berthier. All the material in this page and the pages it gives access to are the property of the author and may not be republished or reposted without his prior written permission. 
1) Comparison of classification results for collections
of minimal puzzles

generator 
suexgx.x (topdown)  Allan Barker's (topdown)  suexg14 (bottomup)  Mike Metcalf's (bottomup) 
collection name 
sudogen0_1M 
rabrnd_1M  suexg140_1M

Mike#5

size of sample used (unless other size stated) 
1,000,000 
1,000,000 
1,000,000 
64,000 
mean(#clues) 
24.38 
24.38 
23.87 
23.89 
standard deviation(#clues)  1.12 
1.116 
1.08 
1.08 
skewness(#clues) 
0.08 
0.11 
0.11 

kurtosis(#clues) 
0.007 
0.014 
0.026 

mean(NRCZT) (size of subsample used) 
1.94 
1.946 (50,000) 
1.80 (10,000) 
1.844 (50,000) 
standard
deviation(NRCZT) (size of subsample used) 
1.29 
1.29 (50,000) 
1.24 (10,000) 
1.24 (50,000) 
skewness(NRCZT)  1.01 
1.01 (50,000) 
1.24 (10,000) 
(50,000) 
kurtosis(NRCZT)  0.27 
0.34 (50,000) 
0.92 (10,000) 
(50,000) 
mean(SER)  3.77 
3.77 
3.50 
3.58 
standard
deviation(SER) 
2.42 
2.42 
2.33 
2.34 
skewness(SER)  0.60 
0.60 
0.79 

kurtosis(SER)  1.36 
1.35 
1.08 

correlation coeff
(NRCZT, SER) (size of subsample used) 
0.895 
0.895 (50,000) 
0.898 (10,000) 
0.896 (50,000) 
correlation coeff
(NRCZT, log(#chains)) (size of subsample used) 
0.946 
0.946 (50,000) 
0.946 (10,000) 
0.96 (50,000) 
correlation coeff
(#clues, NRCZT) (size of subsample used) 
0.115 
0.117 (50,000) 
0.096 (10,000) 
0.112 (50,000) 
correlation coeff
(#clues, SER) 
0.120 
0.121 
0.11 
0.094 
max NRCZT (*) 
13 
13 (50,000) 
11 (10,000) 
11 (50,000) 
max SER (*) (size of subsample used) 
9.3 
9.3 
9.2 
9.2 
generator 
suexgx.x (topdown)  Allan Barker's (topdown)  suexg14 (bottomup)  Mike Metcalf's (bottomup) 
collection name  sudogen0_1M  rabrnd_1M 
suexg140_1M  Mike#5 
size of
subcollection used 
1,000,000  50,000  10,000  50,000 
# clues 
mean 
standard deviation skewness  kurtosis # puzzles 
mean 
standard deviation skewness  kurtosis # puzzles  #puzzles x 20 
mean 
standard deviation skewness  kurtosis # puzzles 
mean 
standard deviation skewness  kurtosis # puzzles  #puzzles x 20 
19 
0 
0 
0 
0 
20 
1.41 
0.72 5e5  0.06 44 
0.97 
0.05 (*) 4e5  1.5 3  60 
2.5 
0.5 (*) 0.0  2.0 2 
1.20 
0.46 (*) 16  320 
21 
1.58 
1.04 0.0037  1.52 2,428 
1.73 
1.23 (*) 0.003  0.43 117  2,340 
1.65 
1.00 0.011  0.72 88 
1.64 
1.05 393  7,860 
22 
1.69 
1.13 0.048  1.43 34,548 
1.70 
1.17 0.05  1.76 1,733  34,660 
1.63 
1.15 0.13  1.83 824 
1.65 
1.13 4,032  80,640 
23 
1.77 
1.20 0.22  0.83 172,512 
1.78 
1.19 0.22  1.07 8,611  172,220 
1.70 
1.20 0.42  2.84 2671 
1.74 
1.19 13,603  272,060 
24 
1.88 
1.26 0.38  0.54 342,335 
1.88 
1.26 0.37  0.28 17,216  344,320 
1.81 
1.24 0.45  0.72 3679 
1.84 
1.24 18,335  366,700 
25 
2.01 
1.31 0.28  0.096 297,838 
2.00 
1.30 0.27  0.06 14,905  298,100 
1.91 
1.27 0.20  0.12 2106 
1.98 
1.29 10,439  208,720 
26 
2.17 
1.36 0.008  0.31 122,116 
2.21 
1.39 0.09  0.36 6,054  121,080 
2.06 
1.35 0.04  0.58 550 
2.11 
1.35 2,761  55,220 
27 
2.38 
1.40 0.01  0.52 25,315 
2.37 
1.39 0.01  0.5 1,221  24,420 
2.63 
1.33 0.0004  1.30 71 
2.37 
1.41 406  8,120 
28 
2.64 
1.44 0.0007  0.75 2,686 
2.61 
1.52 0.001  0.03 130  2,600 
2.64 
1.44 (*) 9e5  1.36 9 
2.11 
1.33 (*) 14  280 
29 
2.86 
1.45 1e5  0.82 168 
3.11 
1.45 (*) 9  180 
0 
3.00 
0.00 (*) 1  20 
30 
3.19 
1.10 (*) 4e6  0.14 10 
0.9 
0.0 (*) 4e5  0.21 1  20 
0 
0  0 
all 
1.94 
1.29 1.01  0.27 1,000,000 
1.94 
1.28 30,000 
1.94 
1.28 10,000 
1.844 
1.242 50,000  1,000,000 
generator 
suexgx.x (topdown) 
Allan Barker's (topdown)  suexg14 (bottomup) 
Mike Metcalf's (bottomup) 
collection name  sudogen0_1M  rabrnd_1M 
suexg140_1M  Mike#5 
size of sample used  1,000,000  1,000,000  1,000,000  50,000 
# clues 
mean 
standard deviation skewness  kurtosis # puzzles 
mean 
standard deviation skewness  kurtosis # puzzles 
mean 
standard deviation skewness  kurtosis # puzzles 
mean 
standard deviation skewness  kurtosis # puzzles  #puzzles x 20 
19 
0 
3.0 
0.0 (*) 1 
0 
0 
20 
2.75 
1.70 (*) 7e5  1.08 44 
2.98 
1.94 (*) 8e5  0.76 56 
3.01 
1.99 0.0004  0.25 281 
2.60 
1.61 (*) 16  320 
21 
3.03 
2.00 0.003  0.28 2,428 
3.19 
2.11 0.003  0.20 2,392 
3.02 
2.00 0.012  0.28 8,559 
3.26 
2.16 393  7,860 
22 
3.27 
2.16 0.037  0.50 34,548 
3.27 
2.17 0.036  0.48 33,980 
3.17 
2.12 0.095  0.28 82,423 
3.19 
2.13 4,032  80,640 
23 
3.44 
2.28 0.15  0.88 172,512 
3.43 
2.27 0.15  0.86 171,607 
3.32 
2.24 0.27  0.69 276,719 
3.35 
2.46 13,603  272,060 
24 
3.65 
2.38 0.24  1.21 342,335 
3.63 
2.37 0.24  1.20 342,747 
3.52 
2.34 0.29  1.08 363,806 
3.57 
2.37 18,335  366,700 
25 
3.90 
2.46 0.15  1.48 297,838 
3.90 
2.46 0.15  1.48 298,548 
3.79 
2.44 0.12  1.41 205,938 
3.83 
2.45 10,439  208,720 
26 
4.22 
2.53 0.03  1.68 122,116 
4.23 
2.53 0.03  1.68 122,583 
4.16 
2.52 0.016  1.66 54,493 
4.12 
2.52 2,761  55,220 
27 
4.63 
2.56 0.0006  1.74 25,315 
4.62 
2.56 0.0003  1.73 25,124 
4.58 
2.55 6e6  1.74 7,213 
4.58 
2.58 406  8,120 
28 
5.11 
2.56 0.0009  1.59 2,686 
5.16 
2.51 0.001  1.55 2,798 
5.14 
2.47 0.0002  1.54 538 
4.44 
2.77 (*) 14  280 
29 
5.43 
2.46 0.0001  1.28 168 
5.40 
2.54 8e5  1.40 156 
6.43 
1.84 (*) 4e5  1.57 24 
6.00 
0.00 (*) 1  20 
30 
6.46 
1.74 (*) 2e5  3.6 10 
5,69 
2.02 (*) 9e6  0.22 8 
4.75 
2.45 (*) 0.0  2.0 2 
0  0 
all 
3.77 
2.42 0.60  1.36 1,000,000 
3.77 
2.42 0.60  1.35 1,000,000 
3.53 
2.34 0.79  1.08 1,000,000 
3.567 
2.35 50,000  1,000,000 
2) A controlledbias generator of minimal puzlesThe above classification results are relative to the output of classical topdown or bottomup generators of minimal puzzles. There are now serious reasons to suspect that these generators are biased with respect to the number of clues of these puzzles: the relative proportions of puzzles in the collection with different numbers of clues do not reflect reality. (Red Ed, on the Sudoku Player's Forum, was the first to suggest that the classical generators had a bias.) As, from the above tables, there appears to be a small upward trend of (SER or NRCZT) complexity with respect to the number of clues, the above results may also have some bias with respect to these variables. As the correlation coefficient between the SER or NRCZT rating and the number of clues is very small (0.1), the potential bias with respect to SER or NRCZT is likely to be small also. Nevertheless, one may want statistics based on collections of minimal puzzles that are unbiased, perhaps not in the absolute but at least with respect to these variables. Unfortunately, no generator of minimal puzzles is currently guaranteed to have no such bias and building such a generator with reasonable computation times seems out of reach. I therefore devised another way of proceeding: taking the generators as they are and applying corrections for the bias, if we can estimate it. The method is similar to what becomes now applied in cameras: instead of complex optimisations of the lenses to reduce typical anomalies (such as chromatic aberration, purple fringing, barrel or pincushion distortion, and so on) — optimisations that lead to large and expensive lenses —, some camera makers now accept a small amount of these in the lenses and they correct the result in real time with dedicated software before recording the photo. The main question here is: can we determine the bias of these current generators? Unfortuntely, the answer is negative for the classical topdown or bottomup generators. But there appears to be a medium way between "improving the lens" and "correcting its small defects by software": I devised a conceptually simple modification of the topdown generators such that it allows a precise mathematical computation of the bias and a simple correction procedure. Acknowlegments: Thanks to Eleven for implementing the first modification of topdown suexgx.x compliant with the specification of controlledbias defined below and then several faster versions of it. This allowed to turn the whole idea into reality. Thanks to Paul Isaacson for adapting Brian Turner's fast solver so that it could be used instead of that of suexgcb, thus making it still faster. Thanks to Glenn Fowler (gsf) for providing an a priori unbiased source of complete grids: the full (compressed) collection of their equivalence classes together with a fast decompressor. Thanks also to Allan Barker, Coloin, David P. Bird, Mike Metcalf for discussions and/or various contributions. This informal collaboration via the Sudoku Player's Forum was very productive: due to several independent optimisations, the last version of suexgcb (cbopt, which doesn't retain much of the original suexg code) is 200 times faster than the first. 2.1) A controlledbias topdown generator (available here: suexgcb.c, first accelerated version here: suexgcbopt.c) A standard topdown generator works as follows to produce one minimal puzzle (it has to be iterated n times to produce n minimal puzzles):
Clause 2b makes any analysis very difficlut. Moroever, it also causes the generator to go deeper, i.e. towards puzzles with fewer clues. It thus introduces a strong, uncontrolled bias. Consider therefore the following, modified topdown generator of minimal puzzles, the controlledbias generator. The step described below produces one minimal puzzle (it has to be iterated n times to produce n minimal puzzles):
The only difference is in clause 2b: if we find a multisolution puzzle, instead of backtracking to the previous state, we merely discard the current complete grid and restart the search for a minimal puzzle with another complete grid. Notice that, contrary to the standard topdown algorithm which produces one minimal puzzle per complete grid, the modified algorithm will generally use several complete grids before it outputs a minimal puzzle. The efficiency question is: how many? Experimentations show that many complete grids (approximately 250,000 in the mean) are necessary before a minimal puzzle is reached. But this is a question of efficiency of the generator, not a conceptual problem. Once this algorithm is defined, it can be implemented by a simple modification of the topdown suegx.x (the version of suexg used to build the sudogen0_1M collection), call it suexgcb. The modified generator is indeed much slower than the original one. The purpose here is not speed, but controlled bias and, as mentioned in the acknowlegments, drastic optimisations are possible. The topdown controlledbias generator has the same output as its following "virtual" counterpart. As a result, the topdown controlledbias generator will output minimal puzzles according to the same probability as this virtual counterpart. Repeat until a minimal puzzle has been printed
This virtual generator does the same thing as the controlledbias one, except that, once it has found a minimal puzzle or a multisolution one, instead of stopping, it blindly continues along a useless path until it reaches the empty grid. But this virtual generator is interesting theoretically because it works similarly to the random uniform search defined in section 3.2 below and according to the same transition probabilities and it outputs minimal puzzles according to the probability Pr on the set B of minimal puzzles defined below. Let us now build our formal model of this generator. 2.2) A forest of paths from complete grids to puzzles Let us introduce the notion of a doubly indexed puzzle. We consider only (single or multi solution) consistent puzzles P. The double index of a doubly indexed puzzle P has a clear intuitive meaning: the first index is one of its solution grids and the second index is a sequence (notice: not a set, but a sequence, i.e. an ordered set) of clue deletions leading from this solution to P. In a sense, the double index keeps track of the generation process. Given a doubly indexed puzzle Q, there is an underlying singlyindexed puzzle: the ordinary puzzle obtained by forgetting the second index of Q, i.e. by remembering the solution grid from which it came and by forgetting from which sequence of deletions Q was reached from this solution. Given a doubly indexed puzzle Q, there is also a non indexed puzzle, obtained by forgetting the two indices. Notice that, for a single solution doubly indexed puzzle, the first index is useless as it can be computed from the puzzle; in this case singly indexed and non indexed are equivalent. (In terms of the generator, it could as well output minimal puzzles or couples minimalpuzzleplussolution.) Consider now the following layered structure (a forest of trees with branches pointing downwards), the nodes being (single or multi solution) doubly indexed puzzles:  floor 81 : the N different complete solution grids (considered as puzzles), each indexed by itself and by the empty sequence; notice that all the puzzles at floor 81 have 81 clues;  floor 80: each doubly indexed puzzle Q at floor 81 sprouts 81 branches pointing to floor 80, one for each clue C in Q; the other end of this C branch will be the doubly indexed puzzle obtained from Q by removing clue C and indexed by the same complete grid as Q and by the 1element sequence (C); notice that all the puzzles at floor 80 have 80 clues;  recursive step: given floor n+1 (each doubly indexed puzzle of which has n+1 clues and is indexed by a complete grid that solves it and by a sequence of length 81(n+1)), build floor n as follows: each doubly indexed puzzle Q at floor n+1 sprouts n+1 branches; for each clue C in Q, there is a branch leading to a doubly indexed puzzle R at floor n: R is obtained from Q by removing clue C; its first index is identical to that of Q and its second index is the (81n)element sequence obtained by appending C to the end of the second index of Q; notice that all the doubly indexed puzzles at floor n have n clues and the length of their second index is equal to 1 + (81(n+1)) = 81n. It is easy to see that, at floor n, each doubly indexed puzzle has an underlying singly indexed puzzle identical to that of (81  n)! doubly indexed puzzles with the same first index at the same floor (including itself). This is equivalent to saying that, at any floor n < 81, any singlyindexed puzzle Q can be reached by exactly (81  n)! different paths from the top (all of which start necessarily from the complete grid defined as the first index of Q). These paths are the (81  n)! different ways of deleting one by one its missing 81n clues from its solution grid. Notice that this would not be true for non indexed puzzles that have multiple solutions. This is where the first index is useful. Let N be the number of complete grids. At each floor n, there are: N * 81! / n! doubly indexed puzzles, N * 81! / (81n)! / n! singly indexed puzzles. For each n, there is therefore a uniform probability P(n) = 1/N * 1/81! * (81n)! * n! that a singly indexed puzzle Q at floor n is reached by a random (uniform) search starting from the associated complete grid (its first index) at the top. What is important here is the ratio: P(n+1) / P(n) = (n + 1) / (81  n). This formula is valid globally if we start from all the complete grids, as above, but it is also valid for all the single solution puzzles if we start from a single complete grid (just forget N in the proof above). (Notice however that it is not valid if we start with a subgrid instead of a complete grid.) Now, call B the set of (non indexed) minimal puzzles. On B, all the puzzles are minimal. Any puzzle strictly above B has redundant clues and a single solution. Notice that, for all the puzzles on B and above B, singly indexed and non indexed puzzles are in onetoone correspondence. On the set B of minimal puzzles there is a probabily Pr naturally induced by the different Pn's (and renormalised to sum up to 1) and it is the probability that a minimal puzzle Q is output by our controlledbias generator. It depends only on the number of clues and it is defined, up to a multiplicative constant k, by Pr(Q) = k P(n), if Q has n clues. k must be chosen so that the probabilities of all the minimal puzzles sum up to 1. But we need not know k. What is important here is that, by construction of Pr on B (a construction which models the workings of the controlled bias generator), the fundamental relation Pr(n+1) / Pr(n) = (n + 1) / (81  n) holds for any two minimal puzzles, with respectively n+1 and n clues. For n < 41, this relation means that a minimal puzzle with n clues is more likely to be reached from the top than a minimal puzzle with n+1 clues. More precisely, we have: Pr(40) = Pr(41), Pr(39) = 42/40 * Pr(40), Pr(38) = 43/39 * Pr(39). Repeated application of the formula gives Pr(24) = 61.11 Pr(30) : a puzzle with 24 clues has ~ 61 more chances of being output than a puzzle with 30 clues. This is indeed a strong bias. A nonbiased generator would give the same probability to all the minimal puzzles. The above relation shows that the controlled bias generator:  is unbiased when restricted (by filtering its output) to nclue puzzles, for any fixed n,  is biased towards puzzles with fewer clues,  this bias is well known. Moreover, the puzzles produced by the controlledbias generator are uncorrelated, provided that the complete grids are chosen in an uncorrelated way. As we know precisely the bias with respect to uniformity, we can correct it easily by applying correction factors cf(n) to the probabilities on B. Only the relative values of the cf(n) is important: they satisfy cf(n+1) / cf(n) = (81  n) / (n + 1). Mathematically, after normalisation, cf is just the relative density of the uniform distribution on B with respect to the probability distribution Pr. [Notice that a classical topdown generator is still more biased in favour of puzzles with fewer clues because, instead of discarding the current path when it meets a multisolution puzzle, it backtracks to the previous floor and tries again to go deeper.] 2.3) Computing unbiased means and standard deviations of a variable X using a controlledbias generator In practice, how can one compute statistics of minimal puzzles based on a (large) sample produced by a controlledbias generator, using an uncorrelated source of complete grids? If we consider any random variable X defined (at least) on minimal puzzles, let:  on(n) be the observed number of puzzles with n clues in the sample,  E(X, n) be the observed mean value of X for puzzles with n clues in the same sample,  sd(X, n) be the observed standard deviation of X for puzzles with n clues in the same sample. The raw (biased) mean of X is classically estimated as: sum[E(X, n) * on(n)] / sum[on(n)] (theorem on the additivity of the mean values). The real, unbiased mean of X must be estimated as (this is a mere weighted average): realmean(X) = sum[E(X, n) * on(n) * cf(n)] / sum[on(n) * cf(n)]. Similarly, the raw (biased) standard deviation of X is classically estimated as: sqrt{sum[sd(X, n)^2 * on(n)] / sum[on(n)]} (theorem on the additivity of the variances  beware, not the standard deviations!). And the real, unbiased standard deviation of X must be estimated as (this is merely the standard deviation for a weighted average): realsd(X) = sqrt{sum[sd(X, n)^2 * on(n) * cf(n)] / sum[on(n) * cf(n)]}. These formulæ show that the cf(n) sequence needs be defined only modulo a multiplicative factor. It is convenient to choose cf(26) =1. This gives the following sequence of correction factors (in the range 1931, which includes all the puzzles of all the samples we have obtained with all the random generators considered here): cfsequence[19...31] = [0.00134 0.00415 0.0120 0.0329 0.0843 0.204 0.464 1 2.037 3.929 7.180 12.445 20.474] It may be shocking to consider that a 30clue puzzle in a sample must be given a weight 61 times greater than a 24clue puzzle, but that's how it is. A consequence of all this is that unbiased statistics for the mean number of clues of minimal puzzles must rely on extremely large samples with sufficiently many 29clue and 30clue puzzles. Practical computations below show that the interval of interest is [22, 30]. 2.4) Very small sensitivity of the controlledbias generator to the source of complete grids The source of (sufficiently random) complete grids has a very limited impact on the output of the controlledbias generator. This nice property has been tested with different sources of complete grids. See section 4.2. It is easily understandable: as two thirds (in the mean) of a complete grid are deleted in the deletion phase, any structure that might have existed in the complete grid is washed away by this deletion phase. 2.5) A remark on bottomup generators A similar analysis for bottomup generators is more difficult, perhaps even unfeasible, because these generators are not purely bottomup. Starting with 0 clues, they add clues until they reach a single solution puzzle, but after that they delete clues until they reach a minimal puzzle. Contrary to topdown generators, there doesn't seem to be an easy way of modifying them to get some form of controlled bias. Moreover, as bottomup generators are more biased than topdown, it doesn't seem useful to start from them if one wants to build a modified algorithm with controlled bias: the correction factors would have to be very large. 
3) Unbiased classification of minimal puzlesThe controlledbias method works in practice, although minimal puzzle generation was very slow before various optimisations of the generator were made. The algorithm can be accelerated by deleting the first 46 (or even 48) clues without doing any intermediate test, because the probability of obtaining an nclue minimal puzzle with n > 35 (or even n > 33) is very small (as shown by the first 180,000 puzzles generated without this optimisation, in which the maximum number of clues was 31). The resulting accelerated algorithm is 6 times faster (20 times if we consider only the deletion part). After generating more than 6.5 millions of minimals, only two 32s and no minimal puzzle with more than 32 clues has been found. I first used the method on a collection of 500,000 puzzles generated by the controlledbias generator suexgcb. (The first 180,000 puzzles were generated before the algorithm was accelerated; the distributions before and after the above 46clue acceleration have been checked to be the same). Apart from the distribution of clues, which is more sensitive to fluctuations, the various unbiased averages obtained are very stable. After the above computations were done, it was suggested that the source of complete grids I had used (the internal suexg generator) might be a source of bias (this will be discussed in section 4.2). Alternative sources of complete grids were then tested. A final solution to this problem was reached when Glenn Fowler (gsf) made available, in a compressed form of reasonable size, a full list of all the (equivalence classes of) complete grids and a fast decompressor. Not only did this anihilated any doubts about the source of complete grids, it also allowed an important speed improvement. This is of course an uncorrelated source of complete grids (more precisely: essentially uncorrelated, i.e. uncorrelated modulo isomorphims). Technically, Unix piping is used to input an integer number of full scans of gsf's collection into the (deletor part of the) suexgcb controlledbias generator. The results reported in this section are therefore guaranteed to be unbiased. Subsection 4.2 gives the results when the suexg internal generator of complete grids is used instead of gsf's collection. It shows that the controlledbias generator is relatively insensitive to the source of complete grids: even a strong bias in this source (suexg is known to generate complete grids with ~ 20% more minimals than an ubiased source) has almost no effect on the statistics of minimals. 1.1) Final results using an a priori unbiased uncorrelated source of complete grids (with the final version of the controlledbias generator: cbopt) The final version of the controlledbias generator is available here: cbopt Compile it with: gcc O3 Wall cbopt o cbopt.exe Use it as follows: ./sudoku q f%v *.sudz  ./cbopt.exe where "sudoku" is gsf program (available on his web pages) and the *.sudz are the various gsf bands of complete grids. The reults below were obtained with a sample of 5,926,343 uncorrelated minimal puzzles, corresponding to 279 full scans of gsf's collection. Remark: there is some (very small: 0.03% in the mean) discrepancy in the number of tries, whether one counts them directly in the algorithm (as I did when I needed this datum, i.e. only for the estimated number of minimals, section 4.1.4) or one multiplies the number of gsf scans with the number of gsf grids. This discrepancy is so small that it would have been harmless even if it had not been random. But, for some time, I have been wondering about the cause. I have found. UNIX piping is far from perfect: there is some (very small) random data leak. In the present case, a very small percentage of the complete gsf grids are lost before reaching the deletor part of suexgcb. This has no impact on the following results, as one can consider this data leak as a (real, not pseudo) random sampling of the input complete grids, with high probability of acceptance. The leak seems to be different on different machines. It is very low on my Mac (0.01%) and a little higher on other Unix machines I've been able to use occasionally. The positive aspect of this difference is, I could check that the results don't depend on the leak. 3.1.1) Global results At the risk of some redundancy with section 2.3.1, it is interesting to compare the global results for the (now three) main kinds of generators with the real (estimated) values.
(*) comparison of maximum values for samples of different sizes is not meaningful It can be seen that, in all these cases, the numberofclues skewness and kurtosis are close to 0, which means that the general shape of each of these distributions is close to that of a Normal (but, of course, they are not continuous). 3.1.2) The real number of clues of minimal puzzles controlledbias mean = 25.667 controlledbias standarddeviation = 1.116 real (estimated) mean = 26.577 real (estimated) standarddeviation = 1.116 The real, unbiased value for the mean number of clues of minimal puzzles is 0.9 more than the raw mean number given by the controlledbias generator. The controlledbias and real (estimated) numberofclues distributions are given by the following table:
The vast majority of minimal puzzles produced by the controlledbias algorithm is still in the range [23  28] clues, but the real distribution one can deduce from it is notably different from its raw distribution. For n < 26, it has fewer occurrences, for n ≥ 26 it has more occurrences. 3.1.3) The real NRCZT rating (mean, standard deviation, skewness and kurtosis) as a function of the number of clues Remember that, for any fixed number of clues, the controlledbias generator is completely unbiased. As a result, each row of the the table below gives both the controlledbias and the real values for the nclue NRCZT rating. Only the global mean value, standard deviation, skewness and kurtosis have to be computed differently.
(*) values based on small samples are not meaningful (**) although the standard deviation depends on the number of clues, this dependency is small and we have used the formula in section 3.3. Which gives: controlledbias mean(NRCZT) = 2.217 controlledbias standarddeviation(NRCZT) = 1.35 real mean(NRCZT) = 2.449 real standarddeviation(SER) = 1.39 These values are identical to those obtained in case the source of complete grids was the suexg internal generator. Conclusion: there seems to be a (non absolute) barrier of complexity such that, when the number of clues (n) increases:  the nclue mean complexity increases;  the proportion of puzzles away from the nclue mean increases; but  the proportion of puzzles far below the nclue mean increases;  the proportion of puzzles far above the nclue mean decreases. Graphically, the nclue distribution looks like a wave; when n increases, the wave moves to the right, with a longer left tail and a steeper right front. 3.1.4) The real SER rating (mean, standard deviation, skewness and kurtosis) as a function of the number of clues Here again, we use the fact that, for any fixed number of clues, the controlledbias generator is completely unbiased. As a result, each row of the the table below gives both the controlledbias and the real values for the nclue SER. Only the global mean value, standard deviation, skewness and kurtosis have to be computed differently. Computations for the SER were done on a subsample of only 1,380,962 puzzles (corresponding to 65 full scans of gsf's collection).
(*) values based on small samples are not meaningful (**) although the standard deviation depends on the number of clues, this dependency is small and we have used the formula in section 3.3. Which gives: controlledbias mean(SER) = 4.29 controlledbias standarddeviation(SER) = 2.48 controlledbias kurtosis(SER) =  1.70 real mean(SER) = 4.73 real standarddeviation(SER) = 2.49 These values are identical to those obtained in case the source of complete grids was the suexg internal generator. The conclusions obtained for the NRCZT rating could be repeated unchanged for the SER rating. 3.1.5) The estimated mean number of minimal nclue puzzles per complete grid Finally, we can estimate the mean number of nclue minimal puzzles per complete grid. This is not useful for our complexity computations, but it has been a longstanding open question in the Sudoku world.
which (still with 0.065% relative error):  multiplied by the number of complete grids (6,670,903,752,021,072,936,960) gives an estimated total of 3.1055e+37 minimal puzzles  multiplied by the number of non isomorphic grids (5,472,730,538) gives "only" an estimated total of 2.5477e+25 non equivalent minimal puzzles. 3.2) Relative insensitivity of the controlledbias generator to the source of complete grids This subsection gives the results when suexg internal generator of complete grids is used instead of gsf's collection. It shows that the controlledbias generator is relatively insensitive to the source of complete grids: even a strong bias in this source (suexg is known to generate complete grids with 20% more minimals than an ubiased source) has almost no effect on the collection of cb minimals. 3.2.1) The number of clues of minimal puzzles controlledbias average = 25.65 controlledbias standarddeviation = 1.113 real (estimated) average = 26.56 real (estimated) standarddeviation = 1.113 The real, unbiased value for the mean number of clues of minimal puzzles is 0.9 more than the raw mean number given by the controlledbias generator. Above all, it is instructive to compare the mean values obtained for different generators with the estimated real value:
The following estimates are merely the product of the observed distribution and the correction factors, namely on(n) * cf(n) (normalised, of course, by sum(on(n) * cf(n)). Figures in this section, especially for the tail of the distribution, should therefore be taken with care, due to the relatively small sample size.
* values based on few data are not reliable. ** the number of digits given here is obviously above the precision allowed by the sample. 3.2.2) Correlation coefficients #clues vs SER = 0.20 #clues vs NRCZT = 0.19 SER vs NRCZT = 0.90 3.2.3) Conclusions Form the above results, we can conclude that, when we use a controlledbias genereator of minimal puzzles, the source of complete grids leads to very small differences in the controlledbias and the unbiased statistics. This can be understood on the basis of the results in section 2 relative to:  the very weak correlation between the number of clues and the SER or NRCZT ratings,  the small trend for increasing SER or NRCZT with increasing number of clues. 3.3) The real nrczt distribution of minimal puzzles Using the results obtained with the controlledbias generator, we can now give the real (nrczt) complexity distribution of the minimal puzzles, which may be considered the ultimate goal of this section. It is interesting to compare it with the distributions obtained with different kinds of generators (bottomup, topdown, controllledbias).
* values based on a small subsample are not reliable. These distributions show very clearly the complexity bias of the three kinds of generators. All these distributions have the same two modes, at L1_0 and at L3, as the real distribution. It can be seen that when one moves from bottomup to topdown to controlledbias to real, the distribution moves progressively to the right. This displacement towards higher complexity occurs mainly at the first nrcztlevels, after which it is only very slight. In any cases:  more than 99% of the puzzles can be solved with whips of maximal length 7,  more than 99.9% of the puzzles can be solved with whips of maximal length 9. 