The New Sudoku Players' Forum

[sciguy47]

I think I have figured out a way to reduce the calculation needed to find out how many valid solution grids are possible. First start with a blank grid. Select 1 number, and count the number of possible arrangements for that number. Keep on moving down the line until all the numbers are accounted for.

[william77]

There is a slightly more complicated (I think) question I was considering.

The root of it is how many 'real' puzzles are there that fulfil the criteria and by real I mean:

If you take one data set that fits the criteria. You could obviously rotate, or mirror it.

Also you could swap around the numbers so that for example all the 5s become 3s and vice versa.

Moreover you could switch the orderings of the 9x1 lines within a marked out 9x3 block and it would be still valid (or 3x9 block). By marked I mean marked out by the bold lines.

Moreover still, u could switch the order of the marked 3x9 blocks in both vertical and horizontal directions.

If all these transformations are considered 1 puzzle, how many real puzzles are there.



I suppose it is the total number of possible puzzles divided by the number of variations that one puzzle can be transformed into using the above criteria.

[frazer]

Red Ed solved your question within the last month -- it's quite a tricky calculation, and the answer turns out to be 5,472,730,538. Your guess that it is the total number of puzzles divided by the number of variations (9!*6^8*2) is pretty close (that would give 5,472,447,994.271...); the discrepancy comes about because there are some transformations which in general take a valid solution grid to a different one, but which take some special grids to themselves.

[coloin]

Might this number be the number of solutions which give a valid sudoku come from 3 horizontal chutes [one each of Red Eds 44] combined with the only combination of 3 vertical chutes which give a valid solution.

Each essentially different valid sudoku is one of a combination of 3 horizontal and 3 vertical chutes - in a particular combination of the 44 chutes.

number of 44^3 intersecting with 44^3 [if they are valid sudoku] = 5,472,730,538

maybe

[coloin]

Logically following on from my last post

5,472,730,538 is the number Red Ed calculated for "essentially different grids",
44^6 = 7,256,313,856 Healthily above and allows for many grids that dont turn up a solution.

[dukuso]

Logically following on from my last post

5,472,730,538 is the number Red Ed calculated for "essentially different grids",
44^6 = 7,256,313,856 Healthily above and allows for many grids that dont turn up a solution.

I think, I counted the number of different combinations
of gangsters in my very first post here.
It's now deleted/removed for some reason.
Maybe I can find that old post somewhere on my HD...

[coloin]

Let S be the collection of the 84 subsets of {1,..,9} of size 3.
Let T be the collection of ...........................
............................................
60713 out of the 85184=44^3 tupels of 3 members
from the list can be joined to form a valid 9*9 sudoku.


-Guenter Stertenbrink, sterten(-at-)aol.com

Ah.......
I was under the impression that this calculation was a repeat of the Bertrand enumeration - although I did wonder because of Red Eds response if it was a quick way to determine the "essentially different grids". If this is the case it certainly deserves / deserved more credit.

I did try to follow it -

Does the 60713 expand in any way to give the number of essentially different grids ? - 5472730538 - forgive me if this is implied.

It perhaps needs to be reposted and expanded [!] as it is relevant perhaps to our quest on finding a grid within withch is a 16er.

You were certainly on the case of the 3 horizontal "tupels" or bands giving a valid suduku - see above quote. I dont think Red Ed spelled out exactly what he had done in his calculation - he perhaps was a little miffed that you confirmed his magnificent work so neatly.

That also explains your understanding of the 44^2 concept a while back.

I think it is 44^6 now - as the vertical component of 3 stacks has a value for classification puposes - which may or may not be relevant.
[Edit - you classified Gfroyles grid this way some time ago ! - Doh]
.

[dukuso]

here is a repost of the enumeration method using
the "gang44"-representatives. I couldn't find the original post,
but maybe it's still there. Anyway, here is it again:


