Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

ED Latin Square #1

Postby Mathimagics » Tue Dec 10, 2019 6:52 am

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
123456789
214365897
341278956
432189675
567891234
658917342
789523461
896742513
975634128


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
123456789
234167895
345678912
416839527
579324168
658792341
782913456
891245673
967581234
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: ED Latin Square #1

Postby Serg » Tue Dec 10, 2019 10:45 pm

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
123456789
214365897
341278956
432189675
567891234
658917342
789523461
896742513
975634128
What is your method of finding this LS grid with lowest minlex metric?

Serg
Serg
2018 Supporter
 
Posts: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Dec 11, 2019 5:24 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby Serg » Wed Dec 11, 2019 11:25 pm

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
123456789
214365897     Index = 0

123456789
214367895     Index = 1

123456789
214537896     Index = 2

123456789
214567893     Index = 3

123456789
231564897     Index = 4

123456789
231567894     Index = 5

123456789
234167895     Index = 6

123456789
234567891     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: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby coloin » Thu Dec 12, 2019 7:57 pm

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
123456789
214......
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.)

123456789
23156....
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)

123456789
234167895
3........
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: 1858
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Thu Dec 12, 2019 8:02 pm

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: 1858
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Serg » Thu Dec 12, 2019 11:00 pm

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: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby Serg » Thu Dec 12, 2019 11:19 pm

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
123456789
214365897     Index = 0

123456789
214367895     Index = 1

123456789
214537896     Index = 2

123456789
214567893     Index = 3

Serg
Serg
2018 Supporter
 
Posts: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby coloin » Fri Dec 13, 2019 12:33 am

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: 1858
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Serg » Fri Dec 13, 2019 11:02 pm

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: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby coloin » Sat Dec 14, 2019 9:40 pm

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: 1858
Joined: 05 May 2005

Latin Squares - Band Distribution

Postby Mathimagics » Mon Dec 16, 2019 8:09 am

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:   5244
123456789214365897341527968:  40654
123456789214365897341578926:  57757
123456789214365897341579268:  43082
123456789214365897341789256:   4924
123456789214365897341789265:  15384
123456789214365897341789526:  13029
123456789214365897342178956:   4336
123456789214365897342517968:  20969
123456789214365897342578916:  29777
123456789214365897342579168:  26827
123456789214365897342789156:   6117
123456789214365897342789165:   8651
123456789214365897342789516:   7182
123456789214365897345612978:    696
123456789214365897345617928:  10680
123456789214365897345678912:   8237
123456789214365897345718926:  17092
123456789214365897345718962:   6175
123456789214365897345719268:   6419
123456789214365897345728916:  10737
123456789214365897345728961:   3984
123456789214365897345729168:   4157
123456789214365897345789126:   5077
123456789214365897345789162:   5110
123456789214365897345789216:   3830
123456789214365897345798126:   3978
123456789214365897345798162:   2661
123456789214365897345798216:   3231
123456789214365897351624978:     16
123456789214365897351627948:   1570
123456789214365897351642978:    333
123456789214365897351647928:   3449
123456789214365897351678924:   2386
123456789214365897351678942:   2089
123456789214365897351728946:    701
123456789214365897351728964:     41
123456789214365897351748926:   1615
123456789214365897351748962:    604
123456789214365897351749268:    604
123456789214365897351782946:   1076
123456789214365897351782964:    457
123456789214365897351784926:    821
123456789214365897351784962:    351
123456789214365897351789246:    266
123456789214365897351789264:    248
123456789214365897351789462:    189
123456789214365897351789624:    193
123456789214365897351789642:    179
123456789214365897351792468:    128
123456789214365897351794268:    168
123456789214365897351798246:    123
123456789214365897351798264:    134
123456789214365897351798426:     91
123456789214365897351798624:    116
123456789214365897351798642:    120
123456789214365897352617948:    214
123456789214365897352678914:    195
123456789214365897352678941:    139
123456789214365897352718946:     56
123456789214365897352718964:     22
123456789214365897352748916:     54
123456789214365897352748961:     31
123456789214365897352749168:     20
123456789214365897352749618:      2

