The New Sudoku Players' Forum

[JPF]

Number of puzzles with c clues

As there are Ng = 6.67e21 differents grids, the number of puzzles with c clues (with at least one solution) is :
N(c) = 81 ! / ( c ! * (81-c) ! ) x Ng.
Let’s call N(c,k) the number of puzzles with c clues and k solutions.

By simulations, we can estimate the ratio ρ of valid puzzles with c clues:
ρ = N(c,1) / N(c)

With the estimation of ρ, we can get the estimation of N(c,1) = number of valid puzzles with c clues

Here are the estimated values of ρ as percentage ; 1000 simulations for each value of c

Code: Select all

        c      ρ (%)   
                                                           
       28-     <1                                                               
       29       1                                                               
       30       1                                                               
       31       2                                                               
       32       4                                                               
       33       7                                                               
       34       8                                                               
       35      11                                                               
       36      17                                                               
       37      21                                                               
       38      27                                                               
       39      31                                                               
       40      35                                                               
       41      41                                                               
       42      46                                                               
       43      50                                                               
       44      56                                                               
       45      60                                                               
       46      64                                                               
       47      70                                                               
       48      69                                                               
       49      76                                                               
       50      78                                                               
       51      82                                                               
       52      83                                                               
       53      87                                                               
       54      89                                                               
       55      89                                                               
       56      92                                                               
       57      91                                                               
       58      95                                                               
       59      95                                                               
       60      96                                                               
       61      96                                                               
       62      98                                                               
       63      99                                                               
       64      99                                                               
       65      99                                                               
       66      99                                                               
       67      99                                                               
       68+    >99   



For example, the number of valid puzzles with 35 clues is roughly :
0.11 x 81 ! / (35 ! x 46 !) x 6.67e21 = 7.5e43

Again, those numbers are "estimations", based on a limited number (1000) of simulations.

JPF

[Red Ed]

If there really are 10^16 puzzles ...

I'm sure you meant to say minimal puzzles there. I wouldn't normally nit-pick (mmm... well...) but it's important to distinguish between the hard problem of estimating the number of minimal puzzles and the easy problem of estimating the number of puzzles in total.

I take it back: the minimal puzzles problem isn't so hard after all. SG had the right idea when he talked suggested considering puzzle trees. Let's suppose you really could arrange all the subgrids (puzzles and pseudopuzzles) of a given solution grid into a big tree structure, with each subgrid at "level C" (those with C clues) having a unique parent at level C+1. Level 81 is the solution grid and is the root of the whole tree. For any subgrid X in the tree, let m(X) be the number of its children that are minimal proper puzzles (m>0 only below level 35ish) and let N(X) be the (actual, not number of) children that are non-minimal proper puzzles. We won't need to count the number of non-proper, i.e. multiple-solution children. Then the number of minimal proper puzzles below X is m(X) + sum_{Y in N(X)}( nr minimal proper puzzles below Y ), which could in principle be calculated recursively. In practice, you can't do such a big recursion, so you need to average lots of unbiased estimates. In that case, you would pick a random Y in N(X) and calculate m(X) + |N(X)|*( nr minimal proper puzzles below Y ), which again is recursive but in this case is dead cheap as it has no fan-out. OK, but we don't have a tree of subgrids, we have a directed acyclic graph. This means we end up counting each node at level C multiple times; W*W-C times, in fact. So we just need to divide by that quantity at each level in the recursion and we'll get the unbiased estimate we needed. Take the average, and we're done.

Each estimate takes several seconds to calculate (with my rubbish code), so I've not yet got an answer that looks like it's converged, but early on in the experiment I'm getting about 10^16 minimal puzzles per grid on average, with about 10^15 for the MC grid in particular. I'll let you know tomorrow if the figures stabilise overnight.

[Ocean]

Right. It's possible to get a reasonable estimate of the the number of minimals, provided the following conjectures are true:

Conjecture 1: The number N(C-1) of valid subgrids with C-1 clues equals N(C-1)=Sum(r(C)/(82-C)); where r(C) is the number of removable clues in a valid sudoku with C clues, and the sum is taken over all valid C-sudokus in all grids.

Conjecture 2: The number M(C-1) of minimal sudokus with C-1 clues is equal to M(C-1)=Sum(m(C)/(82-C)); where m(C) is the number of removable clues in a C-grid that leads to a minimal sudoku with C-1 clues, and the sum is taken over all valid C-sudokus in all grids.


If we instead let r(C) and m(C) represent average values, we get the simple recursive formulas:

N(C-1)=N(C)*r(C)/(82-C))
M(C-1)=N(C)*m(C)/(82-C))

[Red Ed]

(( Clarification: W=9 in my previous posting. Sorry, that was a hangover from verifying the method against the 2x2 case. ))

Ocean --- I agree with those conjectures/formulae, which are a nice concise way of describing my method. It might have been interesting if I had kept the r(C) and m(C) stats built up during the tree search, but maybe I'll leave that for someone else now.

