>Some thoughts about higher sudokus than 3x3:

>

>There is a way to give a rather accurate estimate on the number

>of Nx3-sudokus, when the number R of ways to complete the first

>band is calculated:

when you say Nx3, that's what others usually call N*N x 9 - sudokus

>Let M be the number of column configurations for a Nx3-box that

>do not come in conflict with another fixed Nx3-configuration.

and it doesn't matter which, M is always the same.

So M depends on N alone. So maybe M=CC(N) , CC for column-configurations

>A column configuration is a splitting of the 3N numbers into

>three disjoint sets (S_1,S_2,S_3) of N numbers each. Two such

>configurations (S_1,S_2,S_3) and (T_1,T_2,T_3) are in conflict

>if T_ and S_i have a common element for some i.

I called them G-classes (G for gangster) of a Nx3 box : you are

allowed to permute entries in a Nx1 column or permute the 3 columns.

However you don't allow permuting the columns here

>M is given as the sum of (N ch k)^3 when k runs from 0 to N,

>and where (N ch k) is the binomial function. This is because

>for a given k, there are (N ch k) [ways] to pick k numbers from S_1

>to be in T_2, the rest are in T_3, and so we need k numbers

>from S_2 in T_3 and from S_3 in T_1.

>

>The total number of column configurations for a box is (3N)!/N!^3.

= (3*N ch N) * (2*N ch N) = :CC(N)

>The expected (this is where the calculation turns from being exact

>to an estimation) number of bands that can be found from a given

>sequence of column configurations for each of the N boxes on a band,

>is then

>

>R/[ (3N)!/(n!)^3 ]^N = R * n!^(3N) / (3N)!^N

putting N Nx3-CCs together horizontally to form a Nx3N band

>And so we have the estimate:

>

>- The first band can be created in R ways.

>- Then the second band has M^N configurations, and therefore

> R * M^N * n!^(3N) / (3N)!^N expected rows

(what you mean with rows ?)

expected number of N*3N-bands in the middle per fixed first band

>- And finally, then the third band has one unique configuration,

> and therefore R * n!^(3N) / (3N)!^N expected rows

expected number of N*3N-bands in the third place, per fixed 1st and 2nd bands

>Hence, the expected number of rows is

>

>S(N) = R^3 * M^N * N!^(6N) / (3N)!^(2N)

expected number of grids, multiplying the 3 numbers for the bands

>Some values for N...

>

>N=1:

>R=6 (number of choices for the first row in a 3x3 latin square)

>M=2

>S(1)=12, this is also the exact answer (naturally, since there

> is only one configuration modulo permutations)

>

>N=2:

>R=20 * 6^4 (20 ways to choose the numbers on the first row in

> the first box, 6^4 ways to permute the order on each row in each box)

>M=10

>S(2) = 26542080, the exact answer is 28200960, 17/16 times S(2).

>The estimate is 6.25% from the right answer.

>

>N=3:

>This is what we have been doing here

>R=948109639680 (9!*56*6^6)

>M=56

>S(3) = 6.657e21, as already calculated earlier by others, this is

> only 0.2% from the right answer

yes, looks good !

>N=4:

>R=2273614462643364849254400 (I have just calculated this number,

>confirm it those who wish)

>M=346

>S(4) = 4.267532227e81, I'm sure this is less than 0.1% from the

>right answer

>

>This illustrates how fast the number of NxM-grids grows.

>I have the plans for a program counting the 3x4-grids,

>but I don't know if it can be run in w reasonable amount of time.

>

>As my program counts 3x3-grids in 2.6 seconds, while 3x4 will

>take hours, maybe days, I am more than ever sure about the

>impossibility of finding the number of 4x4-grids.

.. but maybe an estimate, using the same method for 4*16 bands ?

1e300 or 1e400 , that would be a giant difference ;-)

another estimate could probably also be done by Monte-Carlo

randomized generation of bands. That should hopefully confirm

your estimates.

Guenter.

PS. can we do the 416^6 classification program this week ?

I sent PM, but maybe you haven't read it. My email is

sterten@aol.com , or just click on the item below this message