Su-Doku's maths

Everything about Sudoku that doesn't fit in one of the other sections

Postby coloin » Sat Oct 08, 2005 9:26 am

Red Ed wrote:I got an answer about 50 million times bigger a while back ...


You did Ed
At the time I didnt understand the phrase "at the same offset".
I do now.
Excellent work it was too.
I am sure it can be confirmed in a very short time !.

dukuso wrote:Are there puzzles which use all 6 arrays ?
I found 104*9! grids here.


Neat demonstration
Have you an example of the 5 and 6 arrays - I just cant see what they do.
Where does 3doku fit - or is it one of 5/6
C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby dukuso » Sat Oct 08, 2005 10:55 am

3doku doesn't seem to fit anything with these 6 constraints


If I made no mistake then the classes for 3x3x3x3
latin tesseracts are :


1.) 2 classes if we allow permuting symbols, permuting parallel 3x3x3
hyperplanes, permuting coordinates

Code: Select all

123456789564897231978312645645978312789123456231564897897231564312645978456789123
123456789564897231978312645647938512389125476251764893895271364712643958436589127




2.) 9 classes if we allow permuting hyperplanes and symbols :

Code: Select all

123456789564897231978312645645978312789123456231564897897231564312645978456789123
123456789564897231978312645647938512389125476251764893895271364712643958436589127
123456789564897231978312645697238514382145976451769823845971362719623458236584197
123456789564897312978231645645978231789123456312564897897312564231645978456789123
123456789564978231897312645645897312789123456231564978978231564312645897456789123
123456789567891234948372615675918342489723156231564897894237561312645978756189423
123456789568397241974812635645978312739124856281563497897231564412685973356749128
123456789578392641964817235645978312239164857781523496897231564416785923352649178
123456789594837261678912345867291534312645978459783126945378612786129453231564897




3.) 104 classes if we allow permuting symbols :

Code: Select all

123456789564897231978312645645978312789123456231564897897231564312645978456789123
123456789564897231978312645647938512389125476251764893895271364712643958436589127
123456789564897231978312645695278314782143956431569827847931562319625478256784193
123456789564897231978312645697238514382145976451769823845971362719623458236584197
123456789564897231978312645845971362719623458236584197697238514382145976451769823
123456789564897231978312645847931562319625478256784193695278314782143956431569827
123456789564897231978312645895271364712643958436589127647938512389125476251764893
123456789564897231978312645897231564312645978456789123645978312789123456231564897
123456789564897312978231645645978231789123456312564897897312564231645978456789123
123456789564897312978231645897312564231645978456789123645978231789123456312564897
123456789564978231897312645645897312789123456231564978978231564312645897456789123
123456789564978231897312645978231564312645897456789123645897312789123456231564978
123456789564978312897231645645897231789123456312564978978312564231645897456789123
123456789564978312897231645978312564231645897456789123645897231789123456312564978
123456789567891234948372615675918342489723156231564897894237561312645978756189423
123456789567891234948372615894237561312645978756189423675918342489723156231564897
123456789568397241974812635645978312739124856281563497897231564412685973356749128
123456789568397241974812635897231564412685973356749128645978312739124856281563497
123456789574892631968317245645978312289163457731524896897231564316745928452689173
123456789574892631968317245897231564316745928452689173645978312289163457731524896
123456789578392641964817235645978312239164857781523496897231564416785923352649178
123456789578392641964817235897231564416785923352649178645978312239164857781523496
123456789594837261678912345867291534312645978459783126945378612786129453231564897
123456789594837261678912345945378612786129453231564897867291534312645978459783126
123456789597831264648972315864297531312645978759183426975318642486729153231564897
123456789597831264648972315975318642486729153231564897864297531312645978759183426
123456789645897231978312564564978312789123456231645897897231645312564978456789123
123456789645897231978312564897231645312564978456789123564978312789123456231645897
123456789645897312978231564564978231789123456312645897897312645231564978456789123
123456789645897312978231564897312645231564978456789123564978231789123456312645897
123456789645978231897312564564897312789123456231645978978231645312564897456789123
123456789645978231897312564978231645312564897456789123564897312789123456231645978
123456789645978312897231564564897231789123456312645978978312645231564897456789123
123456789645978312897231564568397241739124856412685973974812635281563497356749128
123456789645978312897231564574892631289163457316745928968317245731524896452689173
123456789645978312897231564578392641239164857416785923964817235781523496352649178
123456789645978312897231564964817235781523496352649178578392641239164857416785923
123456789645978312897231564968317245731524896452689173574892631289163457316745928
123456789645978312897231564974812635281563497356749128568397241739124856412685973
123456789645978312897231564978312645231564897456789123564897231789123456312645978
123456789647938512895271364564897231389125476712643958978312645251764893436589127
123456789647938512895271364978312645251764893436589127564897231389125476712643958
123456789648972315597831264864297531759183426312645978975318642231564897486729153
123456789648972315597831264975318642231564897486729153864297531759183426312645978
123456789675918342894237561567891234489723156312645978948372615231564897756189423
123456789675918342894237561948372615231564897756189423567891234489723156312645978
123456789678912345594837261867291534459783126312645978945378612231564897786129453
123456789678912345594837261945378612231564897786129453867291534459783126312645978
123456789695278314847931562564897231782143956319625478978312645431569827256784193
123456789695278314847931562978312645431569827256784193564897231782143956319625478
123456789697238514845971362564897231382145976719623458978312645451769823236584197
123456789697238514845971362978312645451769823236584197564897231382145976719623458
123456789845971362697238514564897231719623458382145976978312645236584197451769823
123456789845971362697238514978312645236584197451769823564897231719623458382145976
123456789847931562695278314564897231319625478782143956978312645256784193431569827
123456789847931562695278314978312645256784193431569827564897231319625478782143956
123456789864297531975318642597831264312645978486729153648972315759183426231564897
123456789864297531975318642648972315759183426231564897597831264312645978486729153
123456789867291534945378612594837261312645978786129453678912345459783126231564897
123456789867291534945378612678912345459783126231564897594837261312645978786129453
123456789894237561675918342567891234312645978489723156948372615756189423231564897
123456789894237561675918342948372615756189423231564897567891234312645978489723156
123456789895271364647938512564897231712643958389125476978312645436589127251764893
123456789895271364647938512978312645436589127251764893564897231712643958389125476
123456789897231564645978312564897231312645978789123456978312645456789123231564897
123456789897231564645978312568397241412685973739124856974812635356749128281563497
123456789897231564645978312574892631316745928289163457968317245452689173731524896
123456789897231564645978312578392641416785923239164857964817235352649178781523496
123456789897231564645978312964817235352649178781523496578392641416785923239164857
123456789897231564645978312968317245452689173731524896574892631316745928289163457
123456789897231564645978312974812635356749128281563497568397241412685973739124856
123456789897231564645978312978312645456789123231564897564897231312645978789123456
123456789897231645564978312645897231312564978789123456978312564456789123231645897
123456789897231645564978312978312564456789123231645897645897231312564978789123456
123456789897312564645978231564897312231645978789123456978231645456789123312564897
123456789897312564645978231978231645456789123312564897564897312231645978789123456
123456789897312645564978231645897312231564978789123456978231564456789123312645897
123456789897312645564978231978231564456789123312645897645897312231564978789123456
123456789945378612867291534594837261786129453312645978678912345231564897459783126
123456789945378612867291534678912345231564897459783126594837261786129453312645978
123456789948372615567891234675918342231564897489723156894237561756189423312645978
123456789948372615567891234894237561756189423312645978675918342231564897489723156
123456789964817235578392641645978312781523496239164857897231564352649178416785923
123456789964817235578392641897231564352649178416785923645978312781523496239164857
123456789968317245574892631645978312731524896289163457897231564452689173316745928
123456789968317245574892631897231564452689173316745928645978312731524896289163457
123456789974812635568397241645978312281563497739124856897231564356749128412685973
123456789974812635568397241897231564356749128412685973645978312281563497739124856
123456789975318642864297531597831264486729153312645978648972315231564897759183426
123456789975318642864297531648972315231564897759183426597831264486729153312645978
123456789978231564645897312564978231312645897789123456897312645456789123231564978
123456789978231564645897312897312645456789123231564978564978231312645897789123456
123456789978231645564897312645978231312564897789123456897312564456789123231645978
123456789978231645564897312897312564456789123231645978645978231312564897789123456
123456789978312564645897231564978312231645897789123456897231645456789123312564978
123456789978312564645897231897231645456789123312564978564978312231645897789123456
123456789978312645564897231645978312231564897789123456897231564456789123312645978
123456789978312645564897231647938512251764893389125476895271364436589127712643958
123456789978312645564897231695278314431569827782143956847931562256784193319625478
123456789978312645564897231697238514451769823382145976845971362236584197719623458
123456789978312645564897231845971362236584197719623458697238514451769823382145976
123456789978312645564897231847931562256784193319625478695278314431569827782143956
123456789978312645564897231895271364436589127712643958647938512251764893389125476
123456789978312645564897231897231564456789123312645978645978312231564897789123456

dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Sudoku disjoint groups

Postby Dan Hoey » Sat Oct 08, 2005 11:37 pm

coloin wrote:This is a grid which solves a "4 constraint puzzle" from tso at then end of the latin squares thread http://www.menneske.no/sudoku/dg/3/eng/
Dan Hoey wrote: I make it 8 * 6^4 permutations, or 8 * n!^4 permutations for the n^2 by n^2 grid. (That is before permuting the set of cell labels, which is another factor of n^2!.)
Red Ed wrote: I got an answer about 50 million times bigger a while back ...
Well, I was only talking about the size of the symmetry group. In the article you referenced, you said
Red Ed wrote:... The following operations leave the number of solutions intact: (a) rotate the whole grid; (b) transpose it; (c) switch the order of the row bands [by band, I mean rows 1,2,3 or 4,5,6 or 7,8,9]; (d) switch the order of the rows within each band according to the *same* permutation for each band....
which describes a group of size 2*6^4=2592. I was noting another transformation (e) which involves exchanging the row/column coordinates of each cell with block/offset coordinates. I haven't examined the number of solutions as you have, I'm just talking about having four times as many transformations.
Dan Hoey
 
Posts: 4
Joined: 30 September 2005

Postby crazyindy » Sun Oct 09, 2005 5:41 am

After all these discussions, what is the agreed answer?

Am sorry, but I am confused about the final answer!!
crazyindy
 
Posts: 1
Joined: 08 October 2005

Postby dukuso » Sun Oct 09, 2005 8:06 am

when you view these as 3*3*3*3 tesseracts,
using w,x,y,z for the coordinates

then with latin squares you have constraints
wx,yz

with normal sudoku you have constraints
wx,yz,wy

with 4-constraint sudoku you have constraints
wx,yz,wy,xz

with 4-dim sudoku (6-constraint) you have constraints
wx,wy,wz,xy,xz,yz


these 2 coordinates are fixed, while the other two can vary
and then yield all values 1,2,..,9


when we draw the corresponding graph, then we have

[code]

x-w y-z

x-w-y-z

w-x
| |
y-z

w-x
|X|
y-z

(/code]

for these 4 variants.

Autmomorphismgroups have size 4,2,8,24.

The total groups of equivalence-transformations
should have sizes
9!*9!^2
9!*6^8*2
9!*6^4*8
9!*6^4*24


for latin squares the graph is disconnected so we can
treat the wx and yz planes as one vector

---
I was a bit confused too, i.e. with my mappings to make
graphs from the puzzles
so the puzzles are equivalent. iff their graphs are isomorphic.
I had graphs for sudokus of size 117,
sudoku T-classes of size 111,
sudoku G-classes of size 105,
4-sudoku of size 102
6-sudoku of size 102



-Guenter
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Fast BRUTE FORCE of all solutions

Postby dukuso » Sun Oct 09, 2005 7:13 pm

Red Ed wrote:In an earlier post, I foolishly ventured that
Red Ed wrote:In restricted sudoku, there seem to be very few symmetries to exploit, so we would appear to be in the unfortunate situation of needing much more computing power to calculate a much smaller number ...

Well, not so :) The number of restricted sudokus, such that no digit appears at the same offset in any two 3x3 boxes, appears to be 201105135151764480. Here's how ...

1. without loss of generality, we can assume the top left box is 1...9 in order. We can also assume that the 1s in boxes 2,3 (top middle/right) are in rows 2,3 respectively and the 1s in boxes 4,7 are in columns 2,3. So we solve the problem with those constraints and multiply the answer by 9! x 4.

2. naively, we can just exhaust over the 244 subproblems corresponding to each of the possible arrangements of 1s. Someone said earlier that there are 8784 arrangements without the constraints above, so that's 8784/9 = 976 with 1 in the top left cell and 976/4 = 244 with the additional row/col constraints. But we can do better.

3. following AFJ's and Bertram's lead, we can look for equivalence classes. The following operations leave the number of solutions intact: (a) rotate the whole grid; (b) transpose it; (c) switch the order of the row bands [by band, I mean rows 1,2,3 or 4,5,6 or 7,8,9]; (d) switch the order of the rows within each band according to the *same* permutation for each band. Applying these ops, we find that the 244 layouts of the 1s breaks down into 11 equivalence classes of sizes 1, 2, 4, 9, 12, 18, 18, 36, 36, 36, 72. The number of solutions for each of the 11 representative subproblems is different, suggesting this is the best we can do.