Overnight, the average of the unbiased estimates tended towards ~6.6e15 minimal puzzles per grid (over all grids), with the figure for the canonical grid not being significantly different to that. However, I'm quite sure that this hasn't converged since, regarded as a random variable (call it E), the individual estimates are all over the place. In fact, log(E) appears to be normally distributed with mean ~32 and variance ~9.8 (from the trials so far), suggesting that the true mean of E may be exp(32+9.8/2) = just over 1e16. In any case, the estimates previously posted by coloin, ravel and others appear to be quite close to the mark. Well done, people.

[JPF]

Number of valid puzzles with c clues. (2)


I know that this thread is for minimal puzzles,
but I think these numbers could be of interest anyway.

I redid the calculations of my previous posting but with more trials (10000, for each value c = number of clues).

I only kept the values of c such that : np(1-p)>20
n: number of trials
p: (estimated) average probability of a valid puzzle with c clues

Here are the interval of confidence [N1, N2] (probability = 95%) for the number of valid puzzles with c clues.
Of course, these calculations assume that my generator is unbiased...

Code: Select all

  Clues        N1           N2
                                                 
     28     3.7E+40     9.3E+40                                                 
     29     2.0E+41     3.5E+41                                                 
     30     8.8E+41     1.3E+42                                                 
     31     3.0E+42     3.9E+42                                                 
     32     7.7E+42     9.5E+42                                                 
     33     2.0E+43     2.3E+43                                                 
     34     4.3E+43     4.9E+43                                                 
     35     7.7E+43     8.6E+43                                                 
     36     1.4E+44     1.5E+44                                                 
     37     2.0E+44     2.2E+44                                                 
     38     2.9E+44     3.1E+44                                                 
     39     4.0E+44     4.2E+44                                                 
     40     4.8E+44     5.1E+44                                                 
     41     5.6E+44     5.8E+44                                                 
     42     5.9E+44     6.2E+44                                                 
     43     5.9E+44     6.1E+44                                                 
     44     5.7E+44     5.9E+44                                                 
     45     5.0E+44     5.2E+44                                                 
     46     4.2E+44     4.4E+44                                                 
     47     3.4E+44     3.4E+44                                                 
     48     2.5E+44     2.6E+44                                                 
     49     1.8E+44     1.8E+44                                                 
     50     1.2E+44     1.2E+44                                                 
     51     7.5E+43     7.7E+43                                                 
     52     4.5E+43     4.6E+43                                                 
     53     2.5E+43     2.5E+43                                                 
     54     1.3E+43     1.4E+43                                                 
     55     6.7E+42     6.8E+42                                                 
     56     3.2E+42     3.2E+42                                                 
     57     1.4E+42     1.4E+42                                                 
     58     6.0E+41     6.0E+41                                                 
     59     2.3E+41     2.4E+41                                                 
     60     8.6E+40     8.7E+40                                                 
     61     3.0E+40     3.0E+40                                                 
     62     9.8E+39     9.9E+39                                                 
     63     3.0E+39     3.0E+39                                                 
     64     8.4E+38     8.4E+38                                                 
     65     2.2E+38     2.2E+38                                                 
     66     5.4E+37     5.4E+37                                                 
     67     1.2E+37     1.2E+37                                                 
     68     2.5E+36     2.5E+36                                                 
     69     4.7E+35     4.7E+35                                                 
     70     8.1E+34     8.1E+34                                                 



The values at the bounds are :
N(0)=0
N(81) = Ng = 6.67E+21

We should be able to get the numbers N(c) for a few values of c below 28 or above 70 with more simulations.

Comments are welcome.

JPF

[Red Ed]

One comment I'd make is that you can avoid problems like this (from your previous post) ...

Code: Select all

        c      ρ (%)                                                                 
       47      70
       48      69     ### oops, smaller

... if, during each trial, you test all c at the same time along the following lines:

Code: Select all

set puzzle_count[c]=0 for c=0...81 initially
for each trial {
    pick a random solution grid, set c = 81
    while grid is uniquely solvable {
        increment puzzle_count[c]
        delete a random clue, decrement c
    }
}

(this was my "not the most obvious method" mentioned a few days back when I was taking a weighted average of the puzzle counts to give me an overall 'P' number)

[Ocean]

Here is an attempt to count puzzles, in order to provide an "independent" verification of the numbers given recently.

Based on random paths in 10000 random grids (and the sampling continues...), from full grid to a minimal, and statistics collected for each puzzle.

Code: Select all

  32 M21
 328 M22
1779 M23
3360 M24
2943 M25
1256 M26
 270 M27
  31 M28
   1 M29


The parameters r (number of reducable clues) and m (number of reducable clues that lead directly to a minimal) are averaged over the nonminimal subgrids, so estimated numbers of sudokus N, and minimal sudokus M are caculated recursively using

N(C-1)=(N(C)-M(C))*r(C)/(82-C)
M(C-1)=(N(C)-M(C))*m(C)/(82-C)

where C is number of clues; starting with N(81)=1, so the numbers are average per grid.

Code: Select all

