The New Sudoku Players' Forum

[gfroyle]

Does almost every grid have automorphism group of order 1?

Yes... the vast majority of them do, and this is to be expected. This will be true in the mathematically precise sense of the phrase "almost every" in that the proportion of grids with k^2 rows and columns with trivial automorphism group will tend to 1 as k tends to infinity. [I am just restricting to the square case to avoid ambiguity about what the "boxes" are, but it will be true for any sensible version]

The exact numbers for the regular Sudoku with 9 rows/columns were computed as part of the enumeration of equivalence classes of grids:


http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html


Cheers

Gordon

[Moschopulus]

Oh yeah, I forgot those numbers were there. Thanks!

[kjellfp]

Does almost every grid have automorphism group of order 1?

Yes. If you look at http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=454 you see that almost every isotropy group is trivial. This was also expected before I computed the table, as #grids/#T-classes is almost the same as 9!*6^8.

Which grids have group of order > 1? If there are so few of them, it should be possible to work them out.

I have already done this. Guenter asked for it, so I produced the entire list of class representing grids grouped into files depending on isotropy class size and wether the classes were transpose invariant. I have already sent him the files, except those that are non-transpose invariant with group order 2 (that file alone was 11 MB compressed, the others 300 KB all together).

Give me your mail address, and I'll send the same files to to you.

[dukuso]

Does almost every grid have automorphism group of order 1?

Yes... the vast majority of them do, and this is to be expected. This will be true in the mathematically precise sense of the phrase "almost every" in that the proportion of grids with k^2 rows and columns with trivial automorphism group will tend to 1 as k tends to infinity. [I am just restricting to the square case to avoid ambiguity about what the "boxes" are, but it will be true for any sensible version]

is it true for pandiagonal latin squares ?

[PatmaxDaddy]

Where can I look for a description of the current best method for computing N(Bertram), i.e. the one that you folks have running in well under 1 second? I imagine the description can be found scattered about in this rather long discussion thread, but is there the equivalent of Bertram & Frazer's June 20 paper that describes the current best method? Or perhaps is the current method essentially identical to Bertram's, but using 44 classes for B1-B3 instead of 71? I know how to compute these 44 classes (what I think you call the "gangsters"), and I know at least one way to use them to get N(Bertram), but my running time is more like a minute than a tenth of a second (down from the 5.5 hours in the version I described in previous posts).

One nice feature of Bertram & Frazer is that the description doesn't rely on group theory. My memory of groups is rather fuzzy, having studied it 32 years ago, but I've still got the course notes and I'm willing to re-read them if necessary.

Thanks for any pointers,
Bill

[dukuso]

it's probably too early for the summary. Ed has no time
actually, Kjell is merging their codes...
I got the code too, but didn't yet understand. Seems that
he uses a B12347 - method (?), filling blocks 1,2,3,4,7 first.

Maybe you can read the source code and then write a summary ;-)

[gfroyle]

is it true for pandiagonal latin squares ?

I don't know the exact answer for pandiagonal latin squares, but for almost every known combinatorially defined structure, we either have

(a) such severe restrictions that there are only a few examples of each size, and then the groups can all be large [example, projective spaces]

or, more usually,

(b) less severe restrictions so that the number of non-isomorphic objects increases as the size increases, in which case the group is almost always trivial (on average)

Of course, you could simply define something like "graphs with two vertices with identical neighbourhoods" which would fit into class (b) but always have a group of size at least 2, but the general principle is "if there's lots of them, the groups are almost always small".

Gordon

[kjellfp]

it's probably too early for the summary. Ed has no time
actually, Kjell is merging their codes...
I got the code too, but didn't yet understand. Seems that
he uses a B12347 - method (?), filling blocks 1,2,3,4,7 first.

Maybe you can read the source code and then write a summary ;-)

Not B12347 as we think about it. We (Ed and I) use the same approach: Do band by band by filling in the configurations (find which symbols to be in which box-column, but not the order). Before that, we have calculated the 44 equivalence classes of band configurations, and the number of complete bands from each configuration.

It's enough with one configuration from each of the 44 classes for the first band (the well-known set of gangsters), and multiply up with their equivalence class sizes. For the second band, there are 56^3 configurations, but because of symmetry (band 2-3 swapping), we reduce to 28*56*56. There is only one choice for the third band.

[PatmaxDaddy]

