## Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: Latin Squares and Latin Square puzzles

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`

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

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

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

Aside from that combionotronics ...

Code: Select all
`147235689714523968471352896253689174325968417532896741689174253896741325968417532`

maybe these latin squares have low clue puzzles .... or maybe high clue
coloin

Posts: 1906
Joined: 05 May 2005

### Re: Latin Squares and Latin Square puzzles

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.

Mathimagics
2017 Supporter

Posts: 1535
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

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

tarek

Posts: 3726
Joined: 05 January 2006

### Re: Latin Squares and Latin Square puzzles

Great work, Tarek!

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

Mathimagics
2017 Supporter

Posts: 1535
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

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]

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

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.129........3..6..9..6..9.....89.3..6..`
blue

Posts: 894
Joined: 11 March 2013

### Re: Latin Squares and Latin Square puzzles

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

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
`123456789231564897312645978456789231564897312645978123789231564897312645978123456    most lex-minimal LS BC 123456789234567891345678912456789123567891234678912345789123456891234567912345678   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

Mathimagics wrote:Great work, Tarek!

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

m_b_metcalf
2017 Supporter

Posts: 10984
Joined: 15 May 2006
Location: Berlin

### Re: Latin Squares and Latin Square puzzles

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

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`

Mathimagics
2017 Supporter

Posts: 1535
Joined: 27 May 2015
Location: Canberra

### Re: Latin Squares and Latin Square puzzles

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

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

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.

Mathimagics
2017 Supporter

Posts: 1535
Joined: 27 May 2015
Location: Canberra

PreviousNext