#
# Statistics from 10000 grids: r, m, N, M (average per grid; r and m for nonminimal grids).
#
# r[81]=81.000000 m=0.000000 N=1.000000 M=0.000000
# r[80]=80.000000 m=0.000000 N=81.000000 M=0.000000
# r[79]=79.000000 m=0.000000 N=3240.000000 M=0.000000
# r[78]=78.000000 m=0.000000 N=85320.000000 M=0.000000
# r[77]=76.997700 m=0.000000 N=1663740.000000 M=0.000000
# r[76]=75.995200 m=0.000000 N=25620830.679600 M=0.000000
# r[75]=74.988800 m=0.000000 N=324510025.277056 M=0.000000
# r[74]=73.982500 m=0.000000 N=3476373911.928017 M=0.000000
# r[73]=72.973100 m=0.000000 N=32148854117.401814 M=0.000000
# r[72]=71.960000 m=0.000000 N=260666838488.286011 M=0.000000
# r[71]=70.942500 m=0.000000 N=1875758569761.705810 M=0.000000
# r[70]=69.922300 m=0.000000 N=12097363848665.437500 M=0.000000
# r[69]=68.896300 m=0.000000 N=70489625352961.609300 M=0.000000
# r[68]=67.862900 m=0.000000 N=373574951938865.312000 M=0.000000
# r[67]=66.824300 m=0.000000 N=1810848543280858.500000 M=0.000000
# r[66]=65.784700 m=0.000000 N=8067245754050870.000000 M=0.000000
# r[65]=64.737000 m=0.000000 N=33168833859781892.000000 M=0.000000
# r[64]=63.681900 m=0.000000 N=126308870445923536.000000 M=0.000000
# r[63]=62.619400 m=0.000000 N=446866047602792128.000000 M=0.000000
# r[62]=61.548200 m=0.000000 N=1472762304276751610.000000 M=0.000000
# r[61]=60.470800 m=0.000000 N=4532293442804318200.000000 M=0.000000
# r[60]=59.385100 m=0.000000 N=13051019539101493200.000000 M=0.000000
# r[59]=58.285000 m=0.000000 N=35228913655977095100.000000 M=0.000000
# r[58]=57.178200 m=0.000000 N=89274662279940210600.000000 M=0.000000
# r[57]=56.058300 m=0.000000 N=212690187282286542000.000000 M=0.000000
# r[56]=54.923900 m=0.000000 N=476922013029064179000.000000 M=0.000000
# r[55]=53.782700 m=0.000000 N=1007477575054116120000.000000 M=0.000000
# r[54]=52.616800 m=0.000000 N=2006846821328259640000.000000 M=0.000000
# r[53]=51.440100 m=0.000000 N=3771209208159455930000.000000 M=0.000000
# r[52]=50.248900 m=0.000000 N=6689357889263560030000.000000 M=0.000000
# r[51]=49.027300 m=0.000000 N=11204429188060523000000.000000 M=0.000000
# r[50]=47.790700 m=0.000000 N=17720093907477409500000.000000 M=0.000000
# r[49]=46.531800 m=0.000000 N=26464240372002521600000.000000 M=0.000000
# r[48]=45.253900 m=0.000000 N=37316022428543844600000.000000 M=0.000000
# r[47]=43.945400 m=0.000000 N=49667516099384716500000.000000 M=0.000000
# r[46]=42.607300 m=0.000000 N=62361681771254310200000.000000 M=0.000000
# r[45]=41.219000 m=0.000000 N=73807302325898997300000.000000 M=0.000000
# r[44]=39.794500 m=0.000000 N=82223329583006234900000.000000 M=0.000000
# r[43]=38.321800 m=0.000000 N=86106218133972156600000.000000 M=0.000000
# r[42]=36.800300 m=0.000000 N=84608853079139865800000.000000 M=0.000000
# r[41]=35.210400 m=0.000000 N=77840779399206770000000.000000 M=0.000000
# r[40]=33.564800 m=0.000000 N=66848901925800725400000.000000 M=0.000000
# r[39]=31.836300 m=0.000000 N=53423095794264669400000.000000 M=0.000000
# r[38]=30.005300 m=0.000000 N=39553341968254612000000.000000 M=0.000000
# r[37]=28.063500 m=0.000000 N=26972952085456140300000.000000 M=0.000000
# r[36]=26.029800 m=0.000000 N=16821232018893299500000.000000 M=0.000000
# r[35]=23.833500 m=0.000000 N=9518550113160626430000.000000 M=0.000000
# r[34]=21.517800 m=0.000000 N=4826816257915187360000.000000 M=0.000000
# r[33]=19.128800 m=0.000000 N=2163801393220154550000.000000 M=0.000000
# r[32]=16.615700 m=0.000000 N=844712736543463047000.000000 M=0.000000
# r[31]=13.983100 m=0.000000 N=280709868331704385000.000000 M=0.000000
# r[30]=11.328200 m=0.000300 N=76964591369981476800.000000 M=0.000000
# r[29]= 8.736074 m=0.005801 N=16766736229950400000.000000 M=444026488672969.000000
# r[28]= 6.333266 m=0.051465 N=2763614516888020000.000000 M=1835118133439280.000000
# r[27]= 4.268097 m=0.204166 N=323908954919126000.000000 M=2632129199201930.000000
# r[26]= 2.760009 m=0.493130 N=24931648291358800.000000 M=1192614625453350.000000
# r[25]= 1.864703 m=0.779778 N=1169999045878610.000000 M=209043386994070.000000
# r[24]= 1.377279 m=0.969144 N=31436787719104.800000 M=13146176873222.200000
# r[23]= 1.152778 m=0.972222 N=434332314055.281000 M=305624754441.759000
# r[22]= 1.031250 m=1.031250 N=2514766833.155200 M=2120886796.992840
# r[21]= 0.000000 m=0.000000 N=6769813.121541 M=6769813.121541
# r[20]= 0.000000 m=0.000000 N=0.000000 M=0.000000
# r[19]= 0.000000 m=0.000000 N=0.000000 M=0.000000
# r[18]= 0.000000 m=0.000000 N=0.000000 M=0.000000
# r[17]= 0.000000 m=0.000000 N=0.000000 M=0.000000
# r[16]= 0.000000 m=0.000000 N=0.000000 M=0.000000
#


