## Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: Latin Squares and Latin Square puzzles

Hi Serg,

Serg wrote:I am still thinking about efficient LS canonicalization algorithm.
It's not important - has a LS grid UA4/UA6 or no. But we should know smallest size of its two-row UA set.
Let, for example, the smallest size of LS grid's two-row UA set is 8 (UA8). In this case we can be sure that r1 and r2 LS rows will have such view:
Code: Select all
`123456789234167895`

I have no proof of this statement right now though. But it's very likely.
If it's true, the columns order is fixed, and we get rid of 9! column permutations.

In this case, you can cycle the columns in the UA8 and (independently) in the UA10 (and relabel).
That gives 4*5 = 20 column permutations, to check.

The worst case is 2 rows with 3 UA6's -- 6*3*3*3 = 162 column permutations, to check.
The factor of 6, comes from 6 ways to order the UA6's.

The 2nd worst case is two rows with 3 UA4's and a UA6 -- 6*2*2*2*3 = 144 column permutations, to check.

The worst case happens (many times) in the MC grid.
Each pair of rows has 3 UA6's, and as you say, the rows can be taken in either order.
The total number of checks is 6*72*162 = 69984, where the factor of 6 comes from "6 conjugates".
[ It turns out that the MC grid has 69984/3 = 23328 automorphisms. ]

Cheers,
Blue.
blue

Posts: 894
Joined: 11 March 2013

### Re: Latin Squares and Latin Square puzzles

Hi blue,
blue wrote:Those aren't ED, using latin square transformations. You can check by hand, that there are row and column permutatons that bring them to the form with triangular fills in two opposite corners, and the same number appearing in each diagonal. Your LCF function should be transforming each (solution,puzzle) pair, to:

Code: Select all
`123456789231564897312645978456789231564897312645978123789231564897312645978123456...........1..4..73..6..9..........1..4..7.126..9..........1..489.3..6..9........`

There might be some confusion in my use of the term "ED puzzles". If the puzzles were minlex-ed independently then I suppose they would all give the same result, the one that you list above.

But I don't do that. For various reasons (discussed elsewhere?), I always synchronize the transformations on the grid with transformations on the puzzle, so that I always get a "CF puzzle" that matches the CF grid.
Last edited by Mathimagics on Sun Dec 01, 2019 4:35 am, edited 2 times in total.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Serg's Conjectures

Summary of results:

• there is one ED Latin Square that has no UA4 or UA6 (with {2r3c} or {3r2c} pattern)
• there are 352,894 ED Sudoku grids with no UA4
• there are 56 ED Sudoku grids with no UA4 or UA6 (with {2r3c} or {3r2c} pattern)

The one ED latin square is:
Code: Select all
`123456789456789231789231564234867195518943627697512843372695418861374952945128376`

The 56 Sudoku grids are:
Hidden Text: Show
Code: Select all
`123456789456789231789231564234867195518943627697512843372695418861374952945128376123456789456789231789231564234895617518627943697143852375918426862374195941562378123456789456789231789312456245673918671928345938145672367891524514267893892534167123456789456789231789312456245973618638145972971628345397861524514297863862534197123456789456789231789312456247168593691573824835924167368247915572691348914835672123456789456789231789312456247591368691834572835267914368925147572148693914673825123456789456789231789312456247693518538147692691528347375861924862934175914275863123456789456789231789312456247693815691825347835147692368571924572934168914268573123456789456789231789312456247963518538147962961528347395671824672834195814295673123456789456789231789312456248673915671925348935148672367591824592834167814267593123456789456789231789312456274195863538627194961843527395274618617538942842961375123456789456789231789312456274861395538294617961537842395628174617943528842175963123456789456789231789312456274963518538174962961528374395841627617295843842637195123456789456789231789312456275943618638175942941628375394861527517294863862537194123456789456789231798213645235894176841627953967135428384962517579341862612578394123456789456789231798213645239574816584162973617938524342895167875641392961327458123456789456789231798213645249537168367841592581962473672395814835174926914628357123456789456789231798213645249637158617845923835921476374168592562394817981572364123456789456789231798213645249671853675938412831524976362845197587192364914367528123456789456789231798213645271364958364895127985172364512647893647938512839521476123456789457289163689173452234968517516734928978512634365897241741325896892641375123456789457289163689173452235741896816392574974568231392817645568924317741635928123456789457289163689173452235964817816735924974812635392641578568397241741528396123456789457289163689173452241867395736594821895312674318725946564938217972641538123456789457289163689173452245968317316745928978312645564897231731524896892631574123456789457289163689713254235671948874395621961842537346127895518964372792538416123456789457289163689713254235897641816524397974361825368145972591672438742938516123456789457289163689713254235967841716348925894521376362895417578134692941672538123456789457289163689713254236597841815324697974861325368145972591672438742938516123456789457289163689713254236891475578324691941675832365147928712938546894562317123456789457289163689713254246971538378625941591834627762148395815392476934567812123456789457289163689713254271964538836572491945138672394625817512897346768341925123456789457289163689713254276835941531924678948167325364571892792348516815692437123456789457289163689713254278341695316925478945867312564192837792638541831574926123456789457289163698137425245871396376924518981563274514692837762348951839715642123456789457289163698137425246893571315764892879521634534978216761342958982615347123456789457289163698137425261793854874521396935648271319862547586374912742915638123456789457289163698137425271394856364528971985671234516842397742963518839715642123456789457289163698137524235718946861924375974563812349872651586341297712695438123456789457289163698137524245918637871563492936742851384621975569374218712895346123456789457289163698137524279361845564728931831594672316845297782913456945672318123456789457289163698317254241938576835764921976125438364592817519873642782641395123456789457289163698317254284691375539872416716534892365748921841925637972163548123456789457289163698317524279631458346875291815924376561748932782193645934562817123456789457289163698713254245637891761948532839521476372864915586192347914375628123456789457289163698713254245671938739845621861392475314567892586924317972138546123456789457289163698713254246537891781964325935128647379842516562391478814675932123456789457289163698713254246971835581342976739568421362894517874135692915627348123456789457289163869713245278591634645372918931864527386925471514637892792148356123456789457289163896317245281643597345978621679125834564831972738592416912764358123456789457289613689173245245861397736945128891732564314697852568324971972518436123456789457289613689173245264891357578632491931745862345967128716528934892314576123456789457289613689713245295341867731862594846975132368524971514697328972138456123456789457289631869713245236594817578162394914378526345927168691835472782641953123456789457289631896317245249635817368172594715948326531864972682791453974523168123456789457289631968731245241573896639812457785964123374625918596148372812397564`

Brendan McKay's list of 9x9 Latin Squares with no UA4's can be found here

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Mathimagics wrote:For various reasons (discussed elsewhere?), I always synchronize the transformations on the grid with transformations on the puzzle, so that I always get a "CF puzzle" that matches the CF grid.

I did that too, and the result that I gave, does match the CF grid.

It looks like you aren't dealing with the possiblity that the solution grid has non-trivial automorphisms, and there are several transformations that put in in canonical form.
When that's the case, you should try each such transformation on the puzzle, and keep the result that is "minlex smallest".
blue

Posts: 894
Joined: 11 March 2013

### Re: Latin Squares and Latin Square puzzles

Thanks blue!

I fixed the LSCF code, and now find all 14 puzzles producing the same result, which matches yours, fortunately!

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Hi Serg,
Serg wrote:I am very impressed again by your speed!

Thank you, but there is nothing particularly clever here!

When looking for Sudoku grids with no UA4, we need only to check ~20% of the grids.

Most bands in the ED catalog have this pattern in rows 1 and 2:
Code: Select all
`1 2 3 44 5 7 1`

So there is a UA4 in {r12c14} for every grid in these bands (band indices 32 to 346). These bands represent ~4.4 billion grids, so we only needed to check the other ~1 billion grids.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Conjugation Tests

Some results of tests performed with the conjugation transformations:

• 25% of ED Sudoku grids have at least one valid conjugate. That is, if we transform the grid so that (r, c, d) becomes (r, d, c) or (c, d, r), the resulting grid is isotopic to a valid Sudoku grid for 1,389,356,635 grids (25.39% of ED grids). "Isotopic" just means that some re-ordering of the rows and/or columns might be needed.

There are 166,053,528 "bi-conjugate" grids (3% of ED grids), where both conjugates are valid.

This bi-conjugate example shows a Sudoku grid, its two conjugate grids, and the permutations that transform the conjugates into valid Sudoku grids. The result is 3 x ED grids that are mutually LS-isomorphic - they all belong to the same Latin Square main class:

Code: Select all
`123456789457189263896327145214538697365794821978612354542873916639241578781965432 # (r, c, d) Sudoku145278936418725693971453268283146579634819725867591342326984157759362814592637481 # (c, d, r) 176489523423156879958732146249865317615397482387241695892613754764528931531974268 # r{123457689} c{159267348}123456789479128356754893612215347968981632475567984231836219547642571893398765124 # (r, d, c)126345789478912356395876124753489612982163475641257893217534968564798231839621547 # r{129358467} c{126345789}`

• for Sudoku grids with valid Sudoku conjugate(s), "conjugate puzzles" are only valid Sudoku puzzles when the original puzzle is a valid LS puzzle. Conjugation is only a universal VPT for Latin Squares, not for Sudoku.

