Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Latin Squares and Latin Square puzzles

Postby coloin » Wed Nov 27, 2019 7:00 pm

Well I did wonder about the number, and I did think that it should be reduced by at least
9! - relabelling, 9! - column swaps 9! - row swaps, and finally a reflection - 2 ?
5,524,751,496,156,892,842,531,225,600 / 9!*9!*9!*2 ~ 57808760007.02 which is never going to be right, but thankfully a lot smaller than 3.7e17

FRom Latin square - Wikipedia

Code: Select all
all Latin squares of size n               5,524,751,496,156,892,842,531,225,600
reduced Latin squares of size n                         377,597,570,964,258,816

your progression
Code: Select all
Number of inequivalent Latin squares (or isotopy classes of Latin squares) of order n.
   1, 1, 1, 2, 2, 22, 564, 1676267, 115618721533, 208904371354363006,

and this one here
Code: Select all
Number of structurally distinct Latin squares of order n.       
   1, 1, 1, 12, 192, 145164, 1524901344, ? , ?


They defined "Structurally distinct" as to mean that the squares cannot be made identical by means of
rotation, reflection, and/or permutation of the symbols.

the 192 for n = 5 seems to be correct .... :roll: :!: :oops:

so its unclear what the n=8 or n=9 number is !!!!!
coloin
 
Posts: 1906
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Wed Nov 27, 2019 10:29 pm

ok, confusion reigns...... but i have looked at what those tables in Wikipedia really mean and its not pretty !
the absolute number of 9*9 latin squares - 5,524,751,496,156,892,842,531,225,600 [5e27] - this is equivalent to the 6e21 number
the number of "reduced* 9*9 latin squares - 377,597,570,964,258,816
this is the absolute number of 9*9 latin squares which have this
Code: Select all
123456789
2........
3........
4........
5........
6........
7........
8........
9........

So this should be an upper bound :?: and would appear to be comepletely accurate

looking at the statement in Wikipedia ...
Number of structurally distinct Latin squares of order n.
1, 1, 1, 12, 192, 145164, 1524901344, ? , ?

the n=4 is given as 12 [On the back of an envelope I can see 2 maybe 3 ]
the n=5 [192] details ! here
the n=5 [192] and n=6 [145164] was published as calculated here
the n=7 number was published as calculated at 1524901344 from here

But..... these are higher than the postulated upper bound of the reduced value, so I think the isotope class value is the number of ED solution grids as Mathimagics says !
Code: Select all
n   total[t]                       reduced              isotope         generated     t/n!^3         
1   1                              1                    1               1                           
2   2                              1                    1               1                           
3   12                             1                    1               1                           
4   576                            4                    2               12                           
5   161280                         56                   2               192                         
6   812851200                      9408                 22              145164         2.18           
7   61479419904000                 16942080             564             1524901344     480.21         
8   108776032459082956800          535281401856         1676267         ?              1659478.55     
9   5524751496156892842531225600   3775975709642588     115618721533    ?              115617520014.04
     
coloin
 
Posts: 1906
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Thu Nov 28, 2019 12:46 am

Aside from that combionotronics ... :!:

Code: Select all
147235689
714523968
471352896
253689174
325968417
532896741
689174253
896741325
968417532


maybe these latin squares have low clue puzzles .... or maybe high clue :roll:
coloin
 
Posts: 1906
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Thu Nov 28, 2019 3:31 am

Hi Colin,

The "structurally distinct" definition of the WikiPedia page is a red herring! It defines only a very limited number of VPT's (validity-preserving transformations), namely rotation and reflection.

I think that the correct definition of VPT for our purposes is:
If we permute the rows, permute the columns, and permute the names of the symbols of a Latin square, we obtain a new Latin square said to be isotopic to the first. Isotopism is an equivalence relation, so the set of all Latin squares is divided into subsets, called isotopy classes, such that two squares in the same class are isotopic and two squares in different classes are not isotopic.


Note that rotation/reflection operations can all be expressed as a combination of row/col permutations, so they are included.