The sampling continues ....
The number of significant digits is of course far less than displayed... (but the display gives an illustrative graphical picture).
Weak points in the range 27-36 clues for minimal puzzles, and below 22 clues for puzzles in general.

Summing all minimal puzzles gives 6.33*10^15 for an average grid, rather close to Ed's numbers.

Code: Select all

#
# Distribution of minimal puzzles per grid, as calculated from the sample set.
# Average based on 10000 random grids, one random path per grid.
#
           Minimal Puzzles
Clues  Percentage     Counts
>30   ???        %
 29   7.01864390 %   4,44E+14
 28  29.00737012 %   1,84E+15
 27  41.60557541 %   2,63E+15
 26  18.85143698 %   1,19E+15
 25   3.30430984 %   2,09E+14
 24   0.20779917 %   1,31E+13
 23   0.00483095 %   3,06E+11
 22   0.00003352 %   2,12E+09
 21   0.00000011 %   6,77E+06
<21  <0.0000001  %
#


[Red Ed]

There's a subtle problem in the recursive formulae that you're using, Ocean. The formulae themselves are correct, but they rely upon values r(C) and m(C) that are harder to estimate than I had initially appreciated.

Here's a simplified example in a grid with just 7 puzzles , and where the directed acyclic graph that describes which clue removal has been replaced with a tree.

First, let's show your (slightly adapted, to remove division by 82-C) recursive formulae working nicely:

Code: Select all

What an unbiased subgrid sampler sees:

 c=81         A        r[81]=2      m[81]=0
             / \
 c=80       B   F      r[80]=3/2    m[80]=1
           /   / \
 c=79     C   G   H    r[79]=2/3    m[79]=2/3
         / \
 c=78   D   E
 
What an unbiased subgrid sampler calculates:
 
 N[81] = 1                  M[81] = 0
 N[80] = N[81]*r[81] = 2    M[80] = N[81]*m[81] = 0
 N[79] = N[80]*r[80] = 3    M[79] = N[80]*m[80] = 2
 N[78] = N[79]*r[79] = 2    M[78] = N[79]*m[79] = 2

 (these are all correct)

In that example, we sampled C-clue subgrids purely at random. (By "magic" !)

Now consider how subgrid sampling is (in your case?) implemented: what you might tend to do is run a random path down the tree until you hit a minimal puzzle. Whenever there's a split in the tree, you pick a branch at random. This means that, for example, grids C, G and H are sampled in the biased ratio 2:1:1. The effect this has on the N(.) and M(.) estimates is shown below:

Code: Select all

What tree traversal sees:

 c=81         A        r[81]=2      m[81]=0
             / \
 c=80       B   F      r[80]=3/2    m[80]=1
           /   / \
 c=79     C   G   H    r[79]=1#     m[79]=1#
         / \
 c=78   D   E
 
What tree traversal calculates:
 
 N[81] = 1                  M[81] = 0
 N[80] = N[81]*r[81] = 2    M[80] = N[81]*m[81] = 0
 N[79] = N[80]*r[80] = 3    M[79] = N[80]*m[80] = 2
 N[78] = N[79]*r[79] = 3#   M[78] = N[79]*m[79] = 3#

 (mistakes are marked with hashes)

To understand the wrong values for r[79] and m[79]: they are equal to 2*Pr(C) + 0*Pr(G) + 0*Pr(H) = 2*.5 + 0*.25 + 0*.25 = 1.

OK, so how is my method any better? There are four random paths you can take to a minimal grid, each having equal probability. Let's consider each in turn.