Sample by Band value, Index 1, 127 entries: Show
Code: Select all
123456789214367895341275968:    108
123456789214367895341278956:     90
123456789214367895341528976:   4918
123456789214367895341529678:   3987
123456789214367895341572968:   8132
123456789214367895341578926:   3515
123456789214367895341579268:   1709
123456789214367895341582967:   2460
123456789214367895341589267:   1532
123456789214367895341589276:   1535
123456789214367895341598276:   1117
123456789214367895342175968:    600
123456789214367895342178956:    248
123456789214367895342179568:    393
123456789214367895342189567:    119
123456789214367895342518967:   1738
123456789214367895342518976:   4761
123456789214367895342519678:   3555
123456789214367895342571968:   8287
123456789214367895342578916:   3762
123456789214367895342579168:   1770
123456789214367895342581967:   2608
123456789214367895342589167:   1624
123456789214367895342589176:   1758
123456789214367895342598176:   1368
123456789214367895345612978:   2977
123456789214367895345618927:   4028
123456789214367895345618972:   2280
123456789214367895345619278:   3254
123456789214367895345671928:   3903
123456789214367895345672918:   3358
123456789214367895345678912:   1418
123456789214367895345678921:   1207
123456789214367895345679128:   1179
123456789214367895345679218:   1213
123456789214367895345681927:   1631
123456789214367895345681972:    961
123456789214367895345682917:   1288
123456789214367895345682971:    818
123456789214367895345689127:    413
123456789214367895345689217:    399
123456789214367895345718926:    720
123456789214367895345719268:    765
123456789214367895345719628:    710
123456789214367895345728916:    676
123456789214367895345729168:    573
123456789214367895345729618:    536
123456789214367895345789162:    261
123456789214367895345789261:    225
123456789214367895345798162:    146
123456789214367895345798261:    121
123456789214367895351628974:    100
123456789214367895351629478:     87
123456789214367895351642978:    342
123456789214367895351648927:    187
123456789214367895351648972:    261
123456789214367895351649278:    382
123456789214367895351672948:    501
123456789214367895351674928:    156
123456789214367895351678924:    194
123456789214367895351678942:    206
123456789214367895351679248:    387
123456789214367895351679428:    329
123456789214367895351682947:     49
123456789214367895351682974:    250
123456789214367895351689247:    155
123456789214367895351689274:    190
123456789214367895351689427:    120
123456789214367895351689472:    127
123456789214367895351692478:    125
123456789214367895351694278:     11
123456789214367895351698274:    218
123456789214367895351698472:    154
123456789214367895351728946:     29
123456789214367895351729648:     16
123456789214367895351748926:     89
123456789214367895351749268:     72
123456789214367895351749628:     66
123456789214367895351782946:     98
123456789214367895351782964:     73
123456789214367895351784926:     71
123456789214367895351784962:     83
123456789214367895351789264:     46
123456789214367895351792648:     54
123456789214367895351794628:     59
123456789214367895351798264:      4
123456789214367895352614978:    118
123456789214367895352618947:    156
123456789214367895352618974:     97
123456789214367895352619478:    110
123456789214367895352671948:    203
123456789214367895352674918:     66
123456789214367895352678914:    139
123456789214367895352678941:     48
123456789214367895352679148:    139
123456789214367895352679418:     50
123456789214367895352681947:     68
123456789214367895352681974:     64
123456789214367895352684917:      7
123456789214367895352684971:     22
123456789214367895352689147:     42
123456789214367895352689417:     14
123456789214367895352714968:     27
123456789214367895352718946:     42
123456789214367895352719468:     44
123456789214367895352719648:     29
123456789214367895352748916:     80
123456789214367895352748961:     16
123456789214367895352749168:     31
123456789214367895352749618:     47
123456789214367895352789146:     37
123456789214367895352789164:     25
123456789214367895352789461:      4
123456789214367895352798146:     39
123456789214367895352798164:      1
123456789214367895352814967:     26
123456789214367895352814976:     34
123456789214367895352819467:     11
123456789214367895352819476:      5
123456789214367895352849617:     18
123456789214367895352871946:     12
123456789214367895352874961:     11
123456789214367895352879614:     14
123456789214367895352914678:     10
123456789214367895352948671:      3
123456789214367895352971468:      4
123456789214367895352981467:      8

Sample by Band value, Index 2, 51 entries: Show
Code: Select all
123456789214537896341672958:     20
123456789214537896341675928:     44
123456789214537896341678952:    101
123456789214537896341685972:     88
123456789214537896341692578:     40
123456789214537896341695278:     50
123456789214537896341698572:     42
123456789214537896342165978:     58
123456789214537896342168957:     12
123456789214537896342168975:     98
123456789214537896342169578:     49
123456789214537896342671958:    130
123456789214537896342675918:     71
123456789214537896342678915:     75
123456789214537896342678951:    148
123456789214537896342681975:     76
123456789214537896342685917:     50
123456789214537896342685971:    112
123456789214537896342691578:     98
123456789214537896342695178:     61
123456789214537896342698175:      5
123456789214537896342698571:     37
123456789214537896345162978:     63
123456789214537896345168927:     19
123456789214537896345168972:     38
123456789214537896345169278:      8
123456789214537896345261978:      6
123456789214537896345268971:     18
123456789214537896345269178:     12
123456789214537896345671928:     24
123456789214537896345672918:      8
123456789214537896345678912:     31
123456789214537896345678921:     14
123456789214537896345681927:     22
123456789214537896345681972:     22
123456789214537896345682917:      6
123456789214537896345682971:     16
123456789214537896345691278:      6
123456789214537896345692178:     10
123456789214537896345698172:      2
123456789214537896345698271:      4
123456789214537896346125978:      1
123456789214537896346175928:      6
123456789214537896346178952:      4
123456789214537896346179258:      2
123456789214537896346182975:      4
123456789214537896346185927:      2
123456789214537896346185972:      3
123456789214537896346195278:      4
123456789214537896346198572:      4
123456789214537896346298157:      2
123456789214537896346298571:      2
123456789214567893345198276:      2

Sample by Band value, Index 3, 2 entries: Show
Code: Select all
123456789214537896346298571:      2
123456789214567893345198276:      2
Last edited by Mathimagics on Tue Dec 17, 2019 3:43 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Latin Square - Canonicalisation

Postby Mathimagics » Mon Dec 16, 2019 9:11 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby coloin » Mon Dec 16, 2019 4:41 pm

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,3
34                          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,3
34                          34                       
45                          45                       
53                          56                       
67                          67                       
78                          78                       
89                          89                       
96                          93                       



123456789
214567893     Index = 3,3
34
45
56
67
78
89
93 


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: 1858
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Mon Dec 16, 2019 5:10 pm

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
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Code: Select all
123456789
234567891     Index = 7
coloin
 
Posts: 1858
Joined: 05 May 2005

PreviousNext

Return to Sudoku variants

cron