The New Sudoku Players' Forum

[dukuso]

there are 6670903752021072936960 sudokugrids from
5472730538 equivalence classes ("S-classes")

where grids are S-equivalent, if they can be transformed into
each other by

permuting symbols
permuting the 3 rows in some stack
permuting the 3 columns in some band
permuting the 3 stacks
permuting the 3 bands
transposing

these 6 groups of transformations do commute and give
9!*6^8*2 transformations in total.


When we omit transposition, we get xxx "T-classes",
xxx S-classes have only 1 T-class, the other S-classes
have 2 T-classes.


there are only 306693 classes ("G-classes"), when we also allow
permuting the 3 entries in any minicolumn but remove transposition.
These 306693 classes generate 11555445688 sudokugrids,
by permuting minicolumns modulo permuting rows in a band,
at least one from each T-class. They can be generated in about
10? minutes but storing them requires too much memory.

Many sudoku-properties are an invariant of the S-class and thus
an invariant of the T-class and can be checked by checking
these 11555445688 generated sudokus.

(planning to fill in the missing numbers later...)


answers and updates to:
http://www.setbb.com/phpbb/viewtopic.php?t=194&mforum=sudoku

[Moschopulus]

there are only 306693 classes ("G-classes"), when we also allow
permuting the 3 entries in any minicolumn but remove transposition.
These 306693 classes generate 11555445688 sudokugrids,
by permuting minicolumns modulo permuting rows in a band,
at least one from each T-class. They can be generated in about
10? minutes but storing them requires too much memory.

Many sudoku-properties are an invariant of the S-class and thus
an invariant of the T-class and can be checked by checking
these 11555445688 generated sudokus.

Thanks for the 306693 number. Can you store these 306693 grids in one file? How big?

-----------------------------------------------------

Pity the property of having a 16 is not an invariant of the G-class.

-----------------------------------------------------

Say two grids are U-equivalent if one can be transformed into the other by

permuting symbols
permuting the 3 rows in some band
permuting the 3 columns in some stack
permuting the 3 stacks
permuting the 3 bands
transposing
interchanging digits/cells in an unavoidable set

How many U-classes are there?

[dukuso]

Can you store these 306693 grids in one file? How big?

**26MB, 3.8MB compressed. Maybe I can upload or send a CD
**if you are interested. I'm not 100% sure about this number, though.

Say two grids are U-equivalent if one can be transformed into the other by

permuting symbols
permuting the 3 rows in some band
permuting the 3 columns in some stack
permuting the 3 stacks
permuting the 3 bands
transposing
interchanging digits/cells in an unavoidable set

How many U-classes are there?

still a lot. We wondered about it some time ago here.
It might be possible to get an estimate by picking
some of the 5e9s by random and examining them.
Maybe I'll try it later

[frazer]

I've been following recent posts with some interest, especially concerning the minimum number of clues. I wanted to ask whether Guenter was using the result for S-classes which Red Ed and I found, or whether he had checked the number 5472730538 independently? If the latter, did you use a different method?

I didn't respond to an earlier question (sorry!): our method does not construct these grids, merely counts how many there are. A full list would be very interesting.

The calculation of the number of G-classes is great. The number of U-classes would be even more interesting to know, as Moschopulus remarks, although I imagine this is rather harder to do.

[dukuso]

I've been following recent posts with some interest, especially concerning the minimum number of clues. I wanted to ask whether Guenter was using the result for S-classes which Red Ed and I found, or whether he had checked the number 5472730538 independently? If the latter, did you use a different method?

** no. I wanted to try, but didn't yet. The main motivation was to
** assure, that my program works correctly.
** It would be a lot easier for me to determine the number
** of T-classes, that is Red-Ed's classes but with transposition discarded
** so about 1.1e10.
** If I have this, do you see an easy way to get the 5.4e9 from it ?

I didn't respond to an earlier question (sorry!): our method does not construct these grids, merely counts how many there are. A full list would be very interesting.

The calculation of the number of G-classes is great. The number of U-classes would be even more interesting to know, as Moschopulus remarks, although I imagine this is rather harder to do.

** hmm, I'm just wondering, what we might get, if we also
** allow permuting inside the minirows and transposing.
** Will we get all grids , only one class ??

[frazer]

OK. I've done the T-class calculation, after working out how to write a little program in GAP. I'll add the GAP output to the webpage.

The calculation was done in the same way as for the S-classes; namely, to average (over the group) the number of fixed grids up to relabelling. As I mentioned before, the T-group has 484 conjugacy classes, and it's just a question of working out which correspond to S-classes with fixed grids (there are 41 such classes). One then uses Ed's calculation of the number of fixed grids for each S-class. The final result is that there are 10945437157 T-classes. This means that 23919 S-classes have only 1 T-class, and the other 5472706619 have 2 T-classes.