We have defined here in the forum the notion of grid isomorphism - two grids are isomorphic if one can be obtained from the other via a VPT and relabelling. Thus, for Latin Squares, isomorphic is the the same as isotopic, and so the number of ED grids (for 9x9 Latin Squares) by our definition is the number of isotopy classes, ie 115,618,721,533.

Reduced (normalized) forms alone are not sufficient for comparing Latin Squares for isomorphism. Two grids might have different reduced forms but can still be isomorphic.

If you divide the number of reduced LS9's by the number of isotopy classes (ED grids), you get ~3,265,886. This is very close to the number of reduced forms that you can produce from a single LS9, which is 9 x 9! = 3,265,920. The difference (~34) can be attributed to automorphisms.

A reduced form can be produced by:

  • selecting any row to be the first row (9 ways)
  • selecting a column permutation (9! ways)
  • mapping the first row to {123456789}
  • sorting the rows

This is the basis of a Canonical Form function, which (unlike my earlier prediction), is likely to be just as quick as it is for Sudoku (3,265,920 LS transformations vs 3,359,232 for Sudoku). The CF function selects the minlex candidate from among all the reduced forms.
Last edited by Mathimagics on Thu Nov 28, 2019 2:05 pm, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1535
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby tarek » Thu Nov 28, 2019 6:39 am

As promised (Haven't been checked for isomorphism):
Code: Select all
Valid 22 clue LS puzzles that are also valid sudoku puzzles
...1..2....234.5....42..3..6......7.87...6.5.9....7.8........6.7.....4.....4.....
...1..2....234.5....42..3..6......7.87...6.9.9....7.5........6.7.....4.....4.....
...1..2.3..243.1....32..5..6......7.87...6.5.9....7.86.........7...........3.....
...1..2.3..243.1....32..5..6......7.87...6.9.9....7.56.........7...........3.....
...1..2.3..243.5....32..4..6......7.87...6.5.9....7.86.........7...........3.....
...1..2.3..243.5....32..4..6......7.87...6.9.9....7.56.........7...........3.....
...1..2.3..243.5....32..4..6....7.8.98.....577....8.9..........8...........3.....
..12..3.4...1..2....43..1..5....6.7.67...2.8.8....7........8.........4..7..4.....
..12..3.4...1..2....43..1..5....6.7.67...3.8.8....7........8.........4..7..4.....
..12..3.4...1..2....45..1..6....5.7.87...6.9.9....7........9.........4..7..4.....
..12..3.4...1..2....45..1..6....5.7.87...9.6.9....7........6.........4..7..4.....
..12..3.4...1..2....45..1..6....7.8.78...5.6.9....8........6.........4..8..4.....
..12..3.4...1..2....45..1..6....7.8.78...5.9.9....8........9.........4..8..4.....
..12..3.4...1..2....45..1..6....7.8.98...5.7.7....8........6.........4..8..4.....
..12..3.4...1..2....45..1..6....7.8.98...5.7.7....8........9.........4..8..4.....
..12..3.4...1..5....43..1..6....2.7.87...9.6.9....7........6.........4..7..4.....
..12..3.4...1..5....45..1..6....2.7.87...6.9.9....7............7....94.....4.....
..12..3.4...1..5....45..1..6....2.7.87...6.9.9....7........9.........4..7..4.....
..12..3.4...1..5....45..1..6....2.7.87...9.6.9....7........6.........4..7..4.....
..12..3.4...1..5....45..1..6....7.8.78...2.9.9....8........9.........4..8..4.....
..12..3.4...14.2....45..1..6......7.87...6.3.9....7.86.........7...........4.....
..12..3.4...14.2....45..1..6......7.87...6.9.9....7.36.........7...........4.....
..12..3.4...14.2....45..1..6....5.7.87..69...9....7.6................4..7........
..12..3.4...14.2....45..1..6....7.8.78..65...9....8.6................4..8........
..12..3.4...14.2....45..1..6....7.8.98.....377....8.9..........8...........4.....
..12..3.4...14.2....45..1..6....7.8.98.....677....8.3..........8...........4.....
..12..3.4...14.5....43..1..6......7.87...6.5.9....7.86.........7...........4.....
..12..3.4...14.5....43..1..6......7.87...6.9.9....7.56.........7...........4.....
..12..3.4...14.5....43..1..6....7.8.98.....577....8.9..........8...........4.....
..12..3.4...14.5....43..1..6....7.8.98.....677....8.5..........8...........4.....
..12..3.4...4..5....45..1..6....2.7.87...6.9.9....7........9.........4..7..1.....
..12..3.4...5..1....41..5..6....2.7.87...6.9.9....7........9.........4..7..4.....
..12..3.4..41..2.....3..1..5....6.7.67...3.8.8....7........8.........4..7..4.....
I'm already processing them to see if I can generate lower clue puzzles
User avatar
tarek
 
Posts: 3726
Joined: 05 January 2006

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Thu Nov 28, 2019 7:10 am

Great work, Tarek! 8-)

That's the first evidence of "bi-minimal" puzzles (minimal for Sudoku and LS) that we have, which aren't 20-clue or 38-clue!

I have established that 20-clue bi-minimal puzzles do exist on grids other than the BC grid:

Code: Select all
1.342....4...............562.4.3...................5673...4............5.....5678


That's another automorphic Sudoku grid (NA = 18).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1535
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby coloin » Thu Nov 28, 2019 1:21 pm

Well thats sorted then .... there is not as many grids as we thought, but still the big numbers are differing by 10^6,
so the minimum number of clues has to reflect that. And 115618721533 [11e11] as you say is only a factor of 20.
Glad that the min lexing tool will be quick, however that puzzle is an isomorph of the first puzzle posted ....

In fact your minexing tool will now discover that [EDIT the solution grids from] the first 2 puzzles are row swapped isomorphs [of the LS BC grid] :!: :!: :!: :!: :oops: :roll:

The BC grid [as here] is also the most canonical and the first on the list in the lexicon
Code: Select all
1234.....
234......
34.......
4........
.........
........5
.......56
......567
.....5678    original puzzle

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678   most canonical BC

+---+---+---+
|123|4..|...|
|4..|...|...|
|...|...|.56|
+---+---+---+
|234|...|...|
|...|...|...|
|...|...|567|
+---+---+---+
|34.|...|...|
|...|...|..5|
|...|..5|678|
+---+---+---+   isomorph of above, morphed to be a valid sudoku.


So some morphed LS puzzles may well turn out to have a valid sudoku isomorph !!
Last edited by coloin on Thu Nov 28, 2019 2:39 pm, edited 1 time in total.
coloin
 
Posts: 1906
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby blue » Thu Nov 28, 2019 1:30 pm

This fits well with Colin's post ...

Mathimagics wrote:I have established that 20-clue bi-minimal puzzles do exist on grids other than the BC grid:

Code: Select all
1.342....4...............562.4.3...................5673...4............5.....5678


That's another automorphic Sudoku grid (NA = 18).

It's one of 15 (Sudoko-ED) puzzles for that grid:

Code: Select all
123456789456789231789231564231564897564897312978123456312645978645978123897312645 (Sudoku-minlex)

.................1.....1..4..1..4..7..4..7.129........3..6..9..6..9.....89.3..6..
..............92....92.15...3..6...7.6........7......6..2..59..64..7...3.....2...
...........6.8.2.17..........1.6.8..5....7...97...3.5.3....5.7.......1......1.6..
........9..............1.....1..4.....4..7.1.9.......63..6..9.86..9....3..7.12.4.
........9.....9..1..9..1..4..1..4.9756.8..3...........3..6.....6........8..3..6..
........9.5........8...15..2...6..97....9...29...2...6.1...5....45..81...........
........9.5...9..17..23..6.2...6.................2.....1...59.86...7..2..9......5
........94.6.8.2............3.5...97..4........8.2.4....2.4.......9....3.9.3....5
.....6..9.....9..............1........4....1.9....3..6.12.4..7.6..9.8..3..7.1..4.
.....6.8..5.7....1.......6..315....7..........7.1......1.......6....8.2.8....264.
.....67.............92.....2.15...9..6...73...7...34.6..2........59...2.......6..
.....67....67.92...8..3...4.3............7............31..4...8.4......3..7..26..
..3..6..9..6..9.....9......................1.9.8..3..6.1..4..7..4..7.12.....1..4.
..3.5...94.....2....9.3....2....48......9..........4.............597...38....264.
..3.5.7.94..........9.3.5..2....4.......9.3.................9..64...8.2.8....2.4.