• In path ABCD, the number of minimals and non-minimals directly descended from A are 0 and 2 respectively; from B they are 0 and 1; and from C they are 2 and 0: so the estimated number of minimals is 0+2(0+1(2+0)) = 4.
• Path ABCE is exactly the same as path ABCD, i.e. 4 minimals.
• In path AFG, the number of minimals and non-minimals directly descended from A are 0 and 2 respectively; and from F they are 2 and 0: so the estimated number of minimals is 0+2(2+0) = 4.
• Path AFH is exactly the same as path AFG, i.e. 4 minimals.

The average of these is, of course, 4, which is the correct number of minimals. (Sorry, this example would've been more convincing if I'd made the individual path estimates different.) In comparison, your formulae with r(C) and m(C) given by tree traversal mistakenly reports 5 minimals.

I can't see a way to get reliable estimates for r(C) and m(C) and so, since I believe the two methods have the same complexity, I'd recommend my way of doing things instead of yours.

Having said that, the bias only appears if the tree (or directed acyclic graph) is unbalanced. If the real 3x3 sudoku DAG is fairly regular then your estimates will be good; but that's a big unquantifiable "if". It may be instructive to calculate the result given by your method on the 2x2 case (which could be done exhaustively, so showing what estimate you get in the limit as nr trials->infinity) to see how small the bias is there. If the 2x2 bias is low then it seems likely to me that the 3x3 bias should be nothing to worry about. One good sign is that your estimate for the total number of puzzles (not just minimal), at 8.45e23, isn't far off my fairly uncontroversial estimate calculated several posts ago of 2^81/2.74 = 8.82e23.

[coloin]

Well.....great work by Red Ed and Ocean - I can just about see how they are getting their results - very impressive !

The work on the 2x2/4x4 grid by Red Ed and SG I thought went unappreciated.....even though it was only for the "two " essentially different 2x2 grids !

288 solutions of which 2 are essentially different
13579680 puzzles of which 85632 are irreducible
1536 6-clue, 58368 5-clue and 25728 4-clue irreducible puzzles
4710 essentially different puzzles of which 36 are irreducible (13 4-clues, 22 5-clues and 1 6-clue)

from Ocean's data - it would appear that the average size minmal puzzle would appear to have 27 clues !

Hopefully we shall soon have confirmation regarding the number of puzzles per individual grid.

Regarding JPFs work, thanks for explaining it, the data has answered my curiosity very satisfactorily.

The random array has 3 outcomes

Code: Select all

value of c            16        21           27           32         43      78
minimal puzzle        none      few          few          few        none    none
non-minimal puzzle    none      very few     a lot        many       50%     all
invalid [>1 sol.]     all       most         most         most       50%     none

Since the vast majority of the outcomes are either non-minimal or invalid - the counts cannot be used to guestimate the number of minimals - despite my initial confidence. A few million extra puzzles is neither here nor there in the vast scheme of things !

When one of the random arrays fails to solve a puzzle [invalid] - it is because it has "missed " an unavoidable set. With higher values of c this will happen much more often with the smaller unavoidable sets. The maximum number of these small disjoint sets a grid has has been termed the MCN

Code: Select all

          MCN        p
SFB        8       1/1.44
SF         9       1/1.64
20-17s    12       1/2.26
mc        12       1/4.4
ran11     14       1/5.85
dukoso16  16       1/6.1

There is some correlation, [but some of these grids are not typical] and possibly/probably explains the results

There are grids with an mcn of 6....but I havnt seen one posted !

We should be able to get the numbers N(c) for a few values of c below 28 ...

Will you be able to breakdown these into Minimals & Nonminimals ?

ravel's results..........

Code: Select all

For 5 mio random sudokus each:
clues, unique(all minimals), minimal, all possible, estimated minimals
 28:    7050(?>20000)           0(?)     4.4e21
 27:    2186(14256)             3        2.3e21        1.4e16
 26:     473(1627)              1        1.1e21          2e14
 25:     127(206)               8        5.2e20          9e14
 24:      10(16)                0        2.3e20         <5e13

which in retrospect was rather good !

C

[Red Ed]

Further to this:

It may be instructive to calculate the result given by your method on the 2x2 case (which could be done exhaustively, so showing what estimate you get in the limit as nr trials->infinity) to see how small the bias is there.

I just coded up the 2x2 DAG for each of the two essentially-different grid configs and computed the proportion of time that a random path (from the root to a minimal) hits each node at any level C. From this, together with the individual r and m values at each node, I get weighted average approximations to r(C) and m(C) for all C. I believe this mimics what Ocean's method would end up converging to (in the 2x2 case) when run forever. The approximations give biased results for the number of puzzles N(.) and minimals M(.):

Code: Select all