Let S be the collection of the 84 subsets of {1,..,9} of size 3.
Let T be the collection of the 4741632000 9-tupels (S1,..,S9)
with members from S such that
S1+S2+S3=S4+S5+S6=S7+S8+S9={1,2,3,4,5,6,7,8,9} ,
where "+" is set-union.
Let 2 members from T be equivalent if one can be obtained
from the other by one of the known obvious 6^4*9! operations.
Then we get the collection E of the known 44 minimal elements from T,
one from each equivalence class, called "the gang of the 44".
For M in T let C(M) be its equivalent representative in E.
For M in E let Z(M) be the size of its equivalence class.
For M in E let N(M) be the number of partial 3*9 sudoku grids
compatible with M with respect to the 6^9 operations
of permuting inside a column.
The 2*44 values of N(M),Z(M) are constant within one class and
can be calculated quickly.
For each M=(M1,..,M9) in T let U(M) be the set of the 175616
3-tupels (M,A,B) in T^3 , A=(A1,..,A9),B=(B1,..,B9)
such that Mi+Ai+Bi={1,2,3,4,5,6,7,8,9} for each 1<=i<=9.
----------------------------------------------------------
then the total number of sudokus is the sum over all M in E,
over all (M,A,B) in U(M)
of Z(M)*N(M)*N(C(A))*N(C(B)).
----------------------------------------------------------
This indeed adds up to 6670903752021072936960.
There are 7727104 summands in total, but since many of the
N(x) and Z(x) coincide, only 1398 summands are different.

You can easily save a factor of 2 by discarding triples
in U(M) with A>B.
Maybe another factor of 3 can be saved by requiring M<A<B,
but that makes things more complicated.


How can we calculate the total number of sudoku-classes
as defined by RedEd but discarding transposition
with this method ?

sum over all M in E,
over all (M,A,B) in U(M)
of Z(M)*Q(M)*Q(C(A))*Q(C(B))
gives 19859770556




E = "gang" of the 44
=====================

(1) M, element of E, minimal in its class ("ganger" or "gangster" ?)
(2) C(M)
(3) N(M) , number of compatible 3*9 sudokus (bands)
(4) Q(M) number of classes of compatible bands (from the gang of 416)
(5) Z(M) , number of 9-tupels from T in the class
--------------------------------------------------
123456789123456789123456789,1,1728,2,60480
123456789123456789123457689,2,576,3,4898880
123456789123456789124357689,3,192,3,29393280
123456789123456789124378569,4,192,2,9797760
123456789123456789147258369,5,96,2,6531840
123456789123457689123458679,6,576,4,6531840
123456789123457689123468579,7,864,7,6531840
123456789123457689124356789,8,192,6,58786560
123456789123457689124358679,9,192,8,117573120
123456789123457689124367589,10,192,6,58786560
123456789123457689124368579,11,288,24,235146240
123456789123457689124389567,12,192,6,58786560
123456789123457689126345789,13,192,3,29393280
123456789123457689126347589,14,192,8,117573120
123456789123457689126348579,15,288,16,117573120
123456789123457689145267389,16,96,1,29393280
123456789123457689145268379,17,144,8,117573120
123456789123457689146258379,18,168,14,235146240
123456789123457689148259367,19,144,3,58786560
123456789124357689125348679,20,192,5,39191040
123456789124357689125367489,21,144,4,58786560
123456789124357689125368479,22,168,9,117573120
123456789124357689125378469,23,264,13,117573120
123456789124357689126358479,24,144,8,117573120
123456789124357689126378459,25,168,14,235146240
123456789124357689126389457,26,144,4,58786560
123456789124357689128345679,27,192,10,117573120
123456789124357689128356479,28,168,9,117573120
123456789124357689128359467,29,120,4,78382080
123456789124357689134258679,30,192,5,39191040
123456789124357689134268579,31,288,28,235146240
123456789124357689135268479,32,228,22,235146240
123456789124357689135278469,33,276,26,235146240
123456789124357689136258479,34,168,9,117573120
123456789124357689136278459,35,180,30,470292480
123456789124357689137268459,36,216,20,235146240
123456789124357689138259467,37,156,26,470292480
123456789124357689138269457,38,228,11,78382080
123456789124357689158267349,39,120,6,117573120
123456789124378569129356478,40,96,2,3265920
123456789124378569135279468,41,192,8,78382080
123456789124378569137245689,42,516,9,26127360
123456789124378569157268349,43,168,6,39191040
123456789147258369159267348,44,120,2,4354560
-------------------------------------------------
sum:11352,416,4741632000