Those 15, and the 6 puzzles from here, form a/the complete list of 21 ED Sudoko puzzles, that are LS-isomorphic to the (LS) puzzle in the opening post.

1st of the 15 above:

Code: Select all
.........
........1
.....1..4
..1..4..7
..4..7.12
9........
3..6..9..
6..9.....
89.3..6..
blue
 
Posts: 894
Joined: 11 March 2013

Re: Latin Squares and Latin Square puzzles

Postby coloin » Thu Nov 28, 2019 3:49 pm

Wow
So 1 LS grid and 1 LS puzzle

I think I was nearly getting there !

And the reason I nearly twigged this ....is because I was thinking about the bands :!:

In sudoku we have
3 bands of 3 rows, and 3 bands of 3 columns [6 3-bands] 416 ED with 44 gangsters.
in each 3-band there are 3 2-row bands.
each 3-band can be solved with minimum 2,3,4,5,6 clues depending which one of the 416 it is
each 2-row [15 ED] can be solved with minumum 1,2 or 3 clues depending which one of the 15 it is
Hidden Text: Show
Code: Select all
000000000000000000000000000000000000000000000000000000000000000123456789456789123
000000000000000000000000000000000000000000000000000000000000000123456789456789132
000000000000000000000000000000000000000000000000000000000000000123456789456789231
000000000000000000000000000000000000000000000000000000000000000123456789457189236
000000000000000000000000000000000000000000000000000000000000000123456789457189263
000000000000000000000000000000000000000000000000000000000000000123456789457189326
000000000000000000000000000000000000000000000000000000000000000123456789457189623
000000000000000000000000000000000000000000000000000000000000000123456789457189632
000000000000000000000000000000000000000000000000000000000000000123456789457289163
000000000000000000000000000000000000000000000000000000000000000123456789457289613
000000000000000000000000000000000000000000000000000000000000000123456789457289631
000000000000000000000000000000000000000000000000000000000000000123456789457389612
000000000000000000000000000000000000000000000000000000000000000123456789457389621
000000000000000000000000000000000000000000000000000000000000000123456789457893612
000000000000000000000000000000000000000000000000000000000000000123456789457893621


However in LS world

In each solition grid there are 36 2-rows [and 36 2-columns] [9*8 / 2!]
{12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49,56,57,58,59,67,68,69,78,79,89}
there are therefore 9*8*7 / 3! = 84 3-rows [and 84 3-columns]

So potentially there may well be 84 different 3-rows ... hmmm

least said for now i think

apart from mmentioning the BC grid
Code: Select all
123456789
231564897
312645978
456789231
564897312
645978123
789231564
897312645
978123456    most lex-minimal LS BC


123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678   most lex-minimal BC valid sudoku 


So in LS World
In this grid there are only 2 types of 2-rows
Im not clear exactly how many types of 3-rows .....[?]
At least 1 of the 84 are solvable in 2 clues [3-row/band 29]
Some of the other 3-rows maybe need 6 clues .....[?]

And going back to the puzzle
Code: Select all
1234.....
234......
34.......
4........
.........
........5
.......56
......567
.....5678


there are 9!*9! ways to row swap the puzzle , and blue has found that 21 of those ways result in a valid [ED sudoku] puzzle
Last edited by coloin on Thu Nov 28, 2019 6:16 pm, edited 2 times in total.
coloin
 
Posts: 1906
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby m_b_metcalf » Thu Nov 28, 2019 4:18 pm

Mathimagics wrote:Great work, Tarek! 8-)

That's the first evidence of "bi-minimal" puzzles (minimal for Sudoku and LS) that we have, which aren't 20-clue or 38-clue!

Indeed. Nit pick : I'd just like to point out that the puzzles 9, 14 and 15 each have one redundant clue when treated as vanilla sudoku.

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10984
Joined: 15 May 2006
Location: Berlin