Config 1:
[tt_est] N(16) =     1.0000,   M(16) =    0.0000
[tt_est] N(15) =    16.0000,   M(15) =    0.0000
[tt_est] N(14) =   120.0000,   M(14) =    0.0000
[tt_est] N(13) =   560.0000,   M(13) =    0.0000
[tt_est] N(12) =  1812.0000,   M(12) =    0.0000
[tt_est] N(11) =  4270.7446,   M(11) =    0.0000
[tt_est] N(10) =  7467.7589,   M(10) =    0.0000
[tt_est] N( 9) =  9644.2477,   M( 9) =    0.0000
[tt_est] N( 8) =  8940.7704,   M( 8) =    0.0000
[tt_est] N( 7) =  5583.0698,   M( 7) =    0.0000
[tt_est] N( 6) =  2057.9231,   M( 6) =   19.1214
[tt_est] N( 5) =   340.9392,   M( 5) =  224.1177
[tt_est] N( 4) =     7.7675,   M( 4) =    7.7675
[tt_est] N( 3) =     0.0000,   M( 3) =    0.0000
[tt_est] N( 2) =     0.0000,   M( 2) =    0.0000
[tt_est] N( 1) =     0.0000,   M( 1) =    0.0000
[tt_est] N( 0) =     0.0000,   M( 0) =    0.0000
[tt_est] TOTAL:  40822.2213,            251.0066

Config 2:
[tt_est] N(16) =     1.0000,   M(16) =    0.0000
[tt_est] N(15) =    16.0000,   M(15) =    0.0000
[tt_est] N(14) =   120.0000,   M(14) =    0.0000
[tt_est] N(13) =   560.0000,   M(13) =    0.0000
[tt_est] N(12) =  1816.0000,   M(12) =    0.0000
[tt_est] N(11) =  4319.2862,   M(11) =    0.0000
[tt_est] N(10) =  7736.7433,   M(10) =    0.0000
[tt_est] N( 9) = 10528.2425,   M( 9) =    0.0000
[tt_est] N( 8) = 10811.6952,   M( 8) =    0.0000
[tt_est] N( 7) =  8154.6952,   M( 7) =    0.0000
[tt_est] N( 6) =  4212.3155,   M( 6) =    0.0000
[tt_est] N( 5) =  1219.4061,   M( 5) =  170.3227
[tt_est] N( 4) =   114.4250,   M( 4) =  114.4250
[tt_est] N( 3) =     0.0000,   M( 3) =    0.0000
[tt_est] N( 2) =     0.0000,   M( 2) =    0.0000
[tt_est] N( 1) =     0.0000,   M( 1) =    0.0000
[tt_est] N( 0) =     0.0000,   M( 0) =    0.0000
[tt_est] TOTAL:  49609.8089,            284.7477

Compare these with the true values and you'll see that, in this case at least, Ocean's method gives underestimates for the grand totals.

Whilst this doesn't invalidate Ocean's 3x3 results (the 3x3 DAG might be much better behaved for all I know), it's not good news.

PS: apologies, Ocean, if I have misinterpreted your method!

[JPF]

Number of valid puzzles* with c clues. (3)
* minimal & non minimals

Here is an improvement of the previous numbers given in (2)

In order to get missing values (or more precise values) for c=26,...,30 , I increased the number of simulations from 10^4 to 10^5 for these values of c.
I only kept the values of c such that : np(1-p)>20
n: number of trials
p: (estimated) average probability of a valid puzzle with c clues
Above c≥65, as the proportion of valid puzzles is very close to 1, then N(c) ~ 81! / (c! x (81-c)! ) x Ng for the required precision.

Here are confidence intervals [N1, N2] (probability = 95%) for the number of valid puzzles with c clues.

Code: Select all

  Clues          N1          N2     
                                           
     26     6,0E+38     1,8E+39                                                 
     27     7,4E+39     1,2E+40                                                 
     28     5,5E+40     7,2E+40                                                 
     29     2,4E+41     2,9E+41                                                 
     30     1,0E+42     1,1E+42                                                 
     31     3,0E+42     3,9E+42                                                 
     32     7,7E+42     9,5E+42                                                 
     33     2,0E+43     2,3E+43                                                 
     34     4,3E+43     4,9E+43                                                 
     35     7,7E+43     8,6E+43                                                 
     36     1,4E+44     1,5E+44                                                 
     37     2,0E+44     2,2E+44                                                 
     38     2,9E+44     3,1E+44                                                 
     39     4,0E+44     4,2E+44                                                 
     40     4,8E+44     5,1E+44                                                 
     41     5,6E+44     5,8E+44                                                 
     42     5,9E+44     6,2E+44                                                 
     43     5,9E+44     6,1E+44                                                 
     44     5,7E+44     5,9E+44                                                 
     45     5,0E+44     5,2E+44                                                 
     46     4,2E+44     4,4E+44                                                 
     47     3,4E+44     3,4E+44                                                 
     48     2,5E+44     2,6E+44                                                 
     49     1,8E+44     1,8E+44                                                 
     50     1,2E+44     1,2E+44                                                 
     51     7,5E+43     7,7E+43                                                 
     52     4,5E+43     4,6E+43                                                 
     53     2,5E+43     2,5E+43                                                 
     54     1,3E+43     1,4E+43                                                 
     55     6,7E+42     6,8E+42                                                 
     56     3,2E+42     3,2E+42                                                 
     57     1,4E+42     1,4E+42                                                 
     58     6,0E+41     6,0E+41                                                 
     59     2,3E+41     2,4E+41                                                 
     60     8,6E+40     8,7E+40                                                 
     61     3,0E+40     3,0E+40                                                 
     62     9,8E+39     9,9E+39                                                 
     63     3,0E+39     3,0E+39                                                 
     64     8,4E+38     8,4E+38                                                 
     65     2,2E+38     2,2E+38                                                 
     66     5,4E+37     5,4E+37                                                 
     67     1,2E+37     1,2E+37                                                 
     68     2,5E+36     2,5E+36                                                 
     69     4,7E+35     4,7E+35                                                 
     70     8,1E+34     8,1E+34                                                 
     71     1,3E+34     1,3E+34                                                 
     72     1,7E+33     1,7E+33                                                 
     73     2,1E+32     2,1E+32                                                 
     74     2,3E+31     2,3E+31                                                 
     75     2,2E+30     2,2E+30                                                 
     76     1,7E+29     1,7E+29                                                 
     77     1,1E+28     1,1E+28                                                 
     78     5,7E+26     5,7E+26                                                 
     79     2,2E+25     2,2E+25                                                 
     80     5,4E+23     5,4E+23                                                 
     81     6,7E+21     6,7E+21                                                 