I could easily have messed up my sums here -- I've done it before. Anyone want to check it?



yes, I got the same. Summands of the 11 are:

4*969349902
+8*373961017
+16*490762646
+36*598102466
+48*655641170
+72*458804480
+72*728290886
+144*547152562
+144*606126844
+144*595526742
+288*517948382
---------------------
=554191840696

554191840696*9!=201105135151764480


-Guenter.
Last edited by dukuso on Tue Oct 11, 2005 11:04 pm, edited 1 time in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Fast BRUTE FORCE of all solutions

Postby Red Ed » Mon Oct 10, 2005 7:40 am

dukuso wrote:yes, I got the same. First two summands of the 11 were:
969349902 and 373961017
Great, thanks!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby kjellfp » Tue Oct 11, 2005 6:47 am

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:

Let M be the number of column configurations for a Nx3-box that do not come in conflict with another fixed Nx3-configuration. 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.

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) 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.

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

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
- And finally, then the third band has one unique configuration, and therefore
R * n!^(3N) / (3N)!^N expected rows

Hence, the expected number of rows is

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

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

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.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby dukuso » Tue Oct 11, 2005 12:36 pm

>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
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby dukuso » Tue Oct 11, 2005 5:21 pm

using your numbers and methods I get an estimate of

1e47 for the number of 12*12 sudokus
and 1e107 for the number of 16*16 sudokus



for 12*12 you have

