The New Sudoku Players' Forum

[Hammerite]

The answer to your 'reference number' question would have to be yes, but one wonders if it can it be short enough to be a significant improvement over printing the whole 81 digits.

Well, if there are 5,472,730,538 grids and we identify each one by one of the positive integers, then we can identify each one with just 10 digits instead of 81 Whether that's useful is another thing entirely!

EDIT: In order to make it even smaller, if you use letters as well as numbers - i.e. base 36, the letters being not case sensitive - we can do it in 7 digits!!! (Since 36^6=2176782336 but 36^7=78364164096)

[angusj]

Well, if there are 5,472,730,538 grids and we identify each one by one of the positive integers, then we can identify each one with just 10 digits instead of 81 Whether that's useful is another thing entirely!

Unfortunately, that is based on the false premise that for any one grid there is only one puzzle. The truth is for any one grid there can be many different puzzles.

[Hammerite]

Oh, I thought we were talking about grids...

I was already aware that some grids contain multiple, mathematically distinct puzzles. It came up in the topic I started on the minimum number of clues, which is around here somewhere.

If there was a systematic way of working out how many puzzles a grid has and of ordering them, then in principle the idea would still work. Assuming that no grid contains more than 10^k (or 36^k !) puzzles (for some positive integer k), you could form a puzzle identifier number by giving the 10 (or 7) digit reference number and adding k extra digits on the end. Of course you could only hope to do that if there was a systematic method of doing... what I said in the first sentence. :)

[angusj]

Oh, I thought we were talking about grids...

So you were, my mistake.
It seems to me a rather useless exercise to work out a reference number just for a grid (except for the mathematical challenge).

[Peter Morris]

Unless I am mistaken, you guys have now enumerated the 9x9 grid. Top job! However, have you been able to map the possible grids (i.e. given a unique ID, calculate the grid)? Or is this going to have to be a large look-up table, which I suspect to be the case, save for a pretty complex algorithm.

For either method, and given that the standard 9x9 puzzle is reflectively symmetrical, one only needs a further 25 bits of information to uniquely identify any given puzzle, indicating whether the cell displays its number or not. Using alphanumerics (upper case only), one could do that in a further 5 characters, leading to a 12 character string, identifying any puzzle. This is better than any hashing technique I've been able to create thus far and seems a useful shortcut.

So, the challenge is to determine the mapping algorithm or, given the grunt and the storage, creating a PHP page which returns an XML version of a 9x9 grid, given its 7-character ID. Deriving the puzzle using the 5 character suffix is trivial.

So, does puzzle 3KR WPA M9Y BBU require an x-wing? :o)

Pete

[dukuso]

The number of essentially different sudoku grids is

18,384,171,550,626,816 / 3,359,232 = 5,472,730,538

how many classes, when we consider transposed grids different ?

[Red Ed]

Unless I am mistaken, you guys have now enumerated the 9x9 grid. Top job! However, have you been able to map the possible grids (i.e. given a unique ID, calculate the grid)?

There seems to be some confusion about this, so let me attempt to clarify:

1. The number of ways of filling in an empty grid consistent with the rules of sudoku is 6670903752021072936960. This is now old news; see Bertram's post of May 23 at http://forum.enjoysudoku.com/viewtopic.php?t=44&start=138 .

2. The question just answered by me and Frazer (who also helped with the big number above) is: how many "essentially different" patterns are there within these 6.67x10^21 grids? We regard as essentially the same any two grids that differ only by relabelling the digits and/or applying some sequence of validity-preserving transformations such as rotation, transposition, row-band swapping and rows-within-band swapping. It's easy to show that the answer is something a bit bigger than Bertram's number divided by 3359232 x 362880, but somewhat harder to show that its exact value is 5472730538.

The way you go about getting the exact answer is to count grids for which one of the validity-preserving transformations merely has the effect of relabelling the digits. Here's a nice example, where rotation by 90 degrees just has the effect of mapping 1->3->9->7->1 and 2->6->8->4->2:

Code: Select all

124|567|893
378|294|516
659|831|742
---+---+---
987|123|465
231|456|978
546|789|321
---+---+---
863|972|154
495|618|237
712|345|689

I think all this stuff about reference numbers is a red herring and in any case is not something that anyone has provided the means to achieve. We can't even write down the 5472730538 essentially-unique grids, as the counting argument above doesn't work like that. And no, I am not volunteering to do anything about it!

how many classes, when we consider transposed grids different ?

Nor am I going to bother with this one. Sorry!

[datprogrammer]

A quick play with Ruby shows that a mere 8.2038817249341 e -10 %
of the total number of valid grids are distinct! That's a TINY number!!!

[coloin]

Yes great work Red Ed - a great sigh of relief when the two numbers divided without remainder ! - you can now have a couple of weeks off - but when you come back we will still need your help !!!!!!

So the classes with no invarients had the maximum number of transpositions and substitutions - but the classes which had invarients had a reduced number because they could be transposed into an equivilent grid - which when relabelled was identical. [Is this right ?]

I dont know if we have any further to go on this topic.

Regards

[angusj]

I dont know if we have any further to go on this topic.

Indeed we do! How many unique puzzles are there for each grid?

Yes, I know it's almost certainly an insoluble problem, not least because of the multiple opinions as to what constitutes a valid puzzle.

[dukuso]

I'm convinced now, that the whole enumeration can be done
in a few seconds. I got the correct number after 12 sec.
but included some data for the 44 chute-classes obtained
with another program.
Anyway, the trick is that we can coarsen the classes
by allowing to permute the minicolumns in a filled band.
This doesn't change the count of the possible completions
and gives only 3863552 different classes.

-Guenter.

[Red Ed]

I'm convinced now, that the whole enumeration can be done in a few seconds.

Excellent ... do please show us how you've done this.

EDIT: ah, hang on, I get it. Although permuting the top band to go through all the elements of a given class (of the set of 44) messes up the transformation whose action we're trying to fix, it nevertheless maps that transformation to another element of the same conjugacy class. I guess I'd still like to see the proof that everything fits together as it should (i.e. that we're counting everything once and only once), but I do at least believe the result now. Well done for the finding this trick -- I just wish you'd told us about it earlier!

[dukuso]

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]

[quote="dukuso"]coarsen the classes
by allowing to permute the minicolumns in a filled band.
This doesn't change the count of the possible completions
and gives only 3863552 different classes.
[/quote]

it's even less than this, I had fixed the upper band.
Divide by 3 and add those again with 2 bands from the same class
I haven't already calculated the exact number, it wasn't
important for the enumeration, which hopefully someone
will redo and report the exact counts of the classes ?!
We could list one member from each class and given a
sudoku-grid, quickly calculate it's address in each of the
classes together with the minimal sudoku in that class.

[Rael]

Hi folks, i just disagree with what is written on wikipedia .. well i'm sure the solutions are much lesser ^_^
(if we begin with an empty grid)

they must be something like <= 9! * (Binomial(110, 9)), 110 or a number very close to it. I'm pretty sure of this because the solutions of Sudoku, are strictly related to certain subsets of the set of the solutions of another problem, which is well known ^_^.