Re: Latin Squares and Latin Square puzzles

Postby blue » Thu Nov 28, 2019 4:36 pm

coloin wrote:there are 9!*9! ways to row swap the puzzle , and blue has found that 21 of those ways result in a valid [ED sudoku] puzzle

It sounds like a lot of work, but there are only 280*280 ways to collect the rows & columns into bands & stacks.
For 72 of them, the re-ordered solution grid was also a sudoku grid.
For the corresponding sudoku puzzles, 21 were ED, and there were 2 ED solution grids.

Added: 280 = 28 * 10 ...
    28 = (8*7/2) ways to choose two rows to go with the original row 1
    10 = (5*4/2) ways to choose two rows to go with the first row not chosen above.
---

Here are some more "dual-minimals".
10 each for sizes 22-28.

Hidden Text: Show
Code: Select all
...........6.8.1..7....3.5..14.6...83..5.........1....5.8....3...1...8..93...5.7. (22)
....5..894.6...1........4.5...59..78..4...2.........9........57642...8........6.. (22)
....56......7.....7891.........6......78.........4365..........6...254..8729..... (22)
..3......45.......79....465.........56......4..932.....4.........2913.....12..3.. (22)
.2...6.....6.891..7........27.....5.39.2...7.5......2......8........46......618.. (22)
..............9.....9..1....14..7.9.36......7........6..1.94.7.6..3....88..6..3.5 (22)
1.3..6..9..6..9..1..9..1.....1.......4...3....6..2.45..7..4..2.....7..4........7. (22)
1..4.....4.........................7.....7..29..1..4..31.94.6....2.78..5..7..5.23 (22)
.....67..4.7.8.2.........1.2...7.8..7.....4..8.........1.6.5.4......1.6..6...3.5. (22)
12.........7.8...6.......1.2...6........7...8..8.........84.6.75....1.2.9....215. (22)

....56...4.....123......4...1.567...3.....2.4.6..............42....7.8.....695.7. (23)
...4.....4.678.........25...........64.89......5..7.31...9.1.5....64.........5.12 (23)
...4..789.56..............4......84.635.2.....1......2...9..4.85613..........5... (23)
1.3.......5..8........3.....47..5.1...5..1.7...1....5....86.2..6.....8..8..92.6.. (23)
...456.........123..........1..47..........318.4.65......5.4.....1....7.9.....312 (23)
12.4..7..4..7..1..7..1..........3.58..8..5.....5..8.23.7......66.............1..5 (23)
.2.456.........132...1............7.....64.....8...321.......1386..45......67.... (23)
............789...7.....546..8.1.....3.978.........45.3.5....64...89...........15 (23)
...4.6.....7.8.....89.7..1...85......71.3...8......5......1.......3.5.6....6.435. (23)
.2.4...8...7.......8.3.2..5..6.1.9....1...6..9.5.6.1...1..........29..4....8...2. (23)

....5....456.8.......1.3....1.3.7.9........1.5.82..3..6.....8..845.......7...1.3. (24)
.2.456.........1.3.....2....1....938..4825..............1...8..8..2.4...9.....371 (24)
.2..........7891.3...13....2.4........59........318...549....726.2....4......3... (24)
............789...7.....564....97...36....4.5......2.6.179.8...6...72.........65. (24)
.2....789..........8.213.........9.4...1.2...96....8.7.......985.2.31.......24... (24)
1.3..6.....6.89.....9.3......8.943..7..8...15...1.3..........515........6......27 (24)
......78945........89...14.2...35....6....891.........5....2...7.2563.........9.. (24)
1..4.6....57......6....31.....6...7...5..13.2...........27...95....186....95....7 (24)
1......89..7.....6...372...2..534...3...27.........9.......3.........89498.....61 (24)
..3..6...4...892......2....2..9......6.7.5..1.71.....6.36....1.8....29..91....... (24)

