LatinExplainer - to solve and rate 9x9 latin squares

Programs which generate, solve, and analyze Sudoku puzzles

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Fri Nov 22, 2019 3:07 pm

Are there puzzles that are both minimal Sudoku and minimal LS?

Yes!

These minimal 38-clue Sudoku puzzles (from Mladen's stockpile) are also minimal LS puzzles:
Code: Select all
..345.789..........8923754..3.76.894..6........834267....62..57....734.8...5.496.
...4....945..8.23.6892.3.54.....7...79....325865..2.97.76......5.8..4.6294....573
...4....945..8.23.6892.3.54.....7...79....523865..2.97.76......5.8..4.6294....375
.2345.789457..923....2.3....3654.897.7539.46...4.......62...9.8......67.7.8....2.
....5....45.1..2.66.9..21.524.8..3.139..148.28..2.3...53.9..61...8.....396.3.15.8
1.3...78..57...2.669.....15.........3798..5.151.9.387276.3..128...6.....931..86.7
...4.6...45718....69..731........4..84.3679..97584.....8.....1.5.971...371.63859.
.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
....56......1.9.36...3...152.967.143..493..677...1......27...5..4529..7197.56..24
...4....945..8.23.8692.3.54.....7...685..2.9779....523.76......5.8..4.6294....375
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.24.83.97..3.9.48..89..7234...........1.....9.9.2...13.
12.4.678.4..18..6.68..2741.29.87.34..3.9.48..84..3297..1.....9..........96....1.7
.......89457.89..3.8937245..75.4139...4.......9172354.....17...7.2..8....1823....
.......89457.89..3.8972345..75.4139...4.......9137254.....17...7.2..8....1823....
.........457.892...897324.5.948.1...5.827....71..93.........1..845.17..2.713285..
..345.789.5.......8..2375.4....648.5...52..76...7.349...267.948..6........83426.7
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby tarek » Fri Nov 22, 2019 5:48 pm

Any Sudoku Puzzle that will solve with techniques that do not depend on Box constraints will obviously be Latin square …

I can have a go with a sweep on the PG games which by default are minimal puzzles

By the way who decided that Latin square is (LS) when I think that for years it was either (Q), (LQ) or (QWH) ?

I think it stemmed from it being referred to as Qwasi-group With Holes!

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

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby coloin » Fri Nov 22, 2019 9:31 pm

That was easy .... so we have 20 clue minimal and now 38 clue minimal LSQ [!} puzzles, Maybe with a bit more looking there would be a 39
Here is a 20
Code: Select all
 1 3 2 4 . . . . .
 3 2 4 . . . . . .
 2 4 . . . . . . .
 4 . . . . . . . .
 . . . . . . . . .
 . . . . . . . . 5
 . . . . . . . 5 7
 . . . . . . 5 7 6
 . . . . . 5 7 6 8

from qiuyanzhe's theorm here this is easily made ... but it is not proven that this is the miniumum
Code: Select all
+---+---+---+
|123|4..|...|
|4..|...|...|
|...|...|.56|
+---+---+---+
|234|...|...|
|...|...|...|
|...|...|567|
+---+---+---+
|34.|...|...|
|...|...|..5|
|...|..5|678|
+---+---+---+  valid 9*9 puzzle with 20C - and is also a valid LSQ puzzle

Maybe a search through 19C will provide us with one !

Overall there are more Essentially Different LSQ grid solutions [3.77e17 according to sudopedia *] .... and probably more minimal puzzles per grid solution

Thinking about my theory of hard 9*9 puzzles having more LSQ grid solutions
potentially the existance of many valid LSQ solution in a 9*9 puzzle may indicate that there are longer chains leading to a terminal B/R/C constraint

The number of clues in a minimal 9*9 will also have a bearing ...and thinking about it some more ....
The 9*9 has 3 constraints ....
LSQ has only 2, namely the row and column constraints without the box constraint.
and there are two other complimentary variations, namely the Box/Row an Box/Column varients which are essentially similar.

[*] 5,524,751,496,156,892,842,531,225,600 /(9! x 8!) = 377,597,570,964,258,816 [? correct]
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Sat Nov 23, 2019 3:15 am

tarek wrote:By the way who decided that Latin square is (LS) when I think that for years it was either (Q), (LQ) or (QWH) ? I think it stemmed from it being referred to as Qwasi-group With Holes!

Thanks heavens for progress, then! Latin Squares are an established area of mathematical study, where "minimal puzzles" on a Latin Square are called critical sets.

The connection with quasigroups is simply that the "group multiplication" table for any finite quasigroup happens to form a Latin Square.

tarek wrote:I can have a go with a sweep on the PG games which by default are minimal puzzles.

My hunch is that this phenomenon (minimal Sudoku and minimal LS) will only occur at the higher end of the clue count scale. The less clues you have, the greater the probability that you are exploiting the box constraints. That's why I looked in Mladen's high-clue sets first.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby tarek » Sat Nov 23, 2019 3:31 am

Mathimagics wrote:
tarek wrote:I can have a go with a sweep on the PG games which by default are minimal puzzles.

My hunch is that this phenomenon (minimal Sudoku and minimal LS) will only occur at the higher end of the clue count scale. The less clues you have, the greater the probability that you are exploiting the box constraints. That's why I looked in Mladen's high-clue sets first.
Correct! I did a sweep on Champagne's 3,000,000+ list of hardest puzzles. None were solvable with Latin Squares constraints :cry: .

On a brighter note, Sukaku explainer v1.11.1 is available to download with ability to transform into a (Sukaku) Latin Square solver from the new "Variants" menu. Select Latin Square from that menu to use the GUI as a Latin square Solver and de-select it again to revert to Sudoku mode. From the command line menu the new option would be -Q0 to use as Latin square solver.

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

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Sat Nov 23, 2019 3:42 am

coloin wrote:5,524,751,496,156,892,842,531,225,600 / (9! x 8!) = 377,597,570,964,258,816 [? correct]

Yes, correct.

I hadn't spotted your 20C construction:

Code: Select all
1234.....4...............56234.....................56734...............5.....5678


Excellent work! This is indeed a minimal puzzle for both Sudoku and Latin Square. Give that man a cigar! 8-)

It might not be worthwhile trawling through any sets of 19C puzzles, as they might not even contain any valid LS puzzles. I have seen no evidence in the literature that a 19-clue LS puzzle exists. But then again, nobody has proved (AFAIK) that 20 is the lowest possible ...

Surely these examples will be of interest to 1to9only, they allow a direct comparison of the same puzzle with both LS- and S- Explainers ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby tarek » Sat Nov 23, 2019 10:40 am

ALS - Wings are not as common with Latin squares

Code: Select all
+-------------+-------------+-------------+
| 14  14  7     8   5   6     9   2   3   |
| 6   5   8     7   3   49    1   49  2   |
| 27  29  5     3   8   79    4   6   1   |
| 8   6   3     9   1   2     5   7   4   |
| 47  3   6     1   9   457   2   45  8   |
| 9   7   4     6   2   1     8   3   5   |
| 3   124 *12   5   6   8     7  4-1  9   |
| 12  8  %29    4   7  %59    3  %159 6   |
| 5   19  19    2   4   3     6   8   7   |
+-------------+-------------+-------------+
WXYZ wing *%:(159)  r7c8<>1


Code: Select all
+-------------+-------------+-------------+
| 15  8   3     7   9   15    2   4   6   |
|%357 6   9     1   2  %35    47 %58 %48  |
| 8   2   4     69  1   7     3   69  5   |
| 2   1   67    3   4   9     5   68  78  |
| 9   34  25    24  35  8     6   7   1   |
| 137 34  257   8   56  16    47  25  9   |
| 4   7   8     5   36  36    9   1   2   |
|5-7  9   567   46  8   2     1   3  *47  |
| 6   5   1     29  7   4     8   29  3   |
+-------------+-------------+-------------+
VWXYZ wing *%:(3457) r9c1<>7
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby coloin » Sat Nov 23, 2019 10:53 am

Mathimagics wrote: Excellent work

Thanks for the cigar ! But no work by me really !
The first puzzle was one published by you and morphed by qiuyanzhe
The second one - was a comeplete fluke that I constructed it back in April using qiuyanzhe's method and it just happend to be a LSQ when I looked at how it solved
tarek wrote:Any Sudoku Puzzle that will solve with techniques that do not depend on Box constraints will obviously be Latin Square …

