## Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: Band Distribution (final)

I don't understand, are your questions serious or joky (or rhetoric), but anyway I consider them seriously.
dobrichev wrote:
Serg wrote:So, you can see that rows pair with MI = 7 (no two-row UA) is the most probable event!

Is this phenomenon similar to this observation for sudoku grids in Minlex Form: Min and Max Lists / Chaining?

Yes, variant of two-row configuration for Sudoku solution grid when that configuration doesn't contain any UA sets is the most probable too (as for 9 x 9 Latin Squares). Michael Deverin's article contain data necessary for calculation of probability. This case (no UA sets in two-row combination) takes place for Ranks: 3, 9, 11, 12 - totally for 144+432+1296+1296 = 3168 (variants of the 2-nd row). Probability to observe such case is 3168/12096 = 26.2 %. The next nearest (frequent) case is U4+U14 case - probability to observe it is 21.4 %.
dobrichev wrote:
Michael A. Deverin wrote:In just over 70% of the cases, the lowest ranking pair was of rank = 4. This is especially fortuitous, since there is only one way to convert the row pair to minlex form.

It is possible to estimate probability to get the lowest ranking pair of rank = 4 for random Sudoku solution grid.
Code: Select all
`Rank   Frequency   Probability to observe (approx.)1        72        0.005952       216        0.017863       144        0.011904      1296        0.10714   ...In total 12096 r2 row form when r1 = 123456789`

Probability not to get Rank1 in one two-row (two-column) pair is 1 - 0.00595 = 0.99405 . Probability not to get Rank1 in 18 two-row/column pairs is 0.8981. Probability not to get Rank2 in 18 two-row/column pairs is 0.7230. Probability not to get Rank3 in 18 two-row/column pairs is 0.8062. Probability to get Rank4 at least once in 18 two-row/column pairs is 0.8700. Multiplication of all these probabilities gives 0.455 or 45.5 %. This is substaintially less, than 70%. Probability of 70% is observed during random Sudoku solution grids simulation. It seems different row/column pairs in Sudoku solution grids may not considered as independent (especially rows/columns in the same band/stack). So, this model doesn't work well for Sudoku, but works rather good for 9 x 9 LS.

Serg
Last edited by Serg on Mon Nov 09, 2020 9:18 am, edited 1 time in total.
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:A quick review of the methodology:

• LSMIN function returns minlex canonical form for a complete grid.
• LRMIN function returns "relative minlex form" for a partial (Latin Rectangle) grid, given the first NR rows. Paratopic transformations are not considered.

For each MI value (0 to 6), we can use LRMIN to generate a list of "candidate bands". We fix R1 and R2 for the MI index value, and for each possible R3 setting we add the resulting band B = R1+R2+R3 to the list of candidates if, and only if, LRMIN(B) = B.

Did you checked MI of pairs R1+R3 and R2+R3 for candidate band before adding the band to candidate list? I mean condition MI(R1+R3) >= MI(R1+R2) AND MI(R2+R3) >= MI(R1+R2).

I don't understand why candidate band with MI = 0 can be rejected. (List of "Known bands" is shorter, than list "Candidate bands" for MI = 0.) Maybe I am wrong, but it seems to me, every correct Latin Rectangle can be extended to some Latin Square.

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Serg wrote:Did you check MI of pairs R1+R3 and R2+R3 for candidate band before adding the band to candidate list? I mean condition MI(R1+R3) >= MI(R1+R2) AND MI(R2+R3) >= MI(R1+R2).

Yes, this test is applied whenever a row is added.
Serg wrote:I don't understand why candidate band with MI = 0 can be rejected. (List of "Known bands" is shorter, than list "Candidate bands" for MI = 0.) Maybe I am wrong, but it seems to me, every correct Latin Rectangle can be extended to some Latin Square.

A candidate band B is rejected if there are NO grid completions, G(B), for which LSMIN(G) = G. Conversely, a "valid band" is one that occurs as the first 3 rows of some minlex Latin Square.

Candidate bands for MI = 0 are less likely to be rejected than for other MI values, but still there are 37 cases where this happens. Here is a list of these candidates:

Failed candidate bands with MI=0: Show
Code: Select all
`123456789214365897352789146123456789214365897352789164123456789214365897352789416123456789214365897352789461123456789214365897352789614123456789214365897352789641123456789214365897352798146123456789214365897352798164123456789214365897352798416123456789214365897352798461123456789214365897352798614123456789214365897352798641123456789214365897356789124123456789214365897356789142123456789214365897356789214123456789214365897356789241123456789214365897356789412123456789214365897356789421123456789214365897356798142123456789214365897356798214123456789214365897356798421123456789214365897375819246123456789214365897375819264123456789214365897375819462123456789214365897375819624123456789214365897375829146123456789214365897375829164123456789214365897375829416123456789214365897375829461123456789214365897375829614123456789214365897375829641123456789214365897375892146123456789214365897375892461123456789214365897375892614123456789214365897375918264123456789214365897375918426123456789214365897375918642`

These all satisfy LRMIN(3, B) = B. But I think that you will find that NO minlex grid can start with these bands. In some cases, complete grids can be obtained which satisfy LRMIN(NR, G) = G (where G is the first NR rows), for NR = 4 to 9, but in every such case the final grid is not itself in minlex form, some paratopic transformation gives a lesser minlex grid.

In most cases, however, no grid completions are actually tested, because all partial grid tests return LRMIN(NR, G) < G somewhere between NR = 4 and 8.

Cheers
MM Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Re: Band Distribution (final)

Serg wrote:I cannot say even that I was not aware of his ideas...

We know how good is after a very dynamic day to get a long deep sleep, and how on the next morning the whole world looks simple, ordered and beautiful.
dobrichev
2016 Supporter

Posts: 1795
Joined: 24 May 2010

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:Candidate bands for MI = 0 are less likely to be rejected than for other MI values, but still there are 37 cases where this happens.

If I am not mistaken, candidate bands for MI = 0 can never be rejected because of other MI values, since MI = 0 is minimal possible value of MI. Isn't it? So, candidate band for MI = 0 can be rejected only if this band cannot be extended to full Latin Square. But Wiki says Hall's marriage theorem: "The marriage theorem is used in the usual proofs of the fact that an (r × n) Latin rectangle can always be extended to an ((r+1) × n) Latin rectangle when r < n, and so, ultimately to a Latin square." So, any valid band forever can be extended to some LS. Contradiction! I am thinking about counterexample - to find a way of extending some of your 37 cases to full LS.

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
The first band from your "37 cases" list:
Code: Select all
`123456789214365897352789146......................................................`

is expandable to LS (hope, I am not wrong):
Code: Select all
`123456789214365897352789146431278965546891273675912438789123654897634512968547321`

Do you consider it non-expandable?

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

### Band Distribution

Hi Serg,

Serg wrote:If I am not mistaken, candidate bands for MI = 0 can never be rejected because of other MI values, since MI = 0 is minimal possible value of MI. Isn't it? So, candidate band for MI = 0 can be rejected only if this band cannot be extended to full Latin Square.

It is certainly true that every candidate band with MI = 0 can be extended to a complete Latin Square with MI = 0.

But that is not enough for what we are doing. We want to identify which bands actually do occur as the first 3 rows in some minlex canonical form (CF) Latin Squares.

(Consider Sudoku grids. There are 416 "candidate bands" but 15 of these are empty - there are no ED (minlex CF) grids for those bands).

Your example, for a LS with R3 = 352789146, is not in Canonical Form. The CF has different form, still MI = 0, but different R3, and this corresponds to one of the 67 "known bands" for MI = 0:

Code: Select all
`123456789214365897341578926  * known band (#3 of 67) for MI = 0438197265567932418695784132786219543879621354952843671`

Cheers,
MM Mathimagics
2017 Supporter

Posts: 1615
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
At last I understood your method, please excuse me for my multiple questions on this theme.
All is OK. If you get at least one completion to full LS for band with MI = 0, then there exist ED LS with this first band. Otherwise (no completions to full LS), we can be sure that any LS with given first band has not minimal minlex form, so given band cannot be found among 19 billions of ED LS.

Thanks for clarification!

Serg
Serg
2018 Supporter

Posts: 727
Joined: 01 June 2010
Location: Russia

Previous