In the event the calculation was rather easy -- sorry to dukuso for not doing it earlier, as it's been some weeks since he first asked it... (Again, independent verification would be good -- some of this calculation was done manually, and I may have mistyped something...)

[JohnB]

I am a newcomer, so pardon (and ignore) this if it has been discussed already.
In all the calculations of the number of possible Sudoku grids it helps greatly if we recognize that the first row can be "fixed" at 123456789, because all other grids can be obtained from one with this constraint by any one of 9! substitutions. Furthermore, the first number in the second row can be fixed at 4 (say) because all others can be transformed to this by one or two trivial column interchanges.
This reduces the number of grids by a factor of about 2.2e6: some slight help! I think the reduction factor is greater than this, but it gets messier.
(This is borrowing an idea from the "Magic Squares" puzzle, where they talk about "essentially different" squares. We need to consider only significantly different grids.

[JohnB]

Me again!
After I posted my neophytic reply I found dukosu's* contribution. It says what I said, and much more. I am not sure about concatenating the substitution permutation and all the row/column/stack/band permutations though; might some of the latter not be duplicating the former?
* even the name is permuted!

[mathsman]

I spent about four months on this problem and - corrections if I’m wrong are welcome - I believe the largest possible number of 9 by 9 puzzles following Su Doku rules to be 6,188,965,056. This was done by working out the exact number of possible placements of each of the nine numbers in the puzzle in consecutive order then multiplying the result in order to finalise the calculation. The result, (36^3)(17^3)(3^3) equals the answer. Therefore, if Su Doku was money, everyone on earth would be richer by one pound. I propose that this occur.

The answer to this problem is MINE! I have the copyright to the calculation! Haha!

Ahem. Any more questions?

[coloin]

I spent about four months on this problem

Thanks for your comments - please could you elaborate on your methods if indeed you are serious. I presume you have forgotton the factor of 9! in your answer.

Smart computor programmers have elucidated an answer which does have a 6 in it - but it is slightly bigger than your answer. Unfortunately working out the number of grids answer [ = number of puzzles at least] hasnt been possible for mortals like me - much that I would have liked to have done it myself.

I will politely refer you and anyone else to any of Frazer's recent postings - before anyone else does.

http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=330

However - if you are interested to help on the problem of the minimum number of clues - we could do with assistance on finding a "16".

Regards

[mcguirebarb]

I found myself asking myself the questions asked by this group over the weekend for the first time and was delighted to stumble across this forum....clearly I have some reading to do before I can contribute but one subsidiary question comes to me.....

With regard to the 5,472,730,538 solutions. I note that this number = 2*11*11*23*983243.

Perhaps it is just that I have recently finished the not very satisfying Kanigel biography of Ramanujan but I ask myself why the prime 983243 is appearing. Is this just some fluke or does this prime appear in any other mathematical analysis that anyone has stumbled across.

I also find it curious that the factor of 11^2 features. Is there some reasoning as to why this should be there.....

I'd like to think that there is some way of thinking about the problem which has not yet been described which would have produced one or other of these two numbers using pure logic rather than brute force. Call me a romantic dreamer...

[Moschopulus]

You're not the only one. We all wonder about a derivation of this number "by hand", i.e. not using a computer. But no-one can prove it. The same goes for the total number of grids, which is divisible by an even larger prime.

[dukuso]

the solution is the sum over some different counts.
So it can have any factor or not. Only the factors which are
in all summands can be explained.

The 5e9 number has not been verified AFAIK.
Frazer got another number than I for the T-classes
which could make the whole thing a bit suspicious (?)

Frazer, how certain are you about that 5,472,730,538 ?

[mathsman]

hmm... tricky

I presume you mean that possible squares that you can work out from sixteen clues (apologies if that sounds stupid).

By the way, how do you algebraically solve a magic triangle? presumably it must be half a magic square's formulae, but i can't make them tesselate.

[Red Ed]

the solution is the sum over some different counts.
So it can have any factor or not. Only the factors which are
in all summands can be explained.

That's not quite true: it's the sum of a bunch of numbers divided by 3359232. It's enough of an achievement that the result is an integer: I'd be quite impressed to see any factors explained away.

We shouldn't get excited about the large prime; it's to be expected:
http://www.mail-archive.com/mersenne@base.com/msg03890.html

The 5e9 number has not been verified AFAIK.

You're right this hasn't been verified: Frazer and I were hoping you'd do it!

Frazer got another number than I for the T-classes

Really? What answer did you get? And how? (in gory detail please: I sometimes find your short-and-clever posts a little hard to follow ...)