The New Sudoku Players' Forum

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

by **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.

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

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

by **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 | +-------------------+

by **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!

by **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?

by **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 ! :!:

by **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?

by **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!

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

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

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

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

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

The New Sudoku Players' Forum

Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles

Re: Latin Squares and Latin Square puzzles