## Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### ED Latin Square #1

If we were to produce a list of the 19,270,853,541 ED grids for 9x9 Latin Squares, in CF order, then this grid would be the first:

Code: Select all
`123456789214365897341278956432189675567891234658917342789523461896742513975634128`

Code: Select all
`123456789214365897341278956432189675567891234658917342789523461896742513975634128`

And, as Serg has shown above, the only grids for which the CF does not have "214......" in row 2 are the 1707 "no UA4" grids. So these grids would be the last 1707 in the CF order list. 1706 of these have "231......" in row 2, and so the very last grid in the CF order list must be the single grid with "234......" in row 2:

Code: Select all
`123456789234167895345678912416839527579324168658792341782913456891245673967581234`

Code: Select all
`123456789234167895345678912416839527579324168658792341782913456891245673967581234`

Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Re: ED Latin Square #1

Hi, Mathimagics!
Mathimagics wrote:If we were to produce a list of the 19,270,853,541 ED grids for 9x9 Latin Squares, in CF order, then this grid would be the first:

Code: Select all
`123456789214365897341278956432189675567891234658917342789523461896742513975634128`

Code: Select all
`123456789214365897341278956432189675567891234658917342789523461896742513975634128`
What is your method of finding this LS grid with lowest minlex metric?

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi Serg,

I just used a simple recursive solver, starting with givens 1-9 in row 1 and column 1. The solver selects the next cell to solve sequentially, and tests the candidate cell values sequentially, and stops at the first solution found.

Unlike Sudoku, where this method would take considerable time, for Latin Squares it's very quick.

Cheers,
MM

Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Hi, people!
I am sorry for my pollution of this thread, but just another post is coming outside from me...

Just some considerations concerning LS canonicalization algorithm.

Let's define for any pair of LS solution grid's rows Two-Row UA Minimality Index in the following way.

Index = 0 if pair of rows contains U4+U4+U4+U6 UA sets (4 distinct UA sets).
Index = 1 if pair of rows contains U4+U4+U10 UA sets (3 distinct UA sets).
Index = 2 if pair of rows contains U4+U6+U8 UA sets (3 distinct UA sets).
Index = 3 if pair of rows contains U4+U14 UA sets (2 distinct UA sets).
Index = 4 if pair of rows contains U6+U6+U6 UA sets (3 distinct UA sets).
Index = 5 if pair of rows contains U6+U12 UA sets (2 distinct UA sets).
Index = 6 if pair of rows contains U8+U10 UA sets (2 distinct UA sets).
Index = 7 if pair of rows contains no UA sets.

If we consider a pair of LS rows as r1/r2 candidates for LS minlex form, its Minimality Index will determine minlex form of r1/r2 rows.
Code: Select all
`123456789214365897     Index = 0123456789214367895     Index = 1123456789214537896     Index = 2123456789214567893     Index = 3123456789231564897     Index = 4123456789231567894     Index = 5123456789234167895     Index = 6123456789234567891     Index = 7`

So, you can see - the higher Index, the greater r1/r2 rows minlex form.
For any given LS solution grid we should calculate Indexes for all its 36 pairs of rows first. Then we should apply other 5 non-trivial paratopic transformations (in turn) and calculate Indexes for all grid's 36 pairs of rows. Now we can calculate minimal Index of the grid, choosing minimal Index value from 6 x 36 = 216 row pairs. During minlex form finding we should consider as r1/r2 rows candidates only row pairs, having minimal Index value of the grid. This trick can significantly reduce number of grid's checks during canonicalization.

Additional optimisation can be achieved by ignoring some paratopic transformation. For example, paratopic transformation No.3 (cd-exchange) leaves cells in their former rows and doesn't destroy two-row UA sets. So, it can be ignored, because this transformation doesn't change row pairs' Indexes. More careful analysis (see my next post) shows that paratopic transformations No.5 and No.6 can be ignored too.

So, typically we should check several row pairs only from 36 x 3 = 108 possible pairs as r1/r2 rows candidates.

