Latin Squares and Latin Square puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Latin Squares and Latin Square puzzles

Postby coloin » Sun Nov 24, 2019 6:55 pm

Latin Squares

As a varient, some say forerunner of Sudoku, It desrves a recent thread.
Recently a version of Sudoku Explainer for Latin Squares has been developed by workers

A more up to date version of Sudoku Explainer which can also process Latin Square puzzles is available here as SukakuExplainer

Relevant discussions regarding the historical origins etc of Latin squares are leonard Euler and there is probably more written on the forum in the depths.

Latin squares can be size n, and for these discussion purposes Latin Squares refers to the 9*9 Latin Square grid [solution grid]case.

There are significantly more 9*9 LS solution grids [7e17 vv 5e11] Edit....11e11 vv 5e9 is the correct figure

Latin square puzzles can be termed LS or LSQ puzzles or historically LQ [Q also for quasi]

Sudoku solution grids, ie 9*9/3*3 are all 9*9 LS solution grids

Two grids [actually the same LS grid] of note emerged recently, generated using a method suggested by qiuyanzhe and it was an easy way to get low clue puzzles

Code: Select all
123456789                1234.....                                               
234567891                234......                                               
345678912                34.......                                               
456789123                4........                                               
567891234                .........                                               
678912345                ........5                                               
789123456                .......56                                               
891234567                ......567                                               
912345678                .....5678         Valid 20 Clue LS puzzle             

                                                                                 
1234.....234......34.......4.........................5.......56......567.....5678
 


This one was originally found as valid sudoku puzzle which coincidentally was a valid LS puzzle
Code: Select all
123456789                1234.....                                                                               
456789123                4........                                                                               
789123456                .......56                                                                               
234567891                234......                                                                               
567891234                .........                                                                               
891234567                ......567                                                                               
345678912                34.......                                                                               
678912345                ........5                                                                               
912345678                .....5678   Valid 20 clue Sudoku and LS puzzle -  grid named "Back Circulant"  BC grid                                                                                                                 
                                                                                                                 
                                                                                                                 
1234.....4...............56234.....................56734...............5.....5678                               


using qiuyanzhe's method here these are easily made ... but it is not proven that this is the miniumum

Overall there are more Essentially Different LSQ grid solutions [11e11 isotopes [In wikipedia isotopes can be read as isomorphs]] .... and probably more minimal puzzles per grid solution

And paradoxically these 20C latin square puzzles have been found / constructed, even before 21C and larger puzzles !!
From initial searches its probably a safe bet that this will be the minimum.

The upper bound for the minimum number of clues for a latin square of sise n as stated above was n^2 / 4 e.g 9^2 / 4 ~ 20
Looking at the examples below this is the same as [n/2 ]^2 and this would seem to hold for larger n - albeit a little more difficult to prove !

Code: Select all
 8*8
 
 1 2 3 4 . . . .
 2 3 4 . . . . .
 3 4 . . . . . .
 4 . . . . . . .
 . . . . . . . .
 . . . . . . . 5
 . . . . . . 5 6
 . . . . . 5 6 7    16 clues
 
 7*7
 
 1 2 3 . . . .
 2 3 . . . . .
 3 . . . . . .
 . . . . . . .
 . . . . . . 4
 . . . . . 4 5
 . . . . 4 5 6     12 clues
 
 6*6         
             
 1 2 3 . . .
 2 3 . . . .
 3 . . . . .
 . . . . . .
 . . . . . 4
 . . . . 4 5       9 clues
 
 5*5         
             
 1 2 . . .
 2 . . . .
 . . . . .
 . . . . 3
 . . . 3 4         6 clues
 
 4*4       
           
 1 2 . . 
 2 . . . 
 . . . . 
 . . . 3           4 clues
 
 3*3
     
           
 1 . . 
 . . . 
 . . 2             2 clues 
Last edited by coloin on Fri Nov 29, 2019 4:57 pm, edited 2 times in total.
coloin
 
Posts: 1864
Joined: 05 May 2005

Historical Note

Postby Mathimagics » Mon Nov 25, 2019 3:32 am

coloin wrote:from qiuyanzhe's theorem here these are easily made ... but it is not proven that this is the minimum


Perhaps that should probably be "qiuyanzhe's method" rather than theorem.