Total number of valid puzzles*

With 10^6 simulations, I got a proportion P of valid puzzles equal to 0.378
It gives a standard deviation s = sqrt( 0.378 x 0.622 / 10^6 ) ~ 5E-4

and a confidence interval (95%) of [0.377 ; 0.379]

The resulting number of puzzles N = P x 2^81 x Ng is therefore such that : 6.08E+45 < N < 6.11E+45

JPF

[Ocean]

Thanks, Red Ed, for evaluating the methods, and for instructive examples!
Also interesting that our methods are principially different.

There's a subtle problem in the recursive formulae that you're using, Ocean. The formulae themselves are correct, but they rely upon values r(C) and m(C) that are harder to estimate than I had initially appreciated.

Here's a simplified example in a grid with just 7 puzzles , and where the directed acyclic graph that describes which clue removal has been replaced with a tree.

The example in your first post illustrates a possible methodological problem.
The example itself is not a valid case though, since it violates some of the fundamental properties for sudoku "graphs". (In order to reach puzzle D, three clues are removed from the original grid A. The order of removal is not important, so there has to be three different subgraphs starting from A and ending in D. Similar for the other minimals).

So, the sudoku graphs are not trees.

I found it hard to evaluate the combined effects of 1) removing the (82-C) factor, and 2) using an invalid graph. Instead, better to test the methods on real cases, like the 2x2 case, or for valid subgraphs. The cases below are 'hand calculated' on sheets of paper. (If conclusions are questioned, I can supply more details).

Code: Select all

 Subgraph 1 (two levels):

 c=81         A       
             /|\
 c=80       B C E     
             \| 
 c=79         D       

# This is a real case:
100000002020030040000105000006000300030010070008000900000608000070040020300000008 #A:21
000000002020030040000105000006000300030010070008000900000608000070040020300000008 #B:20
100000002020030040000105000006000300030010070008000900000608000070000020300000008 #C:20
000000002020030040000105000006000300030010070008000900000608000070000020300000008 #D:19
100000002020030040000105000006000300030010070008000900000608000070040020000000008 #E:20
#


In this case (subgraph 1 - two levels) the found average values for r and m are correct.

Code: Select all

 Subgraph 2 (three levels):

 c=81           A ---
               /  \   \   
              /    \   \
             /|\   /\   \
 c=80       B C D I  J   L
            |X X|  \ /
 c=79       E F G   K     
             \|/
              H


Subgraph 2 (three levels): Still calculating/finding correct averages for r and m, when using the modified method (when averages are calculated for the non-minimal sets, and the recursive formulas are adjusted accordingly.)

Subgraph 3 (four levels). Adding a fourth level (a parallell uncoupled subgraph with 4+6+4+1 nodes) results in incorrect average values when the method is applied:
correct r=105/63 versus found r=93/63; (average for the non-minimal set, c='79')
correct m=7/21 versus found m=9/21;

Preliminary conclusions: 1. the "found" r seems to be (always?) equal or lower than the correct r. This tends to underestimate N. Can possibly explain the divergence between my estimates and JFK's values for number of grids - where my estimates were generally at the same order of magnitude, but mostly outside the 95% confidence interval (at the lower side).
2. The "found" m is either equal or higher than the correct m. This tends to overestimate the ratio M/N.
3. Combined effects (guessing here): This may result in bias of the distribution of minimals, reporting too many for 'high number of clues', and losing some minimals for low number of clues.

How would you assess your method for finding minimals, given the cases above?


The 2x2 case is also interesting. Not quite sure about the details. The result is not too unlikely. The errors will be different if r and m averages are for all subgrids, compared to only for non-minimal subgrids (and adjusted recursion formulas). (In order to run this case myself some modifications in the program logic must be done. Not sure how much work that is. But the idea of testing 'everything new' for the 2x2 case is good.)