N=4
R=2.3e24
M=3.5e2
CC=3.5e4 (column configurations"

S(N) = R^3 * M^N / CC^(2N) = 1e47
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby LarryLACa » Wed Oct 12, 2005 12:35 am

jayanth wrote:1. The final result obtained by BF and FJ, after discounting for the 9! combos of B1, is NOT divisible by 12096, the number of possible combos for B2. That is (72^2 * 2^7 * 27704267971) is not divisible by 12096. -Jayanth


As you observed, the options for completing B2 come from 4 cases. Since the 4 do not contribute equally to the total, the size of the B2 factor (12096) is not a necessary factor of total 6e21 value.

This is essentially a restatement of the kjellfp reasoning: Not all of the band1 options contribute equally.

Further, I believe the band1 common permutations resulting from B1 (9!), B3 (6^3 column permutations) and the 6 band1 row permutations account for the 9! 6^4 factors in the 6e21 value. One of the 2^9 factors relates to tranposition.
LarryLACa
 
Posts: 32
Joined: 24 August 2005

Postby kjellfp » Wed Oct 12, 2005 7:17 am

dukuso wrote:using your numbers and methods I get an estimate of

1e47 for the number of 12*12 sudokus
and 1e107 for the number of 16*16 sudokus


When you talk about 12*12, I assume you mean boxes of size 3x4, though boxes of size 2x6 also give 12*12 boards. This is why I prefer to describe the board by box dimensions, not board dimensions, to sort out such ambiguities.

My methods are for Nx3 sudokus, it can't be used for 4x4-sudokus, so I don't know how you reach that number.



dukuso wrote:for 12*12 you have

N=4
R=2.3e24
M=3.5e2
CC=3.5e4 (column configurations"

S(N) = R^3 * M^N / CC^(2N) = 1e47


I stand corrected, thanks. Must have mistyped on the calc. More exact (using the exact numbers for R,M,CC) I get
S(4) = 8.106417e46

Still frightening enough to make me stay away from 4x4. But I'm working on the plan on how to attac 4x3 soon.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby dukuso » Wed Oct 12, 2005 10:35 am

>dukuso wrote:
>using your numbers and methods I get an estimate of
>
>1e47 for the number of 12*12 sudokus
>and 1e107 for the number of 16*16 sudokus
>
>
>When you talk about 12*12, I assume you mean boxes of size 3x4,

yes, sorry.

>though boxes of size 2x6 also give 12*12 boards. This is why I
>prefer to describe the board by box dimensions, not board dimensions,
>to sort out such ambiguities.

the problem is only that it's uncommon

>My methods are for Nx3 sudokus, it can't be used for 4x4-sudokus,
>so I don't know how you reach that number.

first I wrote a program to calculate "M", which I called CC2 as for
number of compatible column configurations for the 2nd box, see below.
CC2(4,4)=748521
Then calculating the column configurations for the 3rd box was too
difficult, so I did it via Monte-Carlo.
CC3(4,4)~160
This gave an estimate for R(4,4)~1e39, CC(4,4)=6.3e6, and
S(4,4) = R(4,4)^4 * CC2(4,4)^4 * CC3(4,4)^4 / CC(4,4)^(4*3) ~ 1e107


>dukuso wrote:
>for 12*12 you have
>
>N=4
>R=2.3e24
>M=3.5e2
>CC=3.5e4 (column configurations"
>
>S(N) = R^3 * M^N / CC^(2N) = 1e47
>
>
>I stand corrected, thanks. Must have mistyped on the calc.
>More exact (using the exact numbers for R,M,CC) I get
>S(4) = 8.106417e46
>
>Still frightening enough to make me stay away from 4x4.

it could be interesting for our copyright discussion.
You could argue that laws should be changed such that
with 1e107 16*16 sudokugrids you should be allowed to claim
for copyright, while 6.7e21 is just 21 decimal digits
and maybe not enough for copyright.
I mean, when they are going to regulate copyright on numbers -
which they should - then they must differentiate somehow
on their magnitude IMO.

>But I'm working on the plan on how to attac 4x3 soon.

44 "gangsters" for 3*9
? gangsters for 3*12


1 '----calculating compatible column configurations for the 2nd box
2 M=4:N=4: ' ----M*M x N*N-sudoku
3 DIM X(88),Y(88)
5 F=1:FOR I=1 TO 9:F=F*I:F(I)=F:NEXT:F(0)=1:FOR I=0 TO 9:FOR J=0 TO I:B(I,J)=F(I)/F(J)/F(I-J):NEXT J,I: ' -------B(x,y)=binomial(x,y)
10 I=0:FOR X=1 TO M:FOR Y=1 TO M:I=I+1:X(I)=X:Y(I)=Y:NEXT Y,X
20 I=0:CC2=0
30 I=I+1:X=X(I):Y=Y(I):A(X,Y)=-1:IF I>M*M THEN 60
40 A(X,Y)=A(X,Y)+1:IF A(X,Y)>N THEN 70
44 SX=0:FOR J=1 TO Y:SX=SX+A(X,J):NEXT
45 SY=0:FOR J=1 TO X:SY=SY+A(J,Y):NEXT
50 IF X=M AND SY <>N THEN 40
55 IF Y=M AND SX <>N THEN 40
56 IF X=Y AND A(X,Y)<>0 THEN 40
57 GOTO 30
60 Z=Z+1
65 T=1:FOR X=1 TO M:K=N:FOR Y=1 TO M:T=T*B(K,A(X,Y)):K=K-A(X,Y):NEXT Y,X
67 CC2=CC2+T
70 I=I-1:X=X(I):Y=Y(I):IF I>0 THEN 40
73 PRINT "M=";M:PRINT"N=";N:PRINT Z;"summands":PRINT CC2;"compatible column configurations"
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby kjellfp » Wed Oct 12, 2005 12:03 pm

dukuso wrote:>dukuso wrote:
Then calculating the column configurations for the 3rd box was too
difficult, so I did it via Monte-Carlo.
CC3(4,4)~160


That's why I said my method couldn't be used. Actually, the CC3-number is most probably depending on the choices of the first two bands. That's the big difference from Nx3-sudoku.

But for a check: Use this method to get an estiamte on the number of 3x4-Sudoku, an alternative estimate to the one I've already given (and you have corrected) for 4x3-Sudoku,
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby dukuso » Thu Oct 13, 2005 5:16 am

kjellfp wrote:But for a check: Use this method to get an estiamte on the number of 3x4-Sudoku, an alternative estimate to the one I've already given (and you have corrected) for 4x3-Sudoku,




R(4,3)=4!*4!*12!*114794496 ~ 3.17e19
CC(4,3)=12!/3!^4 ~ 3.70e5
CC2(4,3)=13833 ~ 1.38e4
CC3(4,3) ~ 1.54e2
S(4,3)=R(4,3)^4*CC2(4,3)^3*CC3(4,3)^3/CC(4,3)^9 ~ 7.5e46


compared with S(3,4)=8.1e46



---------------------------------------------------
size of sudokugrid, size of one box :
approximate number of sudokugrids

1*1 , 1*1 : 1.0e0
2*2 , 1*2 : 2.0e0
4*4 , 2*2 : 2.9e2
3*3 , 1*3 : 1.2e1
6*6 , 2*3 : 2.7e7
9*9 , 3*3 : 6.7e21
4*4 , 1*4 : 5.8e2
8*8 , 2*4 :
12*12 , 3*4 : 8.1e46
16*16 , 4*4 : 1e107
---------------------------------------------------
dukuso
 
Posts: 479
Joined: 25 June 2005

PreviousNext

Return to General