Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Latin Squares and Latin Square puzzles

Postby Serg » Fri Nov 29, 2019 9:08 am

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

Postby Mathimagics » Fri Nov 29, 2019 10:04 am

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

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

Re: Latin Squares and Latin Square puzzles

Postby Serg » Fri Nov 29, 2019 10:51 am

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

Postby Serg » Fri Nov 29, 2019 10:42 pm

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
123456789
21.......

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
123456789
231......

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

Postby Mathimagics » Sat Nov 30, 2019 8:30 am

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

Re: Latin Squares and Latin Square puzzles

Postby tarek » Sat Nov 30, 2019 1:39 pm

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

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Sat Nov 30, 2019 2:30 pm

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

Re: Latin Squares and Latin Square puzzles

Postby coloin » Sat Nov 30, 2019 2:31 pm

@ 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 ! :!: :D
coloin
 
Posts: 1879
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Sat Nov 30, 2019 2:45 pm

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

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Sat Nov 30, 2019 3:19 pm

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

Re: Latin Squares and Latin Square puzzles

Postby tarek » Sat Nov 30, 2019 4:19 pm

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

Re: Latin Squares and Latin Square puzzles

Postby coloin » Sat Nov 30, 2019 6:25 pm

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

Postby Serg » Sat Nov 30, 2019 10:15 pm

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

Postby blue » Sat Nov 30, 2019 10:43 pm

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.6
1..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...6
12...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........    .........    ........1
3........    .........    ........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......
.........
......456
23.......
........4
.....4567
3........
.......45
....45678
blue
 
Posts: 894
Joined: 11 March 2013

Re: Latin Squares and Latin Square puzzles

Postby Serg » Sat Nov 30, 2019 11:05 pm

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

Return to Sudoku variants