Remark. The last LS in minlex form ("Solitary" Mathimagics' LS grid) has minimal Index value of 6. LS having minimal index of 7 (no two-row/two-column UA sets) are impossible.

Serg

[Edited. I changed part of the post, concerning paratopic transformation ignoring. I need some time to prepare more correct statements on this theme.]
[Edited2. I changed part of the post, concerning paratopic transformation ignoring, one more time. Hope now it's OK.]
Last edited by Serg on Thu Dec 12, 2019 11:06 pm, edited 1 time in total.
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Serg wrote:Hi, coloin!
There are 19,270,853,541 ED 9x9 LS. Only 1707 from them have no U4 unavoidable sets (see Mathimagics' post). The only ED LS solution grid (from 19 billions) has neither U4, nor two-row (two-column) U6 UA sets. So, we have 3 cases for 9x9 LS canonic form.
Code: Select all
`123456789214......3........4........5........6........7........8........9........     Case1: LS has at least one U4 UA set (19,270,851,834 LS grids - 99.999991 % approx.)12345678923156....3........4........5........6........7........8........9........     Case2: LS has no U4 UA sets, but has at least one two-row or two-column U6 UA set (1706 LS grids)1234567892341678953........4........5........6........7........8........9........     Case3: LS has no U4 UA sets and has no two-row or two-column U6 UA sets (1 LS grid found by Mathimagics)`

I see no other valiants of 9x9 LS minlex form. All 3 cases differ in r2c2 and r2c3 cells' pair.

Case1 - minimal size of grid's two-row or two-column UA sets is 4 (grid has U4).
Case2 - minimal size of grid's two-row or two-column UA sets is 6 (grid has two-row or two-column U6, but has no U4).
Case3 - minimal size of grid's two-row or two-column UA sets is 8 (grid has two-row or two-column U8, but has neither U4, nor two-row (two-column) U6).

Serg

Thanks Serg That was exactly the answer I was looking for !
And no problem with the development ongoing.
coloin

Posts: 1951
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

If it were useful to classify those 99.999991 % of grids

maybe the r2c2 combination in the minlex will define them .... [as all have the canonical r1c1 combination]
coloin

Posts: 1951
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

Hi, people!
Serg wrote:Just some considerations concerning LS canonicalization algorithm.
...
Additional optimisation can be achieved by ignoring some paratopic transformation. For example, paratopic transformation No.3 (cd-exchange) leaves cells in their former rows and doesn't destroy two-row UA sets. So, it can be ignored, because this transformation doesn't change row pairs' Indexes. I am not sure - what other paratopic transformation can be ignored.

I think paratopic transformations
Serg wrote:5. Cyclically exchaning rows, columns and digits (r --> c --> d --> r).
6. Cyclically exchaning rows, columns and digits (d --> c --> r --> d).

can be ignored too.

Transformation No. 5 (r --> c --> d --> r) can be reduced to two sequentially applied transformations No. 4 and No. 3 (first exchanging rows and digits, then exchanging columns and digits). After exchanging rows and digits we'll get LS image, that was already checked. Exchanging columns and digits doesn't change set of UA sets for every pair of rows.

Transformation No. 6 (d --> c --> r --> d) can be reduced to two sequentially applied transformations No. 2 and No. 3 (first transposing, then exchanging columns and digits). After transposing we'll get LS image, that was already checked. Exchanging columns and digits doesn't change set of UA sets for every pair of rows.

So, It's sufficient to use set of 3 paratopic transformations only (No. 1, No. 2 and No. 4) when we are searching for r1/r2 rows image, i.e. during Minimality Index calculation.

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi, coloin!
coloin wrote:If it were useful to classify those 99.999991 % of grids

maybe the r2c2 combination in the minlex will define them .... [as all have the canonical r1c1 combination]

Sorry, but those 99.999991 % of grids have the same digits in the cells r2c1, r2c2 and r2c3 ("214") in their minlex form.

But depending on UAs in the r1/r2 rows, first 2 rows of minlex form of those 99.999991 % of grids can look like
Serg wrote:Index = 0 if pair of rows contains U4+U4+U4+U6 UA sets (4 distinct UA sets).
Index = 1 if pair of rows contains U4+U4+U10 UA sets (3 distinct UA sets).
Index = 2 if pair of rows contains U4+U6+U8 UA sets (3 distinct UA sets).
Index = 3 if pair of rows contains U4+U14 UA sets (2 distinct UA sets).
...
Code: Select all
`123456789214365897     Index = 0123456789214367895     Index = 1123456789214537896     Index = 2123456789214567893     Index = 3`

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Ha .... well I wasn’t totally clear !
When I wrote r2c2 I did mean the whole of row 2 - which you have shown
And also the whole of column 2

I suppose it depends on the ED counts and how convenient each classification is

ED 27 clue 3row
vv
ED 32 clue r1r2+c1c2
coloin

Posts: 1951
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

Hi, coloin!
coloin wrote:When I wrote r2c2 I did mean the whole of row 2 - which you have shown
And also the whole of column 2

Minlex LS metric doesn't allow us to compute c2 column before computing r3-r9 rows. At least I don't know way to do it.
coloin wrote:ED 27 clue 3row
vv
ED 32 clue r1r2+c1c2

Do you mean another metric, other than minlex metric? (Say, the order: r1, r2, c1, c2, etc.)

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Well ... i suppose its going to be an easier task if we were to classify the grids wrt to the minlex r1r2r3 , [ but probably there are significantly less than 416]
coloin

Posts: 1951
Joined: 05 May 2005

### Latin Squares - Band Distribution

I have tested ~500,000 pseudo-random grids, canonicalising them and looking at the first 3 rows ("band 1"). This is a slow process as canonicalisation rates are currently ~3 grids/second (more on this later).

The distribution for this sample, by Serg's MI (Minimality Index):
Code: Select all
`Index 0: R2 = 214365897, count = 394798   78.866%Index 1: R2 = 214367895, count = 103966   20.768%Index 2: R2 = 214537896, count =   1828    0.365%Index 3: R2 = 214567893, count =      2                                 ------                      ed grids = 500594`

We already know that Index values 4, 5 and 6 correspond to the 1707 grids with no UA4. There are 1649 grids with Index 4, 57 grids with Index 5, and just 1 grid with index 6. There no grids with Index 7.

[EDIT] fixed the value above for Index 5 (1649 + 57 + 1 = 1707)

Band (rows 1 - 3) distribution for the sample is given below, one section per Index value. 245 different band (r123) settings have been identified for Index values 0 to 3:
Sample by Band value, Index 0, 65 entries: Show
Code: Select all
`123456789214365897341278956:   5244123456789214365897341527968:  40654123456789214365897341578926:  57757123456789214365897341579268:  43082123456789214365897341789256:   4924123456789214365897341789265:  15384123456789214365897341789526:  13029123456789214365897342178956:   4336123456789214365897342517968:  20969123456789214365897342578916:  29777123456789214365897342579168:  26827123456789214365897342789156:   6117123456789214365897342789165:   8651123456789214365897342789516:   7182123456789214365897345612978:    696123456789214365897345617928:  10680123456789214365897345678912:   8237123456789214365897345718926:  17092123456789214365897345718962:   6175123456789214365897345719268:   6419123456789214365897345728916:  10737123456789214365897345728961:   3984123456789214365897345729168:   4157123456789214365897345789126:   5077123456789214365897345789162:   5110123456789214365897345789216:   3830123456789214365897345798126:   3978123456789214365897345798162:   2661123456789214365897345798216:   3231123456789214365897351624978:     16123456789214365897351627948:   1570123456789214365897351642978:    333123456789214365897351647928:   3449123456789214365897351678924:   2386123456789214365897351678942:   2089123456789214365897351728946:    701123456789214365897351728964:     41123456789214365897351748926:   1615123456789214365897351748962:    604123456789214365897351749268:    604123456789214365897351782946:   1076123456789214365897351782964:    457123456789214365897351784926:    821123456789214365897351784962:    351123456789214365897351789246:    266123456789214365897351789264:    248123456789214365897351789462:    189123456789214365897351789624:    193123456789214365897351789642:    179123456789214365897351792468:    128123456789214365897351794268:    168123456789214365897351798246:    123123456789214365897351798264:    134123456789214365897351798426:     91123456789214365897351798624:    116123456789214365897351798642:    120123456789214365897352617948:    214123456789214365897352678914:    195123456789214365897352678941:    139123456789214365897352718946:     56123456789214365897352718964:     22123456789214365897352748916:     54123456789214365897352748961:     31123456789214365897352749168:     20123456789214365897352749618:      2`

Sample by Band value, Index 1, 127 entries: Show
Code: Select all
`123456789214367895341275968:    108123456789214367895341278956:     90123456789214367895341528976:   4918123456789214367895341529678:   3987123456789214367895341572968:   8132123456789214367895341578926:   3515123456789214367895341579268:   1709123456789214367895341582967:   2460123456789214367895341589267:   1532123456789214367895341589276:   1535123456789214367895341598276:   1117123456789214367895342175968:    600123456789214367895342178956:    248123456789214367895342179568:    393123456789214367895342189567:    119123456789214367895342518967:   1738123456789214367895342518976:   4761123456789214367895342519678:   3555123456789214367895342571968:   8287123456789214367895342578916:   3762123456789214367895342579168:   1770123456789214367895342581967:   2608123456789214367895342589167:   1624123456789214367895342589176:   1758123456789214367895342598176:   1368123456789214367895345612978:   2977123456789214367895345618927:   4028123456789214367895345618972:   2280123456789214367895345619278:   3254123456789214367895345671928:   3903123456789214367895345672918:   3358123456789214367895345678912:   1418123456789214367895345678921:   1207123456789214367895345679128:   1179123456789214367895345679218:   1213123456789214367895345681927:   1631123456789214367895345681972:    961123456789214367895345682917:   1288123456789214367895345682971:    818123456789214367895345689127:    413123456789214367895345689217:    399123456789214367895345718926:    720123456789214367895345719268:    765123456789214367895345719628:    710123456789214367895345728916:    676123456789214367895345729168:    573123456789214367895345729618:    536123456789214367895345789162:    261123456789214367895345789261:    225123456789214367895345798162:    146123456789214367895345798261:    121123456789214367895351628974:    100123456789214367895351629478:     87123456789214367895351642978:    342123456789214367895351648927:    187123456789214367895351648972:    261123456789214367895351649278:    382123456789214367895351672948:    501123456789214367895351674928:    156123456789214367895351678924:    194123456789214367895351678942:    206123456789214367895351679248:    387123456789214367895351679428:    329123456789214367895351682947:     49123456789214367895351682974:    250123456789214367895351689247:    155123456789214367895351689274:    190123456789214367895351689427:    120123456789214367895351689472:    127123456789214367895351692478:    125123456789214367895351694278:     11123456789214367895351698274:    218123456789214367895351698472:    154123456789214367895351728946:     29123456789214367895351729648:     16123456789214367895351748926:     89123456789214367895351749268:     72123456789214367895351749628:     66123456789214367895351782946:     98123456789214367895351782964:     73123456789214367895351784926:     71123456789214367895351784962:     83123456789214367895351789264:     46123456789214367895351792648:     54123456789214367895351794628:     59123456789214367895351798264:      4123456789214367895352614978:    118123456789214367895352618947:    156123456789214367895352618974:     97123456789214367895352619478:    110123456789214367895352671948:    203123456789214367895352674918:     66123456789214367895352678914:    139123456789214367895352678941:     48123456789214367895352679148:    139123456789214367895352679418:     50123456789214367895352681947:     68123456789214367895352681974:     64123456789214367895352684917:      7123456789214367895352684971:     22123456789214367895352689147:     42123456789214367895352689417:     14123456789214367895352714968:     27123456789214367895352718946:     42123456789214367895352719468:     44123456789214367895352719648:     29123456789214367895352748916:     80123456789214367895352748961:     16123456789214367895352749168:     31123456789214367895352749618:     47123456789214367895352789146:     37123456789214367895352789164:     25123456789214367895352789461:      4123456789214367895352798146:     39123456789214367895352798164:      1123456789214367895352814967:     26123456789214367895352814976:     34123456789214367895352819467:     11123456789214367895352819476:      5123456789214367895352849617:     18123456789214367895352871946:     12123456789214367895352874961:     11123456789214367895352879614:     14123456789214367895352914678:     10123456789214367895352948671:      3123456789214367895352971468:      4123456789214367895352981467:      8`

Sample by Band value, Index 2, 51 entries: Show
Code: Select all
`123456789214537896341672958:     20123456789214537896341675928:     44123456789214537896341678952:    101123456789214537896341685972:     88123456789214537896341692578:     40123456789214537896341695278:     50123456789214537896341698572:     42123456789214537896342165978:     58123456789214537896342168957:     12123456789214537896342168975:     98123456789214537896342169578:     49123456789214537896342671958:    130123456789214537896342675918:     71123456789214537896342678915:     75123456789214537896342678951:    148123456789214537896342681975:     76123456789214537896342685917:     50123456789214537896342685971:    112123456789214537896342691578:     98123456789214537896342695178:     61123456789214537896342698175:      5123456789214537896342698571:     37123456789214537896345162978:     63123456789214537896345168927:     19123456789214537896345168972:     38123456789214537896345169278:      8123456789214537896345261978:      6123456789214537896345268971:     18123456789214537896345269178:     12123456789214537896345671928:     24123456789214537896345672918:      8123456789214537896345678912:     31123456789214537896345678921:     14123456789214537896345681927:     22123456789214537896345681972:     22123456789214537896345682917:      6123456789214537896345682971:     16123456789214537896345691278:      6123456789214537896345692178:     10123456789214537896345698172:      2123456789214537896345698271:      4123456789214537896346125978:      1123456789214537896346175928:      6123456789214537896346178952:      4123456789214537896346179258:      2123456789214537896346182975:      4123456789214537896346185927:      2123456789214537896346185972:      3123456789214537896346195278:      4123456789214537896346198572:      4123456789214537896346298157:      2123456789214537896346298571:      2123456789214567893345198276:      2`

Sample by Band value, Index 3, 2 entries: Show
Code: Select all
`123456789214537896346298571:      2123456789214567893345198276:      2`
Last edited by Mathimagics on Tue Dec 17, 2019 3:43 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Latin Square - Canonicalisation

Serg,

I am examining your proposals for the canonicalisation problem. This is taking some time!

Your observations regarding the 2-row/2-column permutation cycle structures are certainly true, but whether using these methods can significantly reduce the time is still uncertain (at least, to me!). The jury is still out on this.

Cheers
MM

Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Thanks thats clear !

serg wrote:Index = 0 if pair of rows contains U4+U4+U4+U6 UA sets (4 distinct UA sets).
Index = 1 if pair of rows contains U4+U4+U10 UA sets (3 distinct UA sets).
Index = 2 if pair of rows contains U4+U6+U8 UA sets (3 distinct UA sets).
Index = 3 if pair of rows contains U4+U14 UA sets (2 distinct UA sets).

as these are 2 row UAs, the min lex order preserves these, so maybe these are the only options [?]
Code: Select all
`123456789                   123456789                    123456789                   123456789                214365897     Index = 0,0   214365897     Index = 0,1    214365897     Index = 0,2   214365897     Index = 0,334                          34                           34                          34                        43                          43                           45                          45                        56                          56                           53                          56                        65                          67                           67                          67                        78                          78                           78                          78                        89                          89                           89                          89                        97                          95                           96                          93                        123456789                   123456789                    123456789                   214367895     Index = 1,1   214367895     Index = 1,2    214367895     Index = 1,3   34                          34                           34                          43                          45                           45                          56                          53                           56                          67                          67                           67                          78                          78                           78                          89                          89                           89                          95                          96                           93                          123456789                   123456789                214537896     Index = 2,2   214537896     Index = 2,334                          34                       45                          45                       53                          56                       67                          67                       78                          78                       89                          89                       96                          93                       123456789214567893     Index = 3,334455667788993  `

Edit but ......of course there will be a few index 4,5,6 in c1/c2
Last edited by coloin on Sat Jan 18, 2020 9:16 am, edited 2 times in total.
coloin

Posts: 1951
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

serg wrote:Remark. The last LS in minlex form ("Solitary" Mathimagics' LS grid) has minimal Index value of 6. LS having minimal index of 7 (no two-row/two-column UA sets) are impossible.

hmmm
this is our grid with the 20C ... is it not index 7 ?
Code: Select all
`123456789234567891345678912456789123567891234678912345789123456891234567912345678`

Code: Select all
`123456789234567891     Index = 7`
coloin

Posts: 1951
Joined: 05 May 2005

PreviousNext