The New Sudoku Players' Forum

by **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

by **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

by **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

by **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.]

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

by **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]

by **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

by **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

by **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

by **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

by **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]

by **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

by **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

by **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

by **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

The New Sudoku Players' Forum

Latin Squares and Latin Square puzzles

ED Latin Square #1

Re: ED Latin Square #1

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Latin Squares - Band Distribution

Latin Square - Canonicalisation

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles