## Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:I really think that this number should be multiplied by 9. For each column permutation, there are 9 reduced forms that can be produced, one for each row - this then becomes row 1 of the reduced form, and fixes a re-labelling + row ordering that gives a reduced form. This gives 19,595,520 isomorphic transformations.

I think you are right. (I corrected my previous post.)

Serg
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Thanks, Serg! We have converged to a state of harmonious concordance ...

Some revision to that list of 20-clue LS puzzles on the "BC" grid. I did a vicinity search to {-3,+3} to try and find whether another grid might be revealed.

But no. I did find 200 or so candidates, but after processing with the revised CF function (which now checks conjugates, so is a true isomorphism checker), they reduced to just 14 ED puzzles, all on the same grid:

Code: Select all
`........9..1..4...3..6..9.8...........4..7.1.6..9....3.....1.....7.12.4.9.......6...4...8...1.......12..59..4..78..3....8.......5...1....9..15..8..3...4...........2.4..7....1.6..9..........45.7..2......9..1..4.........9.31.6.....1.....7....4..1.............4..731.6..9.............4..7..26..9..1..........4..7..2.459..1.....1....6.8............2.4.9........2....4.9.3.26....8...78...1.6.8............2.4..1..4.............7..2..5.784.............7..264.9..1.............7..2..59..1..4..1..4....9...........2..5.7.4.......1.....7.....5.78.2.........4..7..2...9..1..4.61..4..7.............2..5..84..7.............2..5..8.237.............2..597.1..4..1..4..7.9........7..2..5...4..7....1...........5..8.2.7.......4.....2.....8.23.5.1..45..8....5.......2...9....6..92..5..8...1............9.......97..26.....1...5.1.34...8.....6...73........4......3..6..97..2....7.............8..3...4..7..2...612...6.8.2............4.9.............4.9.3..6....8.2...9.3.5.48....2.........4..12.4..7......6..9..1.........6.89.3.....9.....4....1....9.3..6...........7.1..4..12.4..7..2.............5..84..7..2.............5..8..37..2.............5..8..3.56`

The CF function is expensive: it took ~3s per grid+puzzle.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
The final check to be sure that we calculated the number of "true" isomorphic transformations right.
Wiki says that there are 377,597,570,964,258,816 reduced 9 x 9 LS. Dividing it by the number of "main classes" - 19,270,853,541 (number of ED 9 x 9 LS) we'll get ~19,594,231 (approx.) necessary isomorphic transformations, that is very close to your number 19,595,520 of "true" isomorphic transformations (the small difference is caused by automorphic LS).

Serg
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:The CF function is expensive: it took ~3s per grid+puzzle.

Does finding minlex form for LS grid take 3 seconds? Canonicalization can be speed up by finding UA4 and two-row (two-column) UA6 unavoidable sets.

If a LS grid contains (at least one) UA4 unavoidable set, grid's cells r2c1 and r2c2 can be reduced to
Code: Select all
`12345678921.......`

So, only rows participated UA4 should be tested as r1 and r2 rows, and UA4 columns must be transformed to c1 and c2 columns. This limits possible permutations of columns, hence speeds up canonicalization.

If LS grid contains no UA4 unavoidable sets, but contains at least one two-row (two-column) UA6 unavoidable set, it can be morphed to
Code: Select all
`123456789231......`

So, only rows participated two-row UA6 should be tested as r1 and r2 rows, and UA6 columns must be transformed to c1, c2 and c3 columns.

What should we do if a LS grid has neither UA4, nor two-row (two-column) UA6 unavoidable sets?

Conjecture "L"
Any LS solution grid contains either UA4 or two-row (two-column) UA6 unavoidable set(s).

Conjecture "S"
Any Sudoku solution grid contains either UA4 or two-row (two-column) UA6 unavoidable set(s).

It can be proved, that isotopic and paratopic transformation don't destroy UA4 and two-row (two-column) UA6 unavoidable sets in LS solution grid. So, those UA sets can be found once and transformed according to applied isotopic/paratopic transformations.

Serg
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Hi Serg,

Thanks for those suggestions. Version 1 of LSCF (Latin Square Canonical Form function) is fairly simplistic, as the first thing I wanted was to be sure that it got the right answer! Next I will try out your suggestions for improvement and report back.

But one thing that we can check immediately is this:
Serg wrote:Conjecture "L"
Any LS solution grid contains either UA4 or two-row (two-column) UA6 unavoidable set(s).