The case of the 20-clue minimal Sudoku puzzle which is also a minimal Latin Square puzzle (minimal LS puzzles are called "critical sets" in the LS literature) has its origins back in 1978, in this paper:

  • D. Curran & G.H.J. van Rees, Critical sets in latin squares, Cong. Numer. V22 (1978), 165-168.

This appears to be the first known serious treatment of critical sets in Latin Squares (minimal LS puzzles). Coincidentally (?), the very first Sudoku puzzles (created by Howard Garns) appeared in American newspapers the very next year (cf https://en.wikipedia.org/wiki/Sudoku).

The authors discovered that, from the "Back Circulant" Latin Square of any size N x N, one can construct a critical set of size floor(N^2/4), by specifying clues in two opposite corners of the grid.

qiuyanzhe has cleverly noticed that the Back Circulant grid has an isotope (produced by a simple row-reordering) that turns it into a Sudoku grid, and that this works for any box size, and indeed for any rectangle size. Applying the same row-order to the minimal LS puzzle thus produces a minimal Sudoku puzzle.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Minimal Sudoku + LS Puzzles

Postby Mathimagics » Wed Nov 27, 2019 6:48 am

Despite the apparent ease with which we found examples of both 20-clue and 38-clue puzzles which are minimal as both Sudoku and Latin Square puzzles, it seems that finding other instances is really hard!

The 20-clue examples are all on the "BC" grid, which is the Sudoku grid that corresponds to a simple row-reordering of the Back Circulant 9x9 Latin Square. There are 6 ED puzzles that qualify:
Code: Select all
.2.4.6............7.9....5........9.5.7.9..3....2.4....4.6.8..2.....2...9......7.
1......89.567..............2.....891.67......8.........4567.....7.......9.......8
.23..67..4...8.........3....3...7...5..89...48..................7...23..9...4...8
1....6....5........89...45.2...67..1.....1....9....5...45...9..6...12............
.....678945...............62345.....5...............67345.....................678
1.3.5.7........1...8......6..........6.8....4..1.3.5...4.6.8..2....1.3..........8


The 38-clue examples, of which there are now 22, all on different grids, were found by testing Mladen's collection of 2 million x minimal 38-clue Sudoku puzzles:
Code: Select all
1.3...78..57...2.669.....15.........3798..5.151.9.387276.3..128...6.....931..86.7
..345.789..........8923754..3.76.894..6........834267....62..57....734.8...5.496.
.........457.892...897324.5.948.1...5.827....71..93.........1..845.17..2.713285..
..345.789..........8923754..3.76.894..6........834267....52..67....734.8...6.495.
1.3...7.9.57...26.68.....51.........76.83.1928319..67.378.9.51.51.3..927...5.....
12.4.678.4..18..6.68..2741.29.87.34..3.9.48..84..3297..1.....9..........96....1.7
1.3...78..57...2.686.....14.....1...375..2.616.15..4275362.4.787.8..5642.........
12.4.678.4..18..6.68..2741.24.83.97..3.9.48..89..7234...........1.....9.9.2...13.
..345.789.5.......8..2375.4....648.5...52..76...7.349...267.948..6........83426.7
...4....945..8.23.6892.3.54.....7...79....523865..2.97.76......5.8..4.6294....375
...4....945..8.23.8692.3.54.....7...685..2.9779....523.76......5.8..4.6294....375
...4....945..8.23.6892.3.54.....7...79....325865..2.97.76......5.8..4.6294....573
...4.6...45718....69..731........4..84.3679..97584.....8.....1.5.971...371.63859.
1.34.67.9.......3....73.1.4..83.54.7..4.978.5..58.439.5..6.897..869..5.1...5....8
1.34.67.9.......3....73.1.4..53.48.7..8.974.5..48.539.5..6.897..869..5.1...5....8
12.4.6..94.71.9..66.9.27..427.8.4.9...49.....9.52..4.8.1.......5.671....7.26.8.51
....5....45.1..2.66.9..21.524.8..3.139..148.28..2.3...53.9..61...8.....396.3.15.8
....56......1.9.36...3...152.967.143..493..677...1......27...5..4529..7197.56..24
.......89457.89..3.8972345..75.4139...4.......9137254.....17...7.2..8....1823....
.2345.789457..923....2.3....3654.897.7539.46...4.......62...9.8......67.7.8....2.
.......89457.89..3.8937245..75.4139...4.......9172354.....17...7.2..8....1823....
.2....7..4.7..92.66......4.2....8..357..938.283.2..497.6.8..9..745.6.3.8.8.53.6.4


Attempts to find other examples by random reduction searches, despite having checked billions of minimal LS puzzles, have yet to turn up a single case where that puzzles is also minimal Sudoku.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby m_b_metcalf » Wed Nov 27, 2019 7:38 am

Slightly OT, but I started making some tests myself on the Patterns Game file but stopped when 1to9only announced his negative result. However, this entry
Code: Select all
050020090400000008010000030000106000700080004000704000020000060800000003090030050    7.4/1.5/1.5 gsf   

gave my solver in LS-mode severe indigestion for a reason I can't determine. Any idea?

Thanks,

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

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Nov 27, 2019 8:07 am

Hi Mike,

Is your LS solver stopping at the 2nd solution? If not, my LS solver suggests that there are 64,417,216 solutions to wade through.

Cheers
MM (the other one)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby m_b_metcalf » Wed Nov 27, 2019 8:19 am

Mathimagics wrote:Hi Mike,

Is your LS solver stopping at the 2nd solution? If not, my LS solver suggests that there are 64,417,216 solutions to wade through.

Cheers
MM (the other one)

Yes, but it takes an unusually long time to get to it.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10597
Joined: 15 May 2006
Location: Berlin

Re: Latin Squares and Latin Square puzzles

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

Thanks for that work, very good !
Indeed its all very strange that we have got potentially minimal and maximal size puzzles so easily - and that is despite the huge number of ninimal LS puzzles inbetween.
As the maximum side is a whole league harder probably a little look at the minimums first !

Maybe 20 clues is the minimum number to convey enough information to determine the 81 clues in a LS solution grid
If this is easily proven then there is no point in random searching !
Looking at the puzzles in many [? all] puzzles there must be 8 clues in total in a row and column - ie ED = *.*/*.*/1.5 - is this so ?

The LS puzzles essentially are puzzles which solve without using box constraints
Maybe all sudoku puzzles [minimal and non minimal] with less than 20 clues need to use a box/single to solve
Perhaps the easiest search would be to take a selection of the easiest 18 clue puzzles [SE1.5] and add a clue x 63 ways, each 18C + 1 puzzle has a extra chance /clue to overcome a box constraint .

Here is a grid with plenty of man made U4s
Code: Select all
123456789
216547398
341825967
435189276
598712643
652971834
789364125
874693512
967238451


As sudoku is a problem in unavoidable sets and hitting sets - I manually made this solution grid which has a lot of U4s - but with r19c19 covering many ... hmmm
which makes me realize that I have no idea what the MCN of this LS might be or any LS grid for that matter !
coloin
 
Posts: 1864
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby tarek » Wed Nov 27, 2019 3:43 pm

I'm not sure if this helps but I have a number of valid 22 clue LS puzzles which are also valid Sudoku puzzles.

I can do a vicinity search to see if I can find anything with less clues?

tarek
User avatar
tarek
 
Posts: 3416
Joined: 05 January 2006

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Nov 27, 2019 4:37 pm

Tarek, can you post those 22-clue examples?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Nov 27, 2019 4:39 pm

Colin, I tested your grid above with 30 million reductions to minimal, and found some 27-clue puzzles, nothing smaller:
Code: Select all
1......892...47.......2....4..1..27..9...2..3.5.9..83.7....41....4.93....6.....51 # 27
1......8...65.7...3.......7.35.....6....12.4..5.9..8....936...58....3.1296....4.. # 27
1......89...547....4..25....35..9..6....1...365.9.......9..4...8..6...129..2....1 # 27
1.....78...65.7.....1.......3......659.....43.5.9...34...36...5.7.69...2..7..84.. # 27
1...56..9...5..39.3..........5....7.....1.6..6....18.4.89....258..693.....72...5. # 27
...4..78921.......34..25...4..1...7.5....2..36.29......8....1......93..2..7.38... # 27
.23....89...547............43...9..6598.....36..971...7...641.......3..2..7...4.. # 27
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby coloin » Wed Nov 27, 2019 4:43 pm

Excellent
The distribution of these puzzles per individual grid ..... is not what we are used to !
coloin
 
Posts: 1864
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Wed Nov 27, 2019 4:50 pm

tariq wrote:
Code: Select all
.5342.8..528.......6.137...4...8.5...7...8....4.7.3.1..1.....6...564.2.7..9.6.... ED=7.2/7.2/6.6

Well thats very impressive, and the record so far !!! :D

Edit - higher rated puzzles have been found
Code: Select all
468.....15.142..6.27.64.....56..8.248..3.....14.....856....79.2.2..53......7..... ED=9.6/2.3/2.3 - tariq
.8....5.4...7....814..32...2.6.54......6.79.....4.9.2639.....1...3.1..6.6.5....8. ED=9.4/1.5/1.5 - 1to9only
3....5....9.1..7..82.....76...9..5.45...6.4...7...231...6.83.....5.4..914......29 ED=9.3/9.2/9.0 - 1to9only
8..5..6..9...34..1..38..5..3.9....8..9...742...7.86..4....2..56..1.72.4..3.1..7.. ED=9.2/9.2/9.2 - 1to9only
4...8...6.5694......73...9..9......1618..5..93...2.7.....6.1..58..1.32.......48.. ED=9.1/9.1/9.0 - 1to9only
6.7..4.1...8..9.5.9...286...4.7.23...6.2..8.....38.1.451..4...9..5.3......6.....7 ED=9.0/9.0/9.0 - 1to9only
....8.2...8.6.5....4623.7..92......1..43.6.2....7...38....6734.1.7....5.459.2.... ED=8.9/8.9/8.9 - 1to9only
Last edited by coloin on Wed Nov 27, 2019 6:10 pm, edited 1 time in total.
coloin
 
Posts: 1864
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby coloin » Wed Nov 27, 2019 5:02 pm

tarek wrote:I'm not sure if this helps but I have a number of valid 22 clue LS puzzles which are also valid Sudoku puzzles.
I can do a vicinity search to see if I can find anything with less clues?

tarek


hmmmmm
its still muddy for me ! :roll:
A distribution from a few random LS solution grids will surely tell more !
the chances of a random LS puzzle being from a valid sudoku solution grid [unless planned] might be
11e11/5e9 ~ 1 in 20 ~ but as we shall see later this might envolve some row/col swapping to potentially convert a LS grid to a valid sudoku grid !
but all sudoku solution grids are valid LS solution grids
sudoku puzzles have an extra constraint so generally need less clues
if a sudoku puzzle doesnt use box techniques in the solving path - it will be a valid LS puzzle [ :?: ]
a sudoku puzzle with a few extra clues will be non minimal but have more chance of being a valid LS
so i suppose there isnt really a requirement for the sudoku puzzle to be minimal ...
Last edited by coloin on Thu Nov 28, 2019 7:16 pm, edited 1 time in total.
coloin
 
Posts: 1864
Joined: 05 May 2005

Re: Latin Squares and Latin Square puzzles

Postby Mathimagics » Wed Nov 27, 2019 5:33 pm

Hmm, what I don't yet have is a canonicalisation function for 9x9 Latin Squares.

On that subject, it seems that the correct value for the number of ED Latin Squares (9x9) is actually 115,618,721,533. That's the value given in the "isotopy classes" table of the Wiki page.

A far less daunting number ... that's only ~21 times the number of ED Sudoku grids.

It makes sense - there are only 3,359,232 ways to transform a Sudoku grid, but there are 9! x 9! ways to transform a Latin Square. That's 362,880 ^ 2 = 131,681,894,400 members in each isotopy class (minus the occasional automorphism) ...

On the debit side, the CF function for Latin Squares is likely to be far more expensive than its Sudoku cousin ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1482
Joined: 27 May 2015
Location: Canberra

Re: Latin Squares and Latin Square puzzles

Postby tarek » Wed Nov 27, 2019 6:37 pm

Mathimagics wrote:Tarek, can you post those 22-clue examples?

I'm away from those now but will post in 12 hours
User avatar
tarek
 
Posts: 3416
Joined: 05 January 2006

Next

Return to Sudoku variants