Su-Doku's maths

Everything about Sudoku that doesn't fit in one of the other sections

Postby gfroyle » Fri Nov 11, 2005 12:33 am

Moschopulus wrote: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
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Moschopulus » Fri Nov 11, 2005 12:57 am

Oh yeah, I forgot those numbers were there. Thanks!
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby kjellfp » Fri Nov 11, 2005 7:33 am

Moschopulus wrote: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.

Moschopulus wrote: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.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby dukuso » Fri Nov 11, 2005 8:36 am

gfroyle wrote:
Moschopulus wrote: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 ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby PatmaxDaddy » Sat Nov 12, 2005 1:04 am

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
PatmaxDaddy
 
Posts: 63
Joined: 18 October 2005

Postby dukuso » Sat Nov 12, 2005 7:07 am

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 ;-)
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby gfroyle » Sat Nov 12, 2005 9:55 am

dukuso wrote: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
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby kjellfp » Mon Nov 14, 2005 8:34 am

dukuso wrote: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.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby PatmaxDaddy » Tue Nov 15, 2005 4:28 am

kjellfp wrote: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
PatmaxDaddy
 
Posts: 63
Joined: 18 October 2005

Flattened minicol 3tuple

Postby LarryLACa » Thu Nov 24, 2005 5:32 am

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?
LarryLACa
 
Posts: 32
Joined: 24 August 2005

Re: Flattened minicol 3tuple

Postby kjellfp » Thu Nov 24, 2005 2:03 pm

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.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby cmorpurgo » Fri Nov 25, 2005 3:15 pm

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
 
Posts: 4
Joined: 25 November 2005

Postby cmorpurgo » Fri Nov 25, 2005 3:18 pm

cmorpurgo wrote: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
 
Posts: 4
Joined: 25 November 2005

Postby cmorpurgo » Fri Nov 25, 2005 3:20 pm

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
cmorpurgo
 
Posts: 4
Joined: 25 November 2005

Postby Red Ed » Fri Nov 25, 2005 11:04 pm

cmorpurgo eventually wrote: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 }
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General