Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Band Distribution (final)

Postby Serg » Thu Jan 16, 2020 12:56 am

Hi, Mladen!
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 Derevin'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.00595
2       216        0.01786
3       144        0.01190
4      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
Serg
2018 Supporter
 
Posts: 682
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby Serg » Thu Jan 16, 2020 9:43 am

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

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Thu Jan 16, 2020 12:20 pm

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
123456789214365897352789146
123456789214365897352789164
123456789214365897352789416
123456789214365897352789461
123456789214365897352789614
123456789214365897352789641
123456789214365897352798146
123456789214365897352798164
123456789214365897352798416
123456789214365897352798461
123456789214365897352798614
123456789214365897352798641
123456789214365897356789124
123456789214365897356789142
123456789214365897356789214
123456789214365897356789241
123456789214365897356789412
123456789214365897356789421
123456789214365897356798142
123456789214365897356798214
123456789214365897356798421
123456789214365897375819246
123456789214365897375819264
123456789214365897375819462
123456789214365897375819624
123456789214365897375829146
123456789214365897375829164
123456789214365897375829416
123456789214365897375829461
123456789214365897375829614
123456789214365897375829641
123456789214365897375892146
123456789214365897375892461
123456789214365897375892614
123456789214365897375918264
123456789214365897375918426
123456789214365897375918642

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

Re: Band Distribution (final)

Postby dobrichev » Thu Jan 16, 2020 7:25 pm

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: 1777
Joined: 24 May 2010

Re: Latin Squares and Latin Square puzzles

Postby Serg » Thu Jan 16, 2020 9:25 pm

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

Re: Latin Squares and Latin Square puzzles

Postby Serg » Fri Jan 17, 2020 12:46 am

Hi, Mathimagics!
The first band from your "37 cases" list:
Code: Select all
123456789
214365897
352789146
.........
.........
.........
.........
.........
.........

is expandable to LS (hope, I am not wrong):
Code: Select all
123456789
214365897
352789146
431278965
546891273
675912438
789123654
897634512
968547321

Do you consider it non-expandable?

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

Band Distribution

Postby Mathimagics » Fri Jan 17, 2020 7:05 am

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
123456789
214365897
341578926  * known band (#3 of 67) for MI = 0
438197265
567932418
695784132
786219543
879621354
952843671


Cheers,
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby Serg » Fri Jan 17, 2020 4:03 pm

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

Previous

Return to Sudoku variants