60713 out of the 85184=44^3 tupels of 3 members
from the list can be joined to form a valid 9*9 sudoku.


-Guenter Stertenbrink, sterten(-at-)aol.com

[dukuso]

>Posted: Fri Jul 29, 2005 7:20 pm Post subject:
>5,472,730,538
>
>
>
>Might this number be the number of solutions which give a
>valid sudoku come from 3 horizontal chutes [one each of Red
>Eds 44] combined with the only combination of 3 vertical
>chutes which give a valid solution.
>
>Each essentially different valid sudoku is one of a
>combination of 3 horizontal and 3 vertical chutes - in a
>particular combination of the 44 chutes.
>
>number of 44^3 intersecting with 44^3 [if they are valid
>sudoku] = 5,472,730,538
>
>maybe
>
>
>coloin
>
>
>
>Joined: 06 May 2005
>Posts: 84
>Location: Oxford
>Posted: Tue Aug 02, 2005 5:37 pm Post subject:
>
>
>
>Logically following on from my last post
>
>5,472,730,538 is the number Red Ed calculated for "essentially
>different grids",
>44^6 = 7,256,313,856 Healthily above and allows for many grids
>that dont turn up a solution.
>
>coloin wrote:
>Logically following on from my last post
>
>5,472,730,538 is the number Red Ed calculated for
>"essentially different grids",
>44^6 = 7,256,313,856 Healthily above and allows for many
>grids that dont turn up a solution.
>
>
>
>dukuso wrote:
>Let S be the collection of the 84 subsets of {1,..,9} of
>size 3.
>Let T be the collection of ...........................
>............................................
>60713 out of the 85184=44^3 tupels of 3 members
>from the list can be joined to form a valid 9*9 sudoku.
>
>
>-Guenter Stertenbrink, sterten(-at-)aol.com
>
>
>Ah.......
>I was under the impression that this calculation was a repeat
>of the Bertrand enumeration - although I did wonder because of
>Red Eds response if it was a quick way to determine the
>"essentially different grids". If this is the case it
>certainly deserves / deserved more credit.
>
>I did try to follow it -
>
>Does the 60713 expand in any way to give the number of
>essentially different grids ? - 5472730538 - forgive me if
>this is implied.
>
>It perhaps needs to be reposted and expanded [!] as it is
>relevant perhaps to our work on finding a grid within withch
>is a 16er.
>
>You were certainly on the case of the 3 horizontal "tupels" or
>bands giving a valid suduku - see above quote. I dont think
>Red Ed spelled out exactly what he had done in his calculation
>- he perhaps was a little miffed that you confirmed his
>magnificent work so neatly.
>
>That also explains your understanding of the 44^2 concept a
>while back.
>
>I think it is 44^6 now - as the vertical component of 3 stacks
>has a value for classification puposes - which may or may not
>be relevant.


I'm also a bit confused about this all sometimes.
I don't remember exacly my programs from June and what I did.

I think, I did also calculate the number of equivalence-classes of
grids if we don't consider transposed grids as equivalent,
it was a little less than 1e10.

Two nonequivalent grids can still have the same gangster-6-tupel,
also there are 416 nonequivalent bands, only if we allow
permuting the minicolumns we get the 44-gang.

It would be interesting to determine the number of possible
gangster-6-tupels, I'm not sure whether I could do it.
When you fix a grid, you could typically permute the
minicolumns in millions of ways to get another sudoku-grid
without changing the horizontal gangsters.
We have to do this for about 2 million combinations AFAIR.
So, that makes >1e12 grids to check, which seems to be too many.

For any of the 60713^2 possible gangster-6-tupels
we could check whether there is a sudoku-grid with it.

Start with: for any pair (g1,g2) of gangsters, find all
B1,B2,B3,B4,B7 45-cell-sudokus with first band from
class g1 and first stack from class g2,
which reminds to your posts earlier here.
Well put that on the "to do" list.


Guenter.

[coloin]

That is the posting. !

>Two nonequivalent grids can still have the same gangster-6-tupel,