This is exactly what went on fortuitously and i was able to check it with the LatinExplainer !
So any 9*9[3*3] puzzle which solves somehow without using box constraints will be a 9*9 LSQ
Last edited by coloin on Sat Nov 23, 2019 1:32 pm, edited 1 time in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby tarek » Sat Nov 23, 2019 1:24 pm

Code: Select all
+----------------+----------------+----------------+
| 7    3    2      18   9    4      168  5    16   |
| 34   8    469   %39   1    2     67-9  79   5    |
| 28   49   5      28   6    1      3    49   7    |
| 14   69   469    19   3    7      5    2    8    |
| 5    1    7      6    8    9      4    3    2    |
| 6    7    1     *23   5    38    ^29   489  49   |
| 23   59   8      4    7    35     129  6    19   |
| 9    456  3      7    2    568    68   1    46   |
| 18   2    69     5    4    68     1678 789  3    |
+----------------+----------------+----------------+
XY wing %*^:(239) r2c7<>9
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Sat Nov 23, 2019 2:54 pm

coloin wrote:The second one - was a complete fluke that I constructed back in April using qiuyanzhe's method and it just happend to be a LSQ when I looked at how it solved

Ok, but by doing that you have demonstrated that the "minimal Sudoku + minimal LS" phenomenon can indeed occur at the lower-end of the clue-count scale. So you get to keep the cigar!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby tarek » Sat Nov 23, 2019 3:31 pm

Mathimagics wrote:
coloin wrote:The second one - was a complete fluke that I constructed back in April using qiuyanzhe's method and it just happend to be a LSQ when I looked at how it solved

Ok, but by doing that you have demonstrated that the "minimal Sudoku + minimal LS" phenomenon can indeed occur at the lower-end of the clue-count scale. So you get to keep the cigar!

The search from Latin square to Sudoku would be easier. Find a low clue minimal Latin square then scan if sudoku then scan if minimal.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby 1to9only » Sat Nov 23, 2019 3:49 pm

I scanned the submissions for pattern games 1 to 365 inclusive, and the number that are also latin square puzzles is: ZERO.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Sat Nov 23, 2019 4:46 pm

tarek wrote:The search from Latin square to Sudoku would be easier. Find a low clue minimal Latin square then scan if sudoku then scan if minimal.

I assume that you really meant "start with a Sudoku grid", then find minimal LS puzzles, checking these for being minimal Sudoku puzzles. They will of course all be valid Sudoku puzzles, just not necessarily minimal.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

One in a million

Postby 1to9only » Sat Nov 23, 2019 5:24 pm