Not B12347 as we think about it. We (Ed and I) use the same approach: Do band by band by filling in the configurations (find which symbols to be in which box-column, but not the order). Before that, we have calculated the 44 equivalence classes of band configurations, and the number of complete bands from each configuration.

It's enough with one configuration from each of the 44 classes for the first band (the well-known set of gangsters), and multiply up with their equivalence class sizes. For the second band, there are 56^3 configurations, but because of symmetry (band 2-3 swapping), we reduce to 28*56*56. There is only one choice for the third band.

Thanks for the explanation. I knew that there were more symmetries in addition to the 44 gangsters that one needed to get the sub-one-second running times, and I figured that it had to be either in the bands or in boxes 4 and 7, but I wasn't sure which path would bear fruit. I'm going to try to program this when I get a chance and see how fast I can make it run. Not that I expect to add anything to the work you've already done, but being an old assembly language guy I just love making code run fast.

Bill

[LarryLACa]

In Eds validation of the gang of 44 equivalence classes for 3x3 Sudoku and in the T-class band generation approach we use the internally ordered mini-col 3-tuples to build a representative ID for the equivalence classes. E.g. give a band1 configuration like

Code: Select all

123 456 789  boxes--->123 123
456 789 123  2 & 3--->456 456
789 123 456  become:->789 789


from which we build the class id with col tuples as
147 258 369 147 258 369
I can see that this algorithm for building the ID works, very fruitfully. But how do we know that the within-minicol-ordering (flattening) doesn't throw away too much uniqueness? It's clear that the ID permutations of
{147}{258}{369}{147}{258}{369}
will cover all members of the equiv. class, but I don't understand why it's impossible than anyother equiv.class can't be buried in the same ID permutation space. Is this usage an application of the presentation of a group?

[kjellfp]

I'm not sure if I understand what you mean, but the equivalence relation leading to the 44 gangsters is given by permuting any minicolumn independently of the others (together with column permutations within boxes, box permutation, and symbol permutation). So bands with the same ID belong to the same equivalence class.

[cmorpurgo]

hi -- sorry this might have been discussed before, but I can't find the thread. Was there a discussion on the maximum number of squares that can be deleted on any game in order to get a non unique solution? (which seems to be 4) Is there a proof of this anywhere.

Carlo

[cmorpurgo]

hi -- sorry this might have been discussed before, but I can't find the thread. Was there a discussion on the maximum number of squares that can be deleted on any game in order to get a non unique solution? (which seems to be 4) Is there a proof of this anywhere.

Carlo

sorry i meant the minimum number of squares that can be deleted. i mean you can always find 4 squares so that if you delete them then you get 2 solutions, but not less than 3.

carlo

[cmorpurgo]

sorry i meant the minimum number of squares that can be deleted. i mean you can always find 4 squares so that if you delete them then you get 2 solutions, but not less than 3.

carlo[/quote]

oh my ...i am still not awake...I meant

"you can always find 4 squares (but not less than 4) to delete in order to get two solutions."

carlo

[Red Ed]

Was there a discussion on the minimum number of squares that can be deleted on any game in order to get a non unique solution? (which seems to be 4) Is there a proof of this anywhere.
...
you can always find 4 squares (but not less than 4) to delete in order to get two solutions.

You could try using the edit button on your posts ...

You are right that you can sometimes specify 77 clues (all but 4) and have multiple (2, in fact) solutions; but 78+ clues always specify the solution uniquely. That multiple solutions need at least 4 gaps comes from the fact that, to have some freedom of choice for the values in all the gaps, you can't have any row/col/box with just a single gap in it.

On the other hand, you are wrong to suggest that, in any grid, you can always find 4 squares to delete in order to get two solutions. Here's a grid that won't let you do that:

Code: Select all

  { 1, 2, 3, 4, 5, 6, 7, 8, 9 },   /* no 4-sets */
  { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
  { 7, 8, 9, 1, 2, 3, 4, 5, 6 },
  { 2, 3, 1, 5, 6, 4, 8, 9, 7 },
  { 5, 6, 4, 8, 9, 7, 2, 3, 1 },
  { 8, 9, 7, 2, 3, 1, 5, 6, 4 },
  { 3, 1, 2, 6, 4, 5, 9, 7, 8 },
  { 6, 4, 5, 9, 7, 8, 3, 1, 2 },
  { 9, 7, 8, 3, 1, 2, 6, 4, 5 }