Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Latin Squares and Latin Square puzzles

Postby blue » Sat Nov 30, 2019 11:57 pm

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
123456789
234167895

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

Postby Mathimagics » Sun Dec 01, 2019 3:41 am

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

Serg's Conjectures

Postby Mathimagics » Sun Dec 01, 2019 4:31 am

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
123456789456789231789231564234867195518943627697512843372695418861374952945128376
123456789456789231789231564234895617518627943697143852375918426862374195941562378
123456789456789231789312456245673918671928345938145672367891524514267893892534167
123456789456789231789312456245973618638145972971628345397861524514297863862534197
123456789456789231789312456247168593691573824835924167368247915572691348914835672
123456789456789231789312456247591368691834572835267914368925147572148693914673825
123456789456789231789312456247693518538147692691528347375861924862934175914275863
123456789456789231789312456247693815691825347835147692368571924572934168914268573
123456789456789231789312456247963518538147962961528347395671824672834195814295673
123456789456789231789312456248673915671925348935148672367591824592834167814267593
123456789456789231789312456274195863538627194961843527395274618617538942842961375
123456789456789231789312456274861395538294617961537842395628174617943528842175963
123456789456789231789312456274963518538174962961528374395841627617295843842637195
123456789456789231789312456275943618638175942941628375394861527517294863862537194
123456789456789231798213645235894176841627953967135428384962517579341862612578394
123456789456789231798213645239574816584162973617938524342895167875641392961327458
123456789456789231798213645249537168367841592581962473672395814835174926914628357
123456789456789231798213645249637158617845923835921476374168592562394817981572364
123456789456789231798213645249671853675938412831524976362845197587192364914367528
123456789456789231798213645271364958364895127985172364512647893647938512839521476
123456789457289163689173452234968517516734928978512634365897241741325896892641375
123456789457289163689173452235741896816392574974568231392817645568924317741635928
123456789457289163689173452235964817816735924974812635392641578568397241741528396
123456789457289163689173452241867395736594821895312674318725946564938217972641538
123456789457289163689173452245968317316745928978312645564897231731524896892631574
123456789457289163689713254235671948874395621961842537346127895518964372792538416
123456789457289163689713254235897641816524397974361825368145972591672438742938516
123456789457289163689713254235967841716348925894521376362895417578134692941672538
123456789457289163689713254236597841815324697974861325368145972591672438742938516
123456789457289163689713254236891475578324691941675832365147928712938546894562317
123456789457289163689713254246971538378625941591834627762148395815392476934567812
123456789457289163689713254271964538836572491945138672394625817512897346768341925
123456789457289163689713254276835941531924678948167325364571892792348516815692437
123456789457289163689713254278341695316925478945867312564192837792638541831574926
123456789457289163698137425245871396376924518981563274514692837762348951839715642
123456789457289163698137425246893571315764892879521634534978216761342958982615347
123456789457289163698137425261793854874521396935648271319862547586374912742915638
123456789457289163698137425271394856364528971985671234516842397742963518839715642
123456789457289163698137524235718946861924375974563812349872651586341297712695438
123456789457289163698137524245918637871563492936742851384621975569374218712895346
123456789457289163698137524279361845564728931831594672316845297782913456945672318
123456789457289163698317254241938576835764921976125438364592817519873642782641395
123456789457289163698317254284691375539872416716534892365748921841925637972163548
123456789457289163698317524279631458346875291815924376561748932782193645934562817
123456789457289163698713254245637891761948532839521476372864915586192347914375628
123456789457289163698713254245671938739845621861392475314567892586924317972138546
123456789457289163698713254246537891781964325935128647379842516562391478814675932
123456789457289163698713254246971835581342976739568421362894517874135692915627348
123456789457289163869713245278591634645372918931864527386925471514637892792148356
123456789457289163896317245281643597345978621679125834564831972738592416912764358
123456789457289613689173245245861397736945128891732564314697852568324971972518436
123456789457289613689173245264891357578632491931745862345967128716528934892314576
123456789457289613689713245295341867731862594846975132368524971514697328972138456
123456789457289631869713245236594817578162394914378526345927168691835472782641953
123456789457289631896317245249635817368172594715948326531864972682791453974523168
123456789457289631968731245241573896639812457785964123374625918596148372812397564


Brendan McKay's list of 9x9 Latin Squares with no UA4's can be found here
User avatar
Mathimagics
2017 Supporter
 
Posts: 1500
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby blue » Sun Dec 01, 2019 6:45 am

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

Postby Mathimagics » Sun Dec 01, 2019 7:37 am

Thanks blue!

I fixed the LSCF code, and now find all 14 puzzles producing the same result, which matches yours, fortunately! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1500
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Mon Dec 02, 2019 4:33 am

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

Conjugation Tests

Postby Mathimagics » Wed Dec 04, 2019 11:34 am

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) Sudoku

145278936418725693971453268283146579634819725867591342326984157759362814592637481 # (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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1500
Joined: 27 May 2015
Location: Canberra

Re: LS conjugation transformations

Postby tarek » Wed Dec 04, 2019 1:10 pm

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 .... :lol: )

tarek
User avatar
tarek
 
Posts: 3553
Joined: 05 January 2006

Re: LS conjugation transformations

Postby Mathimagics » Wed Dec 04, 2019 2:12 pm

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

Re: LS conjugation transformations

Postby tarek » Wed Dec 04, 2019 2:26 pm

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 ... :lol:

:lol:

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
User avatar
tarek
 
Posts: 3553
Joined: 05 January 2006

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Dec 04, 2019 3:33 pm

Ok, that does sound nicer! :cool:

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

Re: Latin Squares and Latin Square puzzles

Postby tarek » Wed Dec 04, 2019 8:36 pm

Ah yes 3x2X1 = 6 ways to permute r, c, and d
User avatar
tarek
 
Posts: 3553
Joined: 05 January 2006

Re: Latin Squares and Latin Square puzzles

Postby coloin » Sun Dec 08, 2019 7:45 pm

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 4
4 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
123456789
21....... 
.........   these have a U4 and must be  the first grids in the min lex - and this is 80 % of all grids

123456789
231......
.........   these dont have a U4

123456789
234......
.........   these dont have a U4

123456789
312......
.........   these dont have a U4 but have that U6 to start with

123456789
345......
.........   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
123456789
456......   these are sudoku grids with initial band 1-31 and have a repeating minirow in each row in the band

123456789
4571.....    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 ] :roll:
coloin
 
Posts: 1879
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Mon Dec 09, 2019 5:56 am

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

Re: Latin Squares and Latin Square puzzles

Postby Serg » Mon Dec 09, 2019 8:31 pm

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
Serg
2018 Supporter
 
Posts: 701
Joined: 01 June 2010
Location: Russia

PreviousNext

Return to Sudoku variants