suexg :E(X) = 10.67 is the same number we got with 500000 grids.

which is OK :

|m-E(X)|< 2s/sqrt(n) [P = 95%]

as s~3.4 ; n = 500000 is large enough to have an absolute error ~ 0.01

Unbiased generator :11.570 ≤ mean(X) ≤ 11.584 [P=95%] which is consistent with 11.5788

Back to the challenge :

Red Ed wrote: Challenge: given a perfect(*) random number generator, can you produce a perfect random sudoku grid generator(*: perfect = no bias, correlations etc.)

Some thoughts :

A perfect random sudoku grid generator would consist of the followings :

-The list of the set Sg of the different grids. |Sg|= Ng = 6670903752021072936960 = 6.670904 E21

-A perfect uniform random integer generator giving an integer between 1 and Ng.

As it seems impossible to get (and to store) the Ng grids, one could limit the list to a set Se of essentially different Sudoku grids.

|Se|= Ne = 5472730538

Let G be a random grid from Se.

Let f be a random transformation of the symmetry group :

f is generated by a combination of independent random transformations r, t, p

where :

r is a relabelling (9!)

t a transposition (2)

p a permutation (6 x 6 x 6^3 x 6^3)

By using r, t, p it's easy to generate an uniform random f among the nt = 9! x 2 x 6^8 = 1.218998 E12 transformations.

The collection Sf of f(G), when G

describes Se, includes Sg.

The collection Sf has duplicates.

|Sf| = 9! x 2 x 6^8 x Ne = 6.671248 E21 > Ng

The relative error (bias ?) is therefore e = (|Sf| - Ng) / Ng = 5.16 E-05.

Example : Estimation of P = proportion of valid puzzles.

Let P' be the proportion of valid puzzles in the "duplicate" grids.

We will observe P* instead of P, such that :

P* = (1 - e)P+ eP'

and

|P*- P|= e| P'- P|< 5.16 E-05 [as P and P' <1].

But is it easy to build a list of Se ?

With 10 bytes/grid (see

RW) we would need around 55 x 10^9 bytes before any compression to store the file.

JPF