The New Sudoku Players' Forum

[Red Ed]

Ah, good, looks like we might get verification of mine and Frazer's numbers after all; fingers crossed!

Another interesting open problem is the number of classes,
if we allow the 9!*6^8*2 symmetry operations plus permuting
inside minirows plus permuting inside minicolumns (iterated)

What operations are you allowing? If I'm literally allowed to pick any of the 27 minicols or 27 minirows and permute its contents, and repeat for other minicols/rows as often as I like, then I can use these ops to get from any grid to any other, so the answer to the problem is 1.

But I'm sure you don't mean that ...

[dukuso]

Ah, good, looks like we might get verification of mine and Frazer's numbers after all; fingers crossed!

Another interesting open problem is the number of classes,
if we allow the 9!*6^8*2 symmetry operations plus permuting
inside minirows plus permuting inside minicolumns (iterated)

What operations are you allowing? If I'm literally allowed to pick any of the 27 minicols or 27 minirows and permute its contents, and repeat for other minicols/rows as often as I like, then I can use these ops to get from any grid to any other, so the answer to the problem is 1.

But I'm sure you don't mean that ...

permute all the 27 minirows so that you get another valid sudokugrid.
Then do the same with the 27 minicolumns.
Probably we will get all sudokugrids ?!

[kjellfp]

Interresting thread. May I contribute?

Without knowing about this thread, I asked myself the same question about the number of Sudoku grids, and eventually created a program that took 7 seconds to find the number 6670903752021072936960 of Sudoku grids. After reading the thread, I realize that my answer was only dukuso revisited.

Some ask how the Z-numbers in dukuso's notation can be calculated quickly. It took my program only a fraction of a second to do it. This is how:

