The New Sudoku Players' Forum

[Mathimagics]

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


[tarek]

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

[coloin]

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]

[Mathimagics]

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.

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.

[tarek]

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 .

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

[Mathimagics]

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!

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

[tarek]

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

[coloin]

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

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

[tarek]

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

[Mathimagics]

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!

[tarek]

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.

[1to9only]

I scanned the submissions for pattern games 1 to 365 inclusive, and the number that are also latin square puzzles is: ZERO.

[Mathimagics]

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.

[1to9only]

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.

[Mathimagics]

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?