......789......1..7..123...2..3.5.......1.94....6.2....4....89759...8..4....3.... (25)
........94..789.........546.....7.51...39....9..82......5.6..12.....8.....1...465 (25)
...456....5....132.8..........96..1.6.584......1..5..3...6.4..........21.1....37. (25)
......7894567..................1.897..8.9.1.2.6....4..3.5......6.25......4....91. (25)
12.4.....4..18.2.668.2..4.......5.67..5..7.9..4.8...........6.88......7........5. (25)
...45..894..1.9...6.8......285...6.....591...7...........9421..872....6.......... (25)
...4.6.......89......73......9..465...6.254....4....9.7...9....8...7..23.3.2....7 (25)
1..4.....4.71.9.....6..3...2.....5.8....4............3.6..3.8.2.8..6.3.59.15...4. (25)
......7.9...18.2..9.8.23.........6.....831....7....593..........8.512...7.....965 (25)
1..4.....4..1..26.6.....14..74..8......9..8.7.8..73.2......5.18.3...7...9........ (25)

.....67.9456.8.....8..2....2.4...97....8...........31.3......9.542.18....68.4.... (26)
...4...894........7...3.64.239.78......6.......7.23...372..5.......17.9....8....6 (26)
.....67..45..8.1.....231..6.94..3.........2..8359.........67.2.54....6.79........ (26)
1....6.89..7.....66......5124.37.....3.94.....7.6..3..........55....186.....9..2. (26)
1....67....7.8.2..6.9..7.....57..8..3..9...7.....1...4.1...3....3..41..8..65..4.. (26)
...4....94.....2...9..73..42.5....6.38...4..7..6.2.85..3......8..98.......2...69. (26)
......789.5.1.....6..732....86...94.......6.8..1..3......3.78...1.....9..3.215... (26)
....5..8....1.923.896.7............17..59....965..4........1.245..........2...318 (26)
...4..78.45......6..6..7...231........5...8...6......5...8..9.....9.437.69..3..41 (26)
.23..6.8....1..........71.5...71...4.946.5..183.......348...9....2....3...9.7.... (26)

..3..67....678...3.....3..4.14....9..9.....1....91..5.3..59.6....8..4...9...78.4. (27)
1...5....45...9...79.........1.7.6...3.62.8.....59.2....2...4.6...8....2..42..318 (27)
123.....9....8...2......45.2.......3....675....5.2.64..3.6...71..21.......857..6. (27)
1....6...45......6.89...15....7....3...362..7.....8.62.4......88..6..32.9.1...4.. (27)
..3.....945.............514..89.1...34..6......6832....3.6..8......9..65.....8471 (27)
1..4...8....1..2.6.89..........6.3.45.8....7.9....7.52...6......6....543895..4... (27)
.2..5.78.45.1.9....9..7..5...46..8.3......6.7..6.92.....2.........9.1.....1...378 (27)
123....89....8....8.9...51.298.....13...6..5..1......85.26.3......5.46.....7..... (27)
..3.56...45.......96..3....2.....917...9....25..24......98...71.4...18.3.1...4... (27)
.2.4..78.45....2..8.9.3.5....136......67.4..1....91...5...1...6..8........26..8.. (27)

..34567.......9.2.....3.....1.......5649.3...8..51....3.5..7..2.8....9.7.7...24.8 (28)
1.3....894.6.....3798....4.......5.....5.7...9...12.......7.9.8..9.253.....1.425. (28)
1..4..7..4.6...1...8.1..5.423..9.....95.73...8..2......6..27......9....3..2.68.7. (28)
...4.67......8.2...8.3.7.5.2.1.9..........1..968.1........756..5.68....48....4.75 (28)
.....6.8.457.8.........3..42.5...1..7.4..1..2.9..3..6.....1....5726...4...83.26.. (28)
.2.4...8......9236..9..........14.65.1.6...289.4..5...5.....872741......8.....6.. (28)
...456.89....89236.9.2.....2.1.4.3..3.5......7.......1...894.6....6...9..3......2 (28)
...4..7.9..7..9..6...3.......9.6.84....7...95..59...72581.....3.4.63.....3..41... (28)
.2...6..94.7.8.....6.7.2.....1....98.85.9...49.4.7...1..8.1.46......38.....64.... (28)
....5.......1....36....7....3...8.4..8...3912.1694......1.25.9.86.3..1....5.6..2. (28)
blue
 