I look at the set X of all column configurations ( (S1...S9) from dukuso's notation) with some limiting properties:

S1,S2,S3 is {123}{456}{789}.
S4,S5,S6 are ordered (with respect to their minimal elements)
S7,S8,S9 are ordered.

This gives 280 choices for S4,S5,S6 and also for S7,S8,S9, so the size of X is 280^2.

For each element of X, I find the N-numers (number of valid sudoku grids with the given column configuration), and I find the equivalence class representatives and Z-numbers (size of equivalence class in X) as follows:

S4,S5,S6 can be limitied to be one of the 5 following to have every equivalence class represented:
{123}{456}{789} or
{123}{457}{689} or
{147}{258}{369} or
{147}{236}{589} or
{124}{378}{569}

(actually fewer according to the listings of the 44-gang, but it's not worth proving it to reduce calculation time).

I then iterate through these choices for S4,S5,S6 and the 280 choices for S7,S8,S9.

If the set S=(S1..S9) i come up with has already been found in an earlier equivalence class (easy to keep track of), there's nothing to do. If not then
- First find the number of all valud 3*9 sudoku rows derived from S (the N-number), and
- Then find all elements in the group.
The elements in the group are found by permuting the boxes, permuting the cols S1..S3, repermute the numbers to bring S1.S3 back on the base form, and then run through all 6^3 number permutations leaving S1..S3 fixed. I also store the N-numbers in a 280x280 array, representing the elements of X, to make the final counting more efficient.

I end up with the same famous 44 equivalence classes, and the counting is done just like dukuso describes it. Thanks to the 280x280-matrix, finding the N-numbers is now trivial.

[dukuso]

Interresting thread. May I contribute?

Without knowing about this thread, I asked myself the same question about the number of Sudoku grids, and eventually created a program that took 7 seconds to find the number 6670903752021072936960 of Sudoku grids. After reading the thread, I realize that my answer was only dukuso revisited.

Very good.
I knew it could probably be done in less than a minute,
but 7 seconds is amazing !
You must have a very efficient implementation.
Thanks also for explaining the fast calculation of the Z,N- numbers
to RedEd, I was about to walk through my old files.
I only remembered that it could be done quickly, but not how.
I had probably used another method, though. Don't remember.

Now, will you confirm that there are 306693 G-classes ?

see this post:
http://www.setbb.com/phpbb/viewtopic.php?t=194&mforum=sudoku

I had some problems recently which made me doubt
the correctness of that calculation.

-Guenter.

[kjellfp]

Another thing:

I have been thinking about confirming the 5e9-number of essentially different sudoku grids. It may also be used to again reconfirm the total number of grids.

At my first appraoch for finding all grids (less efficient than all other solutions, and thus not implemented), I was planning to do it as follows:

- Run through all T-classes
- Find the number of grids in the class

How can this be done?

1.1 We know there are 416 classes of sudoku rows modulo the 9!*6^5 legal operations. Run through one representative for each of them, put it on the first row of our sudoku grid.
1.2 Then run through the 416 again, and find all ways to let them be filled into the second row, without comming in conflict with the first.
1.3. Then we know the column configuration of the last row, run through all ways to complete it to a grid.

This way we will visit all T-classes. We must be sure to visit each one excactly once, more about this below.

2.1 How do we find the size of a T-class? Well, it's number of elements is simply 9!*6^8/#Aut(T) where Aut(T) is the automorphism group of T. This is normally 1, in general not particularly big, and easy to find, se below.

To help me narrow my search and recognize equivalence classes from each other, I would like to introduce some numerical invariants which
- Are as quick as possible to compute
- Separates non-isomorphic rows/grids as good as possible
- Does not separate isomorphic rows/grids

One of these are the signatures. Given a 3x9 sudoku row, say

482 631 579
157 429 836
396 875 241

and look at a number N in {1..9}. For each number i from 1 to 9, let s_i be 0 for i=N, while s_i otherwise is the number of times N and i are on the same row within the same box. Let the numbers t_1..t_9 in the same way count when the numbers are on the same column on the row. Then create a 2x9 matrix with the s_i and t_i. Example N=1 with the row above:

011111000
001111002

If we reorder this by, say the top row, then the bottom row, we get

000011111
000201111

There are totally 50 different such ordered matrices that can occur, so we represent it by a number from 1 to 50. This is what I call the row signature of N=1 in the given row.

Collecting all row signatures for the numbers N=1..9 might give a number matrix, say

13 15 43 11 5 3 5 39 14

Reorder them into

3 5 5 11 13 14 15 39 43

This row is the row signature of the 3x9 sudoku row. It is an invariant for the permutation group. It strongly, but not completely, also separates the 416 classes. An additional numerical invariant has helped me to divide the 416 classes into 400 groups with one unique eleemnt, and 8 groups with two elements each.

The row signature also helps us find the automorphism group. Since the numbers in the row signature were all different, its automorphism group is trivial with respect to number permutations.
In general, the row permutation groups often have trivial automorphism groups. This again can be used to find the (often trivial) automorphism groups of T. Row signatures also helps me to give an orderding of the different rows, helping me recognize earlier found T-classes, and to cut braches in the search tree (like on point 1.2 above, if the second row comes before the first, forget about it).

Also, when we have a T-class and all its row signatures, we can find its column signatures, to find out wether they belong to the same class or not. This is how we find the number of S-classes.

Implementation has reached far, but is not completed.

[dukuso]

Another thing:


1.1 We know there are 416 classes of sudoku rows modulo the 9!*6^5 legal operations. Run through one representative for each of them, put it on the first row of our sudoku grid.
1.2 Then run through the 416 again, and find all ways to let them be filled into the second row, without comming in conflict with the first.
1.3. Then we know the column configuration of the last row, run through all ways to complete it to a grid.

This way we will visit all T-classes. .

just a quick remark:

In 1.2 you will need more than 416, since the first band
already fixed the permutations of the columns.

I'll read the rest of the maessage later

[kjellfp]

just a quick remark:

In 1.2 you will need more than 416, since the first band
already fixed the permutations of the columns.

I'll read the rest of the maessage later

I know. so for each of the 416 classes, I also need to run through all possible ways to operate on it so it can be filled into the second row without comming in conflict with the first.

I'm sure this is not faster than earlier methods. But it can be used for a confirmation on the number of S-classes and the number of all suduko grids in one go.

[kjellfp]

And yet aother thing:

Some has dared to ask for the number of 16x16 soduko grids, grouped into 4x4 boxes. I'd rather like to call this 4x4-sudoku, which is a description of the box size.

In general, we can play with NxM-sudoku. These are boards of size NM x NM, divided into M rows and N columns of NxM boxes.

What are the number of NxM-sudoku grids for various values of N,M? Clearly NxM MxN is the same case, so we assume N >= M.

M=1 is just NxN latin squares. It has been solved up to N=11.

2x2 is trivial, and by the methods given so far, I had few problems doing 3x2 by hand. It has been reconfirmed by computer.

4x2 hasn't been treated yet, but it seems simpler than 3x3.

3x3 is what this thread is basically about.

Now what about 4x3? I have just looked a little bit on it, at it seems to be a pretty tough job.

Doiong 4x4 is pointless before we are able to handle 4x3.

In general, the complexity and size of the problems increase extremely. From my point of view, I think we might solve 4x3, maybe. But never 4x4. No way!

[dukuso]

I tried to do 4*16 sudoku, just as the 3*9 with the 44 "gangsters",
but failed.
Do you think, 4*16 can be done ? How many classes ?

[dukuso]

>Interresting thread. May I contribute?

looking forward...
Do you have an estimate on the amount of contributions you are planning ?
Just good to know, since some people come and go quite quickly.

>Without knowing about this thread, I asked myself the same question
>about the number of Sudoku grids, and eventually created a program
>that took 7 seconds to find the number 6670903752021072936960 of
>Sudoku grids. After reading the thread, I realize that my answer
>was only dukuso revisited.

I also stored all possible triples of 3*9-classes so it took a bit longer.
7727104 triples, later I found that half of them had been enough,
maybe I even missed some further symmetries.

>Some ask how the Z-numbers in dukuso's notation can be calculated
>quickly. It took my program only a fraction of a second to do it.
>This is how:

OK, but now forgetting everything which is found by clever human reasoning
or precalculation, how fast would be a program which computes the number
of sudokugrids starting from zero knowledge ?
We won't know that there are 44 classes etc.
Is it still <30sec. with 1GHz ?

[dukuso]

>I have been thinking about confirming the 5e9-number of essentially
>different sudoku grids. It may also be used to again reconfirm the
>total number of grids.
>
>At my first appraoch for finding all grids (less efficient than all
>other solutions, and thus not implemented), I was planning to do it
>as follows:
>
>- Run through all T-classes

OK.

>- Find the number of grids in the class

why ?

>How can this be done?
>
>1.1 We know there are 416 classes of sudoku rows modulo
> the 9!*6^5 legal operations. Run through one representative
> for each of them, put it on the first row of our sudoku grid.
>1.2 Then run through the 416 again, and find all ways to let them
> be filled into the second row, without comming in conflict
> with the first.

416 won't be enough here

>1.3. Then we know the column configuration of the last row,
> run through all ways to complete it to a grid.

just run through all triples of band-classes which you found
whith your 7s-program and try to permute the minicolumns
in all possible ways.

>This way we will visit all T-classes. We must be sure to visit
>each one excactly once, more about this below.
>
>2.1 How do we find the size of a T-class? Well, it's number
> of elements is simply 9!*6^8/#Aut(T) where Aut(T) is the
> automorphism group of T. This is normally 1, in general
> not particularly big, and easy to find, se below.
>
>To help me narrow my search and recognize equivalence classes
> from each other, I would like to introduce some numerical
> invariants which
>- Are as quick as possible to compute
>- Separates non-isomorphic rows/grids as good as possible
>- Does not separate isomorphic rows/grids
>
>One of these are the signatures. Given a 3x9 sudoku row, say
>
>482 631 579
>157 429 836
>396 875 241
>
>and look at a number N in {1..9}. For each number i from 1 to 9,
>let s_i be 0 for i=N, while s_i otherwise is the number of
>times N and i are on the same row within the same box.
>Let the numbers t_1..t_9 in the same way count when the
>numbers are on the same column on the row. Then create
>a 2x9 matrix with the s_i and t_i. Example N=1 with the row above:
>
>011111000
>001111002
>
>If we reorder this by, say the top row, then the bottom row, we get
>
>000011111
>000201111
>
>There are totally 50 different such ordered matrices that can occur,
> so we represent it by a number from 1 to 50. This is what I call
> the row signature of N=1 in the given row.
>
>Collecting all row signatures for the numbers N=1..9 might give a
>number matrix, say
>
>13 15 43 11 5 3 5 39 14
>
>Reorder them into
>
>3 5 5 11 13 14 15 39 43
>
>This row is the row signature of the 3x9 sudoku row. It is an
>invariant for the permutation group. It strongly, but not completely,
>also separates the 416 classes. An additional numerical invariant
>has helped me to divide the 416 classes into 400 groups with one
>unique eleemnt, and 8 groups with two elements each.

Can you use this to write a program which reads sudokus and displays
the 6 numbers from {1,..,416} for the S-classes of their 6 chutes ?
I did it for the 44 G-classes, and it was quite useful, but
I never came to do it for the 416 S-classes.

>The row signature also helps us find the automorphism group.
>Since the numbers in the row signature were all different,
>its automorphism group is trivial with respect to number permutations.
>In general, the row permutation groups often have trivial
>automorphism groups. This again can be used to find the
>(often trivial) automorphism groups of T. Row signatures
>also helps me to give an orderding of the different rows,
>helping me recognize earlier found T-classes, and to cut
>braches in the search tree (like on point 1.2 above,
>if the second row comes before the first, forget about it).
>
>Also, when we have a T-class and all its row signatures,
>we can find its column signatures, to find out wether they
>belong to the same class or not. This is how we find the
>number of S-classes.

number of T-classes would be sufficient. Or even number of
T-invariant classes.

>Implementation has reached far, but is not completed.

you will have to generate all 1.1e10 T-classes.
My way to do it would be to generate a graph for each
T-class and its transpose, then test the 6 G-classes,
if they match run "Nauty" to produce canonical forms,
compare them.
This whole process would take me an estimated 5-10 days.
Just generating the 1e10 T-classes
(I can see no way how to avoid this)
takes me 100 hours or such. Maybe you can help to do it faster...


-Guenter.

[kjellfp]

dukuso wrote:

> Do you have an estimate on the amount of contributions you are planning ?
> Just good to know, since some people come and go quite quickly.

No idea, actually, I'm too unpredictable as a person. But as long as both I and others find things interresting, I'm in. My plans are not just to tell my ideas, and then disappear. But if the discussion goes on other places, send me there (you have already provided me with one link, leading to other threads. Thanks)

> 7727104 triples, later I found that half of them had been enough,
> maybe I even missed some further symmetries.

That's my number too. 44 * 56^3. I don't use any symmetries then, 7 seconds was good enough for me.

The symmetry of swapping box 4,5,6 with 7,8,9 should give a factor 2 reduction when done correctly.

> We won't know that there are 44 classes etc.

My program did not "know" about the 44-grouping. All preinformation used is trivially proved by hand. I can send you the code, but first I have to make it a bit more readable.

[kjellfp]

dukuso wrote:

> >- Find the number of grids in the class

> why ?

This was from the time when I wanted to find the complete number of grids, before finding the 7 seconds solution. For only investigating the T-classes, it's not neccessary.

> >1.2 Then run through the 416 again, and find all ways to let them
> > be filled into the second row, without comming in conflict
> > with the first.

> 416 won't be enough here

For a given first row, there are more than 416 ways to fill the next, yes. But I run through them by first picking one of the 416, and then permuting it various ways.

> Can you use this to write a program which reads sudokus and displays
> the 6 numbers from {1,..,416} for the S-classes of their 6 chutes ?

Yes.

> Just generating the 1e10 T-classes[..] takes me 100 hours or such.

I'm also afraid it will take too much time.

Actually, I have more or less abandonned this idea. Just thought about sharing the signature ideas, as this might be used somewhere else (like as you mentioned: To find which of the 416 that describes each row)

[frazer]

I look forward to examining Kjell's method and results more closely when things are less busy at work! I'm also amazed by the 7 second figure -- that's great! I hope that you can confirm the S-classes and T-classes numbers too.

[kjellfp]

dukuso wrote:

That's my number too. 44 * 56^3. I don't use any symmetries then, 7 seconds was good enough for me.

The symmetry of swapping box 4,5,6 with 7,8,9 should give a factor 2 reduction when done correctly.

Uups.. I lied.

The two factor symmetry was already implemented - and quite forward to implement.