Amazingly, this turns out to be not quite true!

We can check this quickly because Brendan McKay has identified all LS9's with no UA4 (ie no intercalates). There are 1707 ED grids in this list, and every one does have a UA6, except for this solitary case:

Code: Select all
`123456789234167895345678912416839527579324168658792341782913456891245673967581234`

Code: Select all
` +-------------------+ | 1 2 3 4 5 6 7 8 9 | | 2 3 4 1 6 7 8 9 5 | | 3 4 5 6 7 8 9 1 2 | | 4 1 6 8 3 9 5 2 7 | | 5 7 9 3 2 4 1 6 8 | | 6 5 8 7 9 2 3 4 1 | | 7 8 2 9 1 3 4 5 6 | | 8 9 1 2 4 5 6 7 3 | | 9 6 7 5 8 1 2 3 4 | +-------------------+`

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

I'm sure you all know this but you only need to add 4 3x3 box constraints to a 9x9 Latin Square to make it into a sudoku. These 4 squares will force the creation of the other 5. This is similar to what the 4 windows of Windoku (Hyper Sudoku, SudokuW) do. I'm not sure if this makes a difference to a SAT solver or not when you restrict the constraints in this way!

tarek

Posts: 3553
Joined: 05 January 2006

### Re: Latin Squares and Latin Square puzzles

Good point, Tarek.

It's hard to test since SAT already solves 9x9 Sudoku's very quickly ... perhaps for larger grids the difference might be more obvious?

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

@ tarek
Hmmm I knew that with 6 [B124679] fixed boxes and 5 [B13579] fixed boxes , the clues in the other boxes must be sudoku complient !,

but not 4 - with B1245 fixed as here
Code: Select all
`123456...457829...689731...214365...365978...798142..........9.......9...........`

The box clues are forced in B3678 and then it seems two similar clues in box 9 is always an invalid LS
It seems you are right, but I am not sure why !

@ mathimagics
well there is always a turn up in sudoku and LS
so there is no U4 in any of the 36 + 36 2-rows
and there is no U6 in any of the 84 + 84 3-rows

that grid is a one in a 19 billion !
coloin

Posts: 1879
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

coloin wrote:It seems you [Tarek] are right, but I am not sure why !

Is it because boxes {1379} force boxes {2468} to be compliant, and so box {5} must then follow?

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

Serg wrote:Conjecture "S"
Any Sudoku solution grid contains either UA4 or two-row (two-column) UA6 unavoidable set(s).

This also seemed to be a reasonable conjecture, but ...

Code: Select all
`123456789456789231789231564234867195518943627697512843372695418861374952945128376`

Code: Select all
` +-------+-------+-------+ | 1 2 3 | 4 5 6 | 7 8 9 | | 4 5 6 | 7 8 9 | 2 3 1 | | 7 8 9 | 2 3 1 | 5 6 4 | +-------+-------+-------+ | 2 3 4 | 8 6 7 | 1 9 5 | | 5 1 8 | 9 4 3 | 6 2 7 | | 6 9 7 | 5 1 2 | 8 4 3 | +-------+-------+-------+ | 3 7 2 | 6 9 5 | 4 1 8 | | 8 6 1 | 3 7 4 | 9 5 2 | | 9 4 5 | 1 2 8 | 3 7 6 | +-------+-------+-------+`

This grid has no UA4's, and only 4 x UA6's, none of which have the desired {3r2c} or {2r3c} patterns:
Code: Select all
`{12,13,41,42,71,73}{34,36,65,66,94,95}{41,49,51,58,88,89}{58,59,85,89,95,98}`

Sorry, Serg!
Last edited by Mathimagics on Sat Nov 30, 2019 4:51 pm, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1500
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

I may have needed to qualify my observation

for 9x9 Latin square you would need 4 boxes in 6 rows x 6 columns
for 16x16 Latin square you would need 9 boxes in 12 rows x 12 columns
for 25x25 Latin square you would need 16 boxes in 20 rows x 20 columns

tarek

Posts: 3553
Joined: 05 January 2006

### Re: Latin Squares and Latin Square puzzles

Code: Select all
`123456...457829...689731...214365...365978...798142..........9.......9...........`

I see now why there cant be a valid latin square grid with this ... and B9 is committed to be a valid sudoku 3*3 box
As it is displayed - there is no room for the two 9s in c9 or r9 therefore B9 can have only one 9
coloin

Posts: 1879
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:... Brendan McKay has identified all LS9's with no UA4 (ie no intercalates). There are 1707 ED grids in this list, and every one does have a UA6, except for this solitary case:

Code: Select all
`123456789234167895345678912416839527579324168658792341782913456891245673967581234`

I am very impressed by this result! What Brendan McKay's article did you cite?

Serg
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

### Re: Latin Squares and Latin Square puzzles

Mathimagics wrote:Some revision to that list of 20-clue LS puzzles on the "BC" grid. I did a vicinity search to {-3,+3} to try and find whether another grid might be revealed.

But no. I did find 200 or so candidates, but after processing with the revised CF function (which now checks conjugates, so is a true isomorphism checker), they reduced to just 14 ED puzzles, all on the same grid:

Hidden Text: Show
Code: Select all
`........9..1..4...3..6..9.8...........4..7.1.6..9....3.....1.....7.12.4.9.......6...4...8...1.......12..59..4..78..3....8.......5...1....9..15..8..3...4...........2.4..7....1.6..9..........45.7..2......9..1..4.........9.31.6.....1.....7....4..1.............4..731.6..9.............4..7..26..9..1..........4..7..2.459..1.....1....6.8............2.4.9........2....4.9.3.26....8...78...1.6.8............2.4..1..4.............7..2..5.784.............7..264.9..1.............7..2..59..1..4..1..4....9...........2..5.7.4.......1.....7.....5.78.2.........4..7..2...9..1..4.61..4..7.............2..5..84..7.............2..5..8.237.............2..597.1..4..1..4..7.9........7..2..5...4..7....1...........5..8.2.7.......4.....2.....8.23.5.1..45..8....5.......2...9....6..92..5..8...1............9.......97..26.....1...5.1.34...8.....6...73........4......3..6..97..2....7.............8..3...4..7..2...612...6.8.2............4.9.............4.9.3..6....8.2...9.3.5.48....2.........4..12.4..7......6..9..1.........6.89.3.....9.....4....1....9.3..6...........7.1..4..12.4..7..2.............5..84..7..2.............5..8..37..2.............5..8..3.56`

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........`

---

I see that these are also minimal (latin square) puzzles for the BC grid:

Code: Select all
`123......    12.......    1........    .........23.......    2........    .........    ........13........    .........    ........2    .......12.........    ........3    .......23    ......123........4    .......34    ......234    .....1234.......45    ......345    .....2345    ....12345......456    .....3456    ....23456    ...123456.....4567    ....34567    ...234567    ..1234567....45678    ...345678    ..2345678    .12345678                                                 21 clue      24 clue      29 clue      36 clue `

They have transformations to valid sudoku puzzles, just like the 20-clue did.
Each one produces 36 ED sudoku puzzles (on the same two sudoku grids as for the 20-clue puzzle).
For the 21 and 24 clue puzzles, all 36 sudoku puzzles are minimal.
For the 29 and 36-clue puzzles, none of them are minimal.

21C example:

Code: Select all
`123.....................45623...............4.....45673...............45....45678`
blue

Posts: 894
Joined: 11 March 2013

### Re: Latin Squares and Latin Square puzzles

Hi, Mathimagics!
Mathimagics wrote:
Code: Select all
`123456789456789231789231564234867195518943627697512843372695418861374952945128376`

This grid has no UA4's, and only 4 x UA6's, none of which have the desired {3r2c} or {2r3c} patterns:
Code: Select all
`{12,13,41,42,71,73}{34,36,65,66,94,95}{41,49,51,58,88,89}{58,59,85,89,95,98}`
I am very impressed again by your speed! Well done!

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 we should check all pairs of rows (36 checks) for their two-row UA sets sizes. Pairs having two-row UA sets with minimum size will be checked as r1/r2 rows candidates.

When we are checking r1/r2 rows candidates, we should check 2 possibilities for pairs of rows - which row will be choosen as r1. In both cases we'll get the same view of r1 and r2 rows, but necessary column permutations will be different to come to that canonic view.

If pair of rows contains several two-row UA sets of minimum size, we should check all possible orders of these UA sets (they must follow each other from the beginning of the r2 row).

Doing above pair of rows check, we should compute the rest (r3-r9) LS rows under given relabelling and given columns permutation.

This procedure will be fast, but it needs correctness proof ...

Serg
Serg
2018 Supporter

Posts: 701
Joined: 01 June 2010
Location: Russia

PreviousNext