• any of our "bi-minimal" puzzles (puzzles which are valid and minimal for both Sudoku and LS), will produce valid conjugate Sudoku puzzles, when the conjugates are valid Sudoku isotopes. The conjugate puzzles will be minimal for LS, but for Sudoku, even if the conjugates are valid, they will not necessarily be minimal.

Here is one of blue's bi-minimal examples (22 clues), and its conjugates (both are valid):
Code: Select all
`..3......45.......79....465.........56......4..932.....4.........2913.....12..3...23.5.....7..2..539..8..1.6...9..6.88..6......5..3..........8...3....9.........3. # (c, d, r)....3.........12....2..7981..............912...354.........2...5.436....3..47.... # (r, d, c) not minimal`

All three are minimal LS puzzles, and valid Sudoku puzzles, but only the first two are minimal Sudoku.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: LS conjugation transformations

conjugation transformations: This is very interesting. The absence of box constraints allows for line permutation as if they were digits.

In your canonicalization algorith for LS is it worth therfore Re-labelling the 3 r, c and transformation as 1-9 as you would do normally just for d and choosing the minlex version to speed up your canonicalization?

I haven't visualized what I'm saying so it might end up being (sounds nice on paper, but the reality is .... )

tarek

tarek

Posts: 3553
Joined: 05 January 2006

### Re: LS conjugation transformations

tarek wrote:I haven't visualized what I'm saying so it might end up being (sounds nice on paper, but the reality is .... )

Actually, I'm not even convinced that it sounds nice on paper ...

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: LS conjugation transformations

Mathimagics wrote:
tarek wrote:I haven't visualized what I'm saying so it might end up being (sounds nice on paper, but the reality is .... )

Actually, I'm not even convinced that it sounds nice on paper ...

Joking aside. The idea was that with each transformation, you would relabel the digits 1-9 and you would choose the the min-lex out of the 3. In theory you are adding 2 lines to the same loop rather than adding 2 extra loops to your algorithm

tarek

tarek

Posts: 3553
Joined: 05 January 2006

### Re: Latin Squares and Latin Square puzzles

Ok, that does sound nicer!

But it's more or less what I do (or should I say, what I will do). The outer loop is over the 9! column permutations. For each permutation there are 54 different RF's (reduced forms), 9 ways to choose the RF base row, times 6 (not 3) for the conjugates. So I do effectively "choose the least minlex RF" from among the 6 candidates, but this choice has to be made for every combination of (column permutation, RF base row index).

The devil is in the detail - there are ways to ensure that candidate RF's that can't possibly be THE minlex target are detected as soon as possible. Similar logic can be applied to selecting the least minlex of the 6 conjugate RF's.

It's a work in progress ... the final result will almost certainly be faster than my first draft, which, just to get a quick result, crudely did each of the 6 conjugates as an outer loop ...

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Ah yes 3x2X1 = 6 ways to permute r, c, and d

tarek

Posts: 3553
Joined: 05 January 2006

### Re: Latin Squares and Latin Square puzzles

Mathimagics wrote:Hi Serg,
Serg wrote:I am very impressed again by your speed!

Thank you, but there is nothing particularly clever here!

When looking for Sudoku grids with no UA4, we need only to check ~20% of the grids.

Most bands in the ED catalog have this pattern in rows 1 and 2:
Code: Select all
`1 2 3 44 5 7 1`

So there is a UA4 in {r12c14} for every grid in these bands (band indices 32 to 346). These bands represent ~4.4 billion grids, so we only needed to check the other ~1 billion grids.

Just wondering what the classification of our 3-row bands looks like ... [ in min lex grid terms]...

pure Latin square grids
Code: Select all
`12345678921.......  .........   these have a U4 and must be  the first grids in the min lex - and this is 80 % of all grids123456789231...... .........   these dont have a U4 123456789234...............   these dont have a U4123456789312...............   these dont have a U4 but have that U6 to start with123456789345...............   not sure if this can be the first few rows in a min lex LS grid `

Sudoku grids /Latin Square grids - presumably there can be reduced to a great extent with column swaps
Code: Select all
`123456789456......   these are sudoku grids with initial band 1-31 and have a repeating minirow in each row in the band1234567894571.....    these are sudoku grids with initial band 32-346   and have a U4`

Hmmm i didn't realise that all sudoku grids with first band 347-416 didnt have a U4 ! [352,894 ED Sudoku grids with no UA4 ]
coloin

Posts: 1879
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

coloin wrote:Hmmm i didn't realise that all sudoku grids with first band 347-416 didnt have a U4

Almost, but not quite true!

Band indices 32 - 346 have a UA4 in the first 3 rows, so we don't need to search these for no-UA4 grids.

Band indices 347 - 416 don't have a UA4 in the top 3 rows, so we need to test each grid individually. There are 60,442 grids in this range, and most of them (53,286 grids) have no UA4, but not all.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

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
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

PreviousNext