I had LE generate over 1m grids (some are in post #2), I've scanned these and found only 1 which is aslo a sudoku grid with a unique solution, but it's not minimal.
Code: Select all
.8374.....7.5....4.9..31.5.8...9.3657.5...2....63........8.35.626..7..4....1.482. ED=7.2/1.5/1.5 latin square
.8374.....7.5....4.9..31.5.8...9.3657.5...2....63........8.35.626..7..4....1.482. ED=1.2/1.2/1.2 sudoku

So finding minimal LS from mininal sudokus (or the other way round), the pickings are thin.
User avatar
1to9only
 
Posts: 4175
Joined: 04 April 2018

Re: LatinExplainer - to solve and rate 9x9 latin squares

Postby Mathimagics » Sat Nov 23, 2019 5:35 pm

1to9only wrote:So finding minimal LS from mininal sudokus (or the other way round), the pickings are thin.

I tend to agree, although perhaps there are considerably more for high-clue minimal Sudokus ...

For low-clue puzzles, there is indeed something special about our 20-clue example grid:
Code: Select all
1234.....4...............56234.....................56734...............5.....5678
123456789456789123789123456234567891567891234891234567345678912678912345912345678


First, there are many more 20C minimal Sudoku/LS puzzles on the same grid. Here are some:
Minimal LS 20C: Show
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
.2......9...7.....7..1.3.5....5.7....6..9.2.4.9........4....9.2............3.5.7.
.2.4.6.8.......1.3.8...............1.6.8.......1.3.5.7.4.6.8.......1.3.5.........
.23..67..4...8.........3....3...7...5..89...48..................7...23..9...4...8
12.....89..67......8.........4567.....7......89.........567.............91......8
.234..............7......56.34......5........8.....567.4.......6.......5.1234....
.........4...8...3..91...5....5...9.........48...34..7..56..91....9.........4...8
.2.4.6.......8.1.3...............8.1.6........9.2.4.6..4.6.......8.1.3.5........8
1.3.5..............8....4.6......8...6.8..2.4..1.3....3.5.7..1.....1..........6.8
.2...6...4..78...37..................6...12..8...3...73...7.........2....12..56..
1....6....5........89...45.2...67..1.....1....9....5...45...9..6...12............
.2....7....6........91...5623...78........2....1....6...56...1..7...23...........
..........5....1.37.9.2.....3.5..8.1..7.9..........5......7..........3.59.2.4..7.
.......8....7....3.89...45...4...89.............23...73..67...2..8....4....3.....
.....678945...............62345.....5...............67345.....................678
.23...78.4....9....8........3....8..5...91..4.....4.............78...3..9...45...
.............8.1.37.9....5..3..6.8.15.7..........3......5..........1.3..9.2..5.7.
..........5.7.9.......2.4.6.3.5.7.9.......2.4.9...............2.7.9.......2.4.6.8
1.3.5.7........1...8......6..........6.8....4..1.3.5...4.6.8..2....1.3..........8
..3......45.........9123............56......4..123.....4.......67.....45..23.....
.........4......23.891.....2........5.....234.91......3.......2.7891.....1.......
...4..........9.2..8.1..4.62....7.9..6.8....4..........4.6..........2...9.2..5.7.
.2...67..4...8...3..............7....67..12..8...3....3.........7...2...9..34...8
...4....9.56...12........5.............89...4..1...56...5....1....9.....9..34...8
...4.6....5..8.1.3.8........3....8.1............2.4.6....6.....6..9.2.4..1......8
1.......9.5678.....8.......2......91.678..............3.....912.78......9........
...4.........8...3..91..45...45...9..........8...3...73...78..2...9...4.........8
.....6......78.........3456...........789.........456.....7.....7891.........56..
.........4.6....2..8.1.3...2.4.6..9....8.1..........6......8...6......4..1.3.5..8
.2.......4.......3.8912.............5......34.912.....3........6.....345.12......
.23...78........2....1....6...56...1..7...23.............6.....6..91...5..2....7.
.......8....7....3.89...45...4...89.............23...73..67...2..8....4....3.....
........9......12.789.....6..............123.89......7.......1.....1234.9.......8
...45...9..6...12.............5.....5..89...4..1....6........1....9....5.12...67.
..34...8..5...91.............4........78...34.9....5........9....8....4.91...56..
.....6.8.4........7.9.2.4..2.4.......6.8.1.3........6....6.8.1..........9.2.4....
..3....8....7.....7..12...6.34...89........3....2....7...67...2..8...34..........
.2.4....9..6.8.1...............6.8..........4.9.2.4..7.4......26.8.1.3........6..


If we look at the solution grid:
Code: Select all
 +-------+-------+-------+
 | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 6 | 7 8 9 | 1 2 3 |
 | 7 8 9 | 1 2 3 | 4 5 6 |
 +-------+-------+-------+
 | 2 3 4 | 5 6 7 | 8 9 1 |
 | 5 6 7 | 8 9 1 | 2 3 4 |
 | 8 9 1 | 2 3 4 | 5 6 7 |
 +-------+-------+-------+
 | 3 4 5 | 6 7 8 | 9 1 2 |
 | 6 7 8 | 9 1 2 | 3 4 5 |
 | 9 1 2 | 3 4 5 | 6 7 8 |
 +-------+-------+-------+

then we realise that it is rather special, each row being a cyclic shift of the first. The 9 possible results are then ordered in such a way as to form a valid Sudoku grid, as Colin did.

The fact that I having a great deal of trouble finding any other Sudoku grid with a low-clue minimal LS puzzle is perhaps evidence that these are very rare. For 20-clues in particular perhaps this is the only grid?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Software