I can sort of see that this will indeed be so !

>also there are 416 nonequivalent bands, only if we allow
permuting the minicolumns we get the 44-gang.

The 416 is a number which you refer to a lot -
>4) Q(M) number of classes of compatible bands (from the gang of 416) is its first mention from you - I believe

Frazer and Red Ed found the 1st band reduction in the sequence
36288 - 306 - 72 - 44 eventually.

I am sure the 416 is a sensible way of looking at the band - maybe you could show a portion of it - apologies if you have already posted it - I dont think you have !

>60713 out of the 85184=44^3 tupels of 3 members have a valid suduku - as you calculated.

>For any of the 60713^2 possible gangster-6-tupels - we could check whether there is a sudoku-grid with it.

Is it not 60713 ?!!!!! If not what does the result represent ?

>B1,B2,B3,B4,B7 - Yes - I remember - that was what I was on about although I was in a roundabout way just repeating the enumeration. I then realized it wouldnt be an easy one to work out - at least not the way I thought !

I think the 16 is the final exercise

Regards

[dukuso]

hi Coloin,

you convinced me, I'm doing the B1B2B3B4B7-calculation now.

Hopefully I'll get the Bertram-number, else there is a bug :-(

give me some hours.
Not that it couldn't be done faster, it's just all
tedious to implement.


Guenter.



no fun. I had some bugs and logical errors.
I.e. the 44*44 thing which Frazer warned us about .
There will be about 3 million essentially different
B1B2B3B4B7s , I estimate. Each with 2000-4000 solutions.

[coloin]

I didnt mean to encourage you to re-evaluate N......
but since you are trying - it possibly will be useful ... as to the 16.....maybe thats why your doing it...................

and I agree with the 2000 - 4000 estimate [though I have found some a lot higher - which makes me wonder if there are some a lot lower !]

3 million essentially different - certainly there will be scope for variation

Ive recently looked at a few B12347s - Its not as simple as 44^2 or 416^2 as inter changing vertical clues in box 3 gives different numbers of solutions

Somehow perhaps you need to reclassify - maybe the 384/392/400/432/448 effect is relevant to this - but it cant just be this because I got different numbers of solutions as above - I suppose somewhere in the grid I changed a box combo I didnt know about

Ah .....of course it is

The 44 Gangsters deal with B456789 all undetermined and dependant on B123 - easy

If there are 3 million essentially different "T-birds" Given a B12347

1-Each will be different from another due to
B2 box combo effects on B4&B7
B3 box combo effects on B4&B7 eg each 44*44 will have 4 box combo combinations

T-bird xxxx = 42,34,3,4,4,4
= [ganster 42] with [ganster 34] ,[B2/B4 = 392], [B2/B7=400],[B3/B4=400],[B3/B7=400]

which has 2500 solutions for example

2-Will give different solutions because
simple gang effects eg B2 will have a 44 ganster withB5&B8
more cross combo effects B2 with B6&B9
more cross combo effects with B1 on B5689 etc etc

your solution counter deals with all these !

How have you classified them ?

Is this garbage ?

Colin

[dukuso]

I postpone this due to bugs.
The "recalculation" of N would just ensure that it works correctly.

[coloin]

Yes its academic somewhat and difficult.

you do have to reclassify

The gangsters only work in one "dimension" - thats why they can be reduced to 44 from 9!*56*216*216.

reducing their effective box combinations is Frazers worry - rightly - it stumped us very early on

Now there are 36 - not 18 box combos per grid

that actually gives us the scope to have 3 000 000 different B12347s

I think sticking to the gangsters is easier !

[dukuso]

one of my mistakes yesterday was, that I wanted to start
with one of the 44 as B1B2B3.
That gave about one million B1B2B3B4B7s, where I allowed
permuting the minicolumns in the B2B3 and the minirows in the B4B7.
This doesn't influence the number of solutions for B5B6B8B9.

But we loose 3 symmetries for permuting the stacks, when
we choose a nonsymmetrical configuration like B1B2B3B4B7,
so we must allow 3 forms of each gangster as B1B2B3,
allowing any of the 3 boxes as B1.