by **dukuso** » Wed Oct 05, 2005 1:35 pm

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