## Su-Doku's maths

Everything about Sudoku that doesn't fit in one of the other sections
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: 2237
Joined: 05 May 2005
Location: Devon

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
`123456789564897231978312645645978312789123456231564897897231564312645978456789123123456789564897231978312645647938512389125476251764893895271364712643958436589127`

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

Code: Select all
`123456789564897231978312645645978312789123456231564897897231564312645978456789123123456789564897231978312645647938512389125476251764893895271364712643958436589127123456789564897231978312645697238514382145976451769823845971362719623458236584197123456789564897312978231645645978231789123456312564897897312564231645978456789123123456789564978231897312645645897312789123456231564978978231564312645897456789123123456789567891234948372615675918342489723156231564897894237561312645978756189423123456789568397241974812635645978312739124856281563497897231564412685973356749128123456789578392641964817235645978312239164857781523496897231564416785923352649178123456789594837261678912345867291534312645978459783126945378612786129453231564897`

3.) 104 classes if we allow permuting symbols :

Code: Select all
`123456789564897231978312645645978312789123456231564897897231564312645978456789123123456789564897231978312645647938512389125476251764893895271364712643958436589127123456789564897231978312645695278314782143956431569827847931562319625478256784193123456789564897231978312645697238514382145976451769823845971362719623458236584197123456789564897231978312645845971362719623458236584197697238514382145976451769823123456789564897231978312645847931562319625478256784193695278314782143956431569827123456789564897231978312645895271364712643958436589127647938512389125476251764893123456789564897231978312645897231564312645978456789123645978312789123456231564897123456789564897312978231645645978231789123456312564897897312564231645978456789123123456789564897312978231645897312564231645978456789123645978231789123456312564897123456789564978231897312645645897312789123456231564978978231564312645897456789123123456789564978231897312645978231564312645897456789123645897312789123456231564978123456789564978312897231645645897231789123456312564978978312564231645897456789123123456789564978312897231645978312564231645897456789123645897231789123456312564978123456789567891234948372615675918342489723156231564897894237561312645978756189423123456789567891234948372615894237561312645978756189423675918342489723156231564897123456789568397241974812635645978312739124856281563497897231564412685973356749128123456789568397241974812635897231564412685973356749128645978312739124856281563497123456789574892631968317245645978312289163457731524896897231564316745928452689173123456789574892631968317245897231564316745928452689173645978312289163457731524896123456789578392641964817235645978312239164857781523496897231564416785923352649178123456789578392641964817235897231564416785923352649178645978312239164857781523496123456789594837261678912345867291534312645978459783126945378612786129453231564897123456789594837261678912345945378612786129453231564897867291534312645978459783126123456789597831264648972315864297531312645978759183426975318642486729153231564897123456789597831264648972315975318642486729153231564897864297531312645978759183426123456789645897231978312564564978312789123456231645897897231645312564978456789123123456789645897231978312564897231645312564978456789123564978312789123456231645897123456789645897312978231564564978231789123456312645897897312645231564978456789123123456789645897312978231564897312645231564978456789123564978231789123456312645897123456789645978231897312564564897312789123456231645978978231645312564897456789123123456789645978231897312564978231645312564897456789123564897312789123456231645978123456789645978312897231564564897231789123456312645978978312645231564897456789123123456789645978312897231564568397241739124856412685973974812635281563497356749128123456789645978312897231564574892631289163457316745928968317245731524896452689173123456789645978312897231564578392641239164857416785923964817235781523496352649178123456789645978312897231564964817235781523496352649178578392641239164857416785923123456789645978312897231564968317245731524896452689173574892631289163457316745928123456789645978312897231564974812635281563497356749128568397241739124856412685973123456789645978312897231564978312645231564897456789123564897231789123456312645978123456789647938512895271364564897231389125476712643958978312645251764893436589127123456789647938512895271364978312645251764893436589127564897231389125476712643958123456789648972315597831264864297531759183426312645978975318642231564897486729153123456789648972315597831264975318642231564897486729153864297531759183426312645978123456789675918342894237561567891234489723156312645978948372615231564897756189423123456789675918342894237561948372615231564897756189423567891234489723156312645978123456789678912345594837261867291534459783126312645978945378612231564897786129453123456789678912345594837261945378612231564897786129453867291534459783126312645978123456789695278314847931562564897231782143956319625478978312645431569827256784193123456789695278314847931562978312645431569827256784193564897231782143956319625478123456789697238514845971362564897231382145976719623458978312645451769823236584197123456789697238514845971362978312645451769823236584197564897231382145976719623458123456789845971362697238514564897231719623458382145976978312645236584197451769823123456789845971362697238514978312645236584197451769823564897231719623458382145976123456789847931562695278314564897231319625478782143956978312645256784193431569827123456789847931562695278314978312645256784193431569827564897231319625478782143956123456789864297531975318642597831264312645978486729153648972315759183426231564897123456789864297531975318642648972315759183426231564897597831264312645978486729153123456789867291534945378612594837261312645978786129453678912345459783126231564897123456789867291534945378612678912345459783126231564897594837261312645978786129453123456789894237561675918342567891234312645978489723156948372615756189423231564897123456789894237561675918342948372615756189423231564897567891234312645978489723156123456789895271364647938512564897231712643958389125476978312645436589127251764893123456789895271364647938512978312645436589127251764893564897231712643958389125476123456789897231564645978312564897231312645978789123456978312645456789123231564897123456789897231564645978312568397241412685973739124856974812635356749128281563497123456789897231564645978312574892631316745928289163457968317245452689173731524896123456789897231564645978312578392641416785923239164857964817235352649178781523496123456789897231564645978312964817235352649178781523496578392641416785923239164857123456789897231564645978312968317245452689173731524896574892631316745928289163457123456789897231564645978312974812635356749128281563497568397241412685973739124856123456789897231564645978312978312645456789123231564897564897231312645978789123456123456789897231645564978312645897231312564978789123456978312564456789123231645897123456789897231645564978312978312564456789123231645897645897231312564978789123456123456789897312564645978231564897312231645978789123456978231645456789123312564897123456789897312564645978231978231645456789123312564897564897312231645978789123456123456789897312645564978231645897312231564978789123456978231564456789123312645897123456789897312645564978231978231564456789123312645897645897312231564978789123456123456789945378612867291534594837261786129453312645978678912345231564897459783126123456789945378612867291534678912345231564897459783126594837261786129453312645978123456789948372615567891234675918342231564897489723156894237561756189423312645978123456789948372615567891234894237561756189423312645978675918342231564897489723156123456789964817235578392641645978312781523496239164857897231564352649178416785923123456789964817235578392641897231564352649178416785923645978312781523496239164857123456789968317245574892631645978312731524896289163457897231564452689173316745928123456789968317245574892631897231564452689173316745928645978312731524896289163457123456789974812635568397241645978312281563497739124856897231564356749128412685973123456789974812635568397241897231564356749128412685973645978312281563497739124856123456789975318642864297531597831264486729153312645978648972315231564897759183426123456789975318642864297531648972315231564897759183426597831264486729153312645978123456789978231564645897312564978231312645897789123456897312645456789123231564978123456789978231564645897312897312645456789123231564978564978231312645897789123456123456789978231645564897312645978231312564897789123456897312564456789123231645978123456789978231645564897312897312564456789123231645978645978231312564897789123456123456789978312564645897231564978312231645897789123456897231645456789123312564978123456789978312564645897231897231645456789123312564978564978312231645897789123456123456789978312645564897231645978312231564897789123456897231564456789123312645978123456789978312645564897231647938512251764893389125476895271364436589127712643958123456789978312645564897231695278314431569827782143956847931562256784193319625478123456789978312645564897231697238514451769823382145976845971362236584197719623458123456789978312645564897231845971362236584197719623458697238514451769823382145976123456789978312645564897231847931562256784193319625478695278314431569827782143956123456789978312645564897231895271364436589127712643958647938512251764893389125476123456789978312645564897231897231564456789123312645978645978312231564897789123456`
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Sudoku disjoint groups

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

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

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

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

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

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

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

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

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

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

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

>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

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

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 