Number of valid puzzles* with c clues. (3)
* minimal & non minimals

Here is an improvement of the previous numbers given in (2)

(...)

Total number of valid puzzles*

With 10^6 simulations, I got a proportion P of valid puzzles equal to 0.378
It gives a standard deviation s = sqrt( 0.378 x 0.622 / 10^6 ) ~ 5E-4

and a confidence interval (95%) of [0.377 ; 0.379]

The resulting number of puzzles N = P x 2^81 x Ng is therefore such that : 6.08E+45 < N < 6.11E+45

JPF

Thanks. Useful for calibration of other methods also.

Comparing calculated total number of valid puzzles:

5.63691E+45 (mine) vs. 6.08E+45 < N < 6.11E+45 (JPF; all grids)

(Ref. also: 8,45e23 (mine) vs. 2^81/2.74 = 8,82e23 (Red Ed; per grid))

Same order of magnitude, but clearly below the 95% confidence interval, which worries me a bit.

[Red Ed]

Also interesting that our methods are principially different.

They are mathematically the same, in that they both use path sampling to build recursive formulae for the number of puzzles. The only difference is that your presentation leads the unwary into the trap of trying to estimate r(C) and m(C) directly which, as I explained a couple of posts ago, is easily done wrongly.

The example in your first post ... is not a valid case though, ... sudoku graphs are not trees.

Yes, I know. That's why I called it a simplified example. The aim was to show you why calculating r(C) and m(C) through tree traversal would lead to incorrect results. Sure, you're traversing a DAG, not a tree, but I figured the principle would be the same (and sure enough, in the 2x2 case, it was).

Your real-world subgraph examples are nice. Glad that you were able to reproduce the bad averaging effect that I noticed.

Preliminary conclusions: ...

Interesting thoughts for further study perhaps!

How would you assess your method for finding minimals, given the cases above?

Sorry, no time now, will come back to this. I can tell you what the conclusion will be, though, and that's that the method works fine. I'm fairly certain that my method is an exact calculation, not an approximation.

...With 10^6 simulations, I got a proportion P of valid puzzles equal to 0.378
It gives a standard deviation s = sqrt( 0.378 x 0.622 / 10^6 ) ~ 5E-4
...

...
5.63691E+45 (mine) vs. 6.08E+45 < N < 6.11E+45 (JPF; all grids)

(Ref. also: 8,45e23 (mine) vs. 2^81/2.74 = 8,82e23 (Red Ed; per grid))

Same order of magnitude, but clearly below the 95% confidence interval, which worries me a bit.

I think this is just down to my, your and JPF's solution grid generators being biased in different ways. What I believe to be my least biased generator gave P ~= 2.72, but I stopped running those trials because I knew that I needed a better generator if I was going to report results with the degree of confidence that JPF (rashly, I believe) has been doing. If/when I get around to writing a proper unbiased generator (modulo any bias present in the 'C' random number generator ...) then I'll repeat my calculations. In the mean time, I'd treat my P ~= 2.72 and JPF's P ~= 2.64 with a pinch of salt ...

[JPF]

What I believe to be my least biased generator gave P ~= 2.72, but I stopped running those trials because I knew that I needed a better generator if I was going to report results with the degree of confidence that JPF (rashly, I believe) has been doing. If/when I get around to writing a proper unbiased generator (modulo any bias present in the 'C' random number generator ...) then I'll repeat my calculations. In the mean time, I'd treat my P ~= 2.72 and JPF's P ~= 2.64 with a pinch of salt ...

That's not the first time you take the liberty of giving (me) good or bad points without logical support, any rational in your answers or convincing arguments.
Could you tell me why ?

I' m still waiting for the number of simulations you've made to do your estimations and how you justify your number 2.72 (which is not P btw) with such a precision (4E-3) without any explanations.

When you or somebody else will have made the same number of simulations and produce the corresponding confidence interval, I would be happy to compare our results and discuss the question of biais.

JPF

[m_b_metcalf]

If/when I get around to writing a proper unbiased generator (modulo any bias present in the 'C' random number generator ...) ...

Well, I'm not a C programmer , but where I'm coming from nobody would dream of relying on a default PRNG without knowing its characteristics (cycle, correlations, biases). A quick Google search yielded the following which you should perhaps seriously consider if you're planning significantly long runs:

"Mersenne Twister (MT) is a pseudorandom number generator developed by Makoto Matsumoto and Takuji Nishimura (alphabetical order) during 1996-1997. MT has the following merits: It is designed with consideration of the flaws of various existing generators. The algorithm is coded into a C source downloadable below. Far longer period and far higher order of equidistribution than any other implemented generators (it is proven that the period is 2^19937-1, and 623-dimensional equidistribution property is assured). Fast generation (although it depends on the system, it is reported that MT is sometimes faster than the standard ANSI-C library in a system with pipeline and cache memory). Efficient use of the memory (the implemented C-code mt19937.c consumes only 624 words of working area). "

Regards,

Mike Metcalf