Posts: 894
Joined: 11 March 2013

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Thu Nov 28, 2019 4:53 pm

blue wrote:Those 15, and the 6 puzzles ... form a/the complete list of 21 ED Sudoko puzzles, that are LS-isomorphic to the (LS) puzzle in the opening post.

I have got my CF function going now, and can now confirm that result.

Do you agree that the LCF (LS, canonical form) of the BC grid is this?
Code: Select all
123456789231564897312645978456789231564897312645978123789231564897312645978123456
User avatar
Mathimagics
2017 Supporter
 
Posts: 1535
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby blue » Thu Nov 28, 2019 5:21 pm

I haven't tried to write a LCF function, but that looks correct.
blue
 
Posts: 894
Joined: 11 March 2013

Re: Latin Squares and Latin Square puzzles

Postby Serg » Thu Nov 28, 2019 11:47 pm

Hi, people!
I suspect that nice article "Latin square" on Wikipedia site was written by Red Ed. (I beleive this article has some his stylistic features ...)

Thinking more about "isotopism" as a rule of LS puzzles/grids equivalence. It is evident, that lack of transposing among isotopic transformations looks strange. Transposing is obviously VPT for LS puzzles/grids. To get true isomorphic transformations for LS puzzles/grids (including transposing) we should consider conjugate Latin squares (also parastrophes - see Wikipedia article). For every LS there exist 6 paratopic transformations, exchanging rows/columns/digits of LS. (These paratopic transformations resemble blue's F/G/E transformations for SudokuP - they turn LS inside out.) Here they are.

1. "Do nothing".
2. Exchanging rows and columns (r <--> c) - usual transposing.
3. Exchanging columns and digits (c <--> d) - every cell of LS, containing digit, moves to another column in its row - the new column is determined by old cell's digit, the new digit value is determined by old cell's column.
4. Exchanging rows and digits (r <--> d, similar to exchanging columns and digits).
5. Cyclically exchaning rows, columns and digits (r --> c --> d --> r).
6. Cyclically exchaning rows, columns and digits (d --> c --> r --> d).

Here is an example of applying paratopic transformation number 3 (cd-exchanging).
Code: Select all
1234.....
234......
34.......
4........
.........
........5
.......56
......567
.....5678    original LS puzzle

1234.....
.123.....
..12.....
...1.....
.........
....9....
....89...
....789..
....6789.    transformed LS puzzle

When we shall account for isotopic AND paratopic transformations, number of ED 9x9 LS will be diminished to 19,270,853,541 (see number of "main classes" in Wikipedia article). This number 4 times greater only, than the number of ED Sudokus.

Number of such isomorphic (isotopic and paratopic) transformations can be calculated as follows.
Let's consider LS in reduced form only. Each LS permits 9! columns permutations, there are 9 ways of choosing a row, that will be the first LS row. The only relabelling and the only swapping of r2-r9 rows restore reduced form. So, there are 9! x 9 x 6 = 19,595,520 "true" isomorphic transformation that we should check during LS canonicalization.

Serg

[Edited. The number of isomorphic transformations was not calculated correctly. Thanks to Mathimagics for his correction.]
[Edited2. I was wrong saying that blue discovered F/G/E transformations for SudokuX. He did it for SudokuP.]
Last edited by Serg on Sun Dec 15, 2019 1:38 pm, edited 2 times in total.
Serg
2018 Supporter
 
Posts: 710
Joined: 01 June 2010
Location: Russia

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Fri Nov 29, 2019 3:31 am

Hi Serg,

You are right. Conjugation - interchanging of the (r, c, d) triplets - is, of course, a VPT.

And so the number of ED grids is 19,270,853,541.

Serg wrote:Number of such isomorphic (isotopic and paratopic) transformations can be calculated as follows.

Let's consider LS in reduced form only. Each LS permits 9! columns permutations, the only relabelling and the only swapping of rows restore reduced form. So, there are 9! x 6 = 2177280 isomorphic transformation that we should check during LS canonicalization.


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

PreviousNext

Return to Sudoku variants