The New Sudoku Players' Forum

[Mathimagics]

BTW, I have confirmed the existence of 12-clue PD13's - see here.

Correction! The puzzles reported were NOT 12-clues, only 13.

creint had identified the first 13-clue puzzle, which he had proven to be valid, but he abandoned the clue-by-clue minimality testing halfway through, as each clue took many hours to check. All I did was to confirm the minimality of that puzzle.

The root cause of the confusion was a bug in my minimality tester, which has now been fixed, and has found lots (over 50) of 12-clue puzzles on that same grid. A few examples:

Code: Select all

.....9......3..............4..............................5..2...8....B....1..........................D......7....6..............A.......................................
..........................A................................31.........B................D...........................2................5.........84..C6......9..............
..........................A................................31.........B..4..........6.9............................2...D......................8...C...5..................


[Mathimagics]

For N=13, we can make an extremely fast solver using pattern matching.

Given any puzzle P:

• set C = {clue value list}, and set C* = Norm(C), so C* is the normalised value list (minlex)

• for each known solution grid G, set S = {clue value list}, ie the set of values in the cells fixed by P

• if Norm(S) = C*, bingo!!

As an example, this puzzle has 13 clues, 2271 solutions. DLX takes about 24 hours (!) to find them all. Pattern-matching finds them in 15 milliseconds ...

So finding minimal puzzles is much easier, now, as you can imagine!

The method exploits the unique property of the VPT group, ie the known grid list is self-mapping under all transformations.

[creint]

Can you explain the algorithm it more?
Will this work for every puzzle?

[999_Springs]

creint, i think he generates all possible solution grids, and sees if the clues in the puzzle match up with the digits in the same position in each of the solution grids (up to relabelling the digits)

this only works because there are a small enough number of solution grids in the 13x13 case

[Mathimagics]

Will this work for every puzzle?

Yes. The matching is valid for any puzzle where the givens include at least N-1 distinct values. And we know that any puzzle with less than N-1 distinct clue values must have multiple solutions.

Say we have this puzzle P:

Code: Select all

 . . . . . 9 . . . C D . .
 . . . 2 . . . . . . . . .
 A . 8 . . 5 . . . 9 . . .
 . . . . . . . 2 . . . . .
 . A . . . . . . 1 . . . .
 . . . . . . . . . 3 . . .
 . . . 4 . . . . . . . . 1
 . . . . . . . . . . C D .
 3 . . . 9 . . . . . . . .
 . . D . . . . . . . . . .
 . 6 . . . . . . . . . . .
 . . A . 6 . . . . . . . .
 . . . . . . B . . 5 7 . .


The clue-value list, and its normalised form is:

Code: Select all

 C  = {9,C,D,2,A,8,5,9,2,A,1,3,4,1,C,D,3,9,D,6,A,6,B,5,7}
 C* = {1,2,3,4,5,6,7,1,4,5,8,9,A,8,2,3,9,1,3,B,5,B,C,7,D}

Normalising a value list is just mapping the values according to the order in which they appear in the original list. It's effectively the value list in minlex form.

Now consider this grid, one of the 12,836 in the ED catalog:

Code: Select all

123456789ABCDCD123456789AB754D1C3BA628986AC9B1234D75379BA8CD125464B6829A75D13CA325D7846BC9121D74563C9AB8DC516349B782A94B3C12A856D768C9BAD123754597A82BCD1463BA867D954C312

The clue-value list for the puzzle pattern in P is:

Code: Select all

 S  = {6,A,B,2,7,4,C,6,2,7,1,D,5,1,A,B,D,6,B,8,7,8,9,C,3}
 S* = {1,2,3,4,5,6,7,1,4,5,8,9,A,8,2,3,9,1,3,B,5,B,C,7,D}


Bingo! S* = C*, so this grid is a solution.

It is a simple matter to map this back so that it matches the original puzzle, if you need to.

You will need a copy of the ED grid list. It's too large to attach (0.84MB zipped) , so PM me with an email address and I'll send it to you.

[Mathimagics]

this only works because there are a small enough number of solution grids in the 13x13 case

We might be able to extend to N=17, 19 ... we can make a "generating set" that might be small enough to fit into memory, then use transforms on the fly to generate the grids. These N sizes are almost certainly beyond the pale for conventional solvers ...

[denis_berthier]

Comes this Naked Triplet:

Code: Select all

3.6, Naked Triplet: Cells R1C7,R2C6,R7C1: 2,3,7 in diagonal(/): -37r6c2, -27r3c5, -37r5c3, -7r4c4


Note: Only main diagonals shown, as I've not changed the code for X much

I now have some Subsets and I find the same NT:

Code: Select all

naked-triplets-in-a-diagonal: d7{a2 a5 a7}{n7 n2 n3} ==> d7a4 ≠ 7, d7a4 ≠ 3, d7a6 ≠ 7, d7a6 ≠ 3, d7a1 ≠ 7, d7a3 ≠ 7, d7a3 ≠ 2

I currently use the diagonal coordinate system for such patterns; but this can change.

[Mathimagics]

.
Some more fun facts about N=13, and minimal puzzles:

• most grids seem to have 12-clue puzzles, and they tend to have have hundreds of them. A notable exception is the cyclic grids (there are only 10), none of which seem to have 12-clue puzzles, they seem to require 13 clues

• the smallest size for a UA is 26 cells. This is the smallest possible difference between any 2 solutions, corresponding to the relabelling that swaps two values.

• a typical non-trivial UA for a grid has size ~100. They are quite hard to find. Most attempts to find them, by removing clues until the first multiple solution occurs, typically with a value-deficient puzzle (less than 12 different values) which simply leads to a UA26, all of which are known anyway

The high numbers of 12-clue puzzles makes me wonder whether they might be easily enumerated (perhaps using hitting sets?). Maybe they can even be generated. I'm building a collection and trying to find some common attributes.

[Serg]

Hi, Mathimagics!

DLX was used to enumerate all sets of 13 mutually disjoint templates, and this process identified 12,386 cases.

I overlooked an important implication of this result.

Enumerating solution grids using this method (disjoint templates) in most cases does NOT enumerate the essentially different grids. It enumerates all the different possible solution grids (up to relabelling).

To obtain a catalog of the ED grids, we would typically have to apply all of the VPT's to each solution grid, obtain a canonical form in each case, then sort the results so we can remove duplicates (grid automorphisms) ...

I went through this process for SudokuP.

So, I was embarrassed not to realise, before now, that the pandiagonal solution space is quite unique: the possible grids and the ED grids are the same set ...

Yes, the method of combining all possible 1-templates gives all the different solution grids (up to relabelling). I went this way too and gave 12,386 different solution grids for 13x13 PLSs (Pandiagonal Latin Squares). But I think most of them are not essentially different. Maybe "cyclic" PLSs (10 grids) are really essentially different, but most (or all) others aren't. Consider, for example, PLS "A":

Code: Select all

            A

1 2 3 4 5 6 7 8 9 A B C D
8 C 1 2 3 4 5 B 6 D 9 A 7
5 B 9 D 1 2 6 4 A 3 7 8 C
9 4 A B C D 1 3 7 8 5 6 2
6 7 8 9 A B C D 1 2 3 4 5
4 D 6 3 7 8 A 5 C 9 1 2 B
A 3 7 8 6 5 2 9 4 B C D 1
D 1 C 5 2 9 4 7 8 6 A B 3
C 5 2 1 4 3 B 6 D 7 8 9 A
2 9 4 C B 1 D A 3 5 6 7 8
7 8 B 6 D A 3 1 2 C 4 5 9
B 6 D A 9 7 8 C 5 1 2 3 4
3 A 5 7 8 C 9 2 B 4 D 1 6

Let's apply to it VPT "cyclic shift of columns from right fo left" and relabel it to restore right order of the first row. We'll get PLS "B":

Code: Select all

            B

1 2 3 4 5 6 7 8 9 A B C D
B D 1 2 3 4 A 5 C 8 9 6 7
A 8 C D 1 5 3 9 2 6 7 B 4
3 9 A B C D 2 6 7 4 5 1 8
6 7 8 9 A B C D 1 2 3 4 5
C 5 2 6 7 9 4 B 8 D 1 A 3
2 6 7 5 4 1 8 3 A B C D 9
D B 4 1 8 3 6 7 5 9 A 2 C
4 1 D 3 2 A 5 C 6 7 8 9 B
8 3 B A D C 9 2 4 5 6 7 1
7 A 5 C 9 2 D 1 B 3 4 8 6
5 C 9 8 6 7 B 4 D 1 2 3 A
9 4 6 7 B 8 1 A 3 C D 5 2

PLS "B" differs from PLS "A". Both PLSs are equivalent because "B" was produced from "A" by appling VPT. But both PLSs are in 12,386 solution grids list. So, there should be less than 12386 ED PLS. At the moment I don't know exact value of ED 13x13 PLS.

Serg

[Mathimagics]

Hi Serg

Yes, you are right. So the transformations that I called VPT's are really solution-mapping transforms (SMT?), and the VPT's would be the subgroup corresponding to the type G (geometric ) and type T (translation) transformations.

So the VPT generators are just {transpose, rotate, cyclic-shift rows, cyclic-shift columns}.

The VPT group for N=13 now has just 1352 transformations, in 44 conjugacy classes.

The number of ED grids is 47, by my reckoning, and 3 of them are cyclic. Hopefully you will arrive at the same figure!

Cheers
MM

PS: based on this VPT group, and assuming the ED count is 47, the revised automorphism table is:

Code: Select all

  nAut   Grids
  ------------
     1       2
     2      12
    26      30
   338       2  *
   676       1  *
  ------------
            47

* = cyclic grid


[denis_berthier]

For N = 11, there are only 8 ED grids, and these are all cyclic wrt both rows and columns. Knowing this property, the solver can exploit this property to great advantage, making for very easy puzzles ...
But I can probably produce some N=11 puzzles for you, if you like?

No, thanks. If they are so easy to solve, it's not very interesting from a solver's POV. I said 11 because I didn't know it would be so easy.

Hi Mathimagics,
I have coded all the Naked, Hidden and Super-Hidden (Fish) Subsets that don't mix rows/columns/diags/anti-diags, neither in their base sets nor in their cover sets - those that mix them could be considered as exotic Fish. Coding these Subsets is easy with any text editor, by partly replacing words row and column in Subsets for normal Latin Squares, by any combination of two words among: row, column diagonal, anti-diagonal.
Even so, that leaves 12 types of Subsets for each size.
Unfortunately, experimenting this with N=13 quickly leads to combinatorial explosion for Subsets of size 4. The return on investment for Subsets is generally very low, but this is particularly noticeable with large Pandiags.

The case N=11 may be trivial if one uses the result that there are only 8 ED grids, but it remains an interesting test case for a solver that doesn't use it.

So, if your proposal to generate 11x11 puzzles (not solvable by Singles only) still holds, I'm now interested. it could be a way of finding more easily various types of Subsets.
The case N=7 might be interesting also, in the same conditions.

[Mathimagics]

So, if your proposal to generate 11x11 puzzles (not solvable by Singles only) still holds, I'm now interested. it could be a way of finding more easily various types of Subsets. The case N=7 might be interesting also, in the same conditions.

These are all minimal

Non-stte, Minimal, N = 7: Show

Code: Select all

.............4........5....1........67.2.........
.............4........5....1..2.....67...........
.............4........5....17.......6..2.........
.............4........5....17.2.....6............
.............4........5..6.1.........7.2.........
.............4........5..6.1..2......7...........
.............4........5..6.17..........2.........
....4....................6................53..7.2
....4....................6....2...........53..7..
....4.........3..........6................5...7.2
....4.........3..........6....2...........5...7..
...34....................6................5...7.2
...34....................6....2...........5...7..
.25............4.........6.1....3................
.25............4..1......6......3................
.253...........4.........6.1.....................
.253...........4..1......6.......................
125............4.........6......3................
1253...........4.........6.......................


Non-stte, Minimal, N = 11: Show

Code: Select all

....9...........................................2............................8....4..............7......1.3.....6...AB...
....9...........................................2............................8....4.........3....7......1.......6...AB...
....9...........................................2............................8....4....1.........7........3.....6...AB...
....9...........................................2............................8....4....1....3....7..............6...AB...
....9...........................................2............................8...64..............7......1.3.........AB...
....9...........................................2............................8...64.........3....7......1...........AB...
....9...........................................2............................8...64....1.........7........3.........AB...
....9...........................................2............................8...64....1....3....7..................AB...
....9...........................................2.........................8.......4..............7......1.3.....6...AB...
....9...........................................2.........................8.......4.........3....7......1.......6...AB...
....9...........................................2.........................8.......4....1.........7........3.....6...AB...
....9...........................................2.........................8.......4....1....3....7..............6...AB...
......4.............................................75...................1...8...........B...29.......A.................3
......4.............................................75.........9.........1...8...........B...2........A.................3
......4.............................................75.....1.................8...........B...29.......A.................3
......4.............................................75.....1...9.............8...........B...2........A.................3
......4.............................................75....B..............1...8...............29.......A.................3
......4.............................................75....B....9.........1...8...............2........A.................3
......4.............................................75....B1.................8...............29.......A.................3
......4.............................................75....B1...9.............8...............2........A.................3
......4......................................1......75.......................8...........B...29.......A.................3
......4......................................1......75.........9.............8...........B...2........A.................3
......4......................................1......75....B..................8...............29.......A.................3
......4......................................1......75....B....9.............8...............2........A.................3
......4.........................9...................75...................1...8...........B...2........A.................3
......4.........................9...................75.....1.................8...........B...2........A.................3
......4.........................9...................75....B..............1...8...............2........A.................3


[denis_berthier]

Each of these were found by randomly removing clues from a full solution until the first non-stte case found:

Too easy. Half of them can be solved by Singles, the rest by whips[1].
Would it be computationally too hard to generate minimal puzzles?

[Mathimagics]

I have updated the list above for N=7.

N=11 will take longer, I have to use DLX as I only built the matching-pattern solver for N=13. Finding minimal puzzles hammers the solver ... and N=11 is where it starts to hurt ...

Ok, they are in place now ...

[Mathimagics]

Hi Serg,

So the transformations that I called VPT's are really solution-mapping transforms (SMT?), and the VPT's would be the subgroup corresponding to the type G (geometric ) and type T (translation) transformations.

Another elementary blunder on my part, I'm afraid ...

The original VPT set (16224 VPT's) is the correct one, of course.

With that group, we find that the 12386 different solution grids boil down to just 10 ED grids.

Hidden Text: Show

Code: Select all

123456789ABCD3412785ACD96B8BA3124756CD9798BACD6435126A5CDB93124785CD6938BA7124D67541298BA3C9341276CD58BAB12784A56CD9328BA35CD79641CD98BA3124756A5CD69B4312874769CD12B83A5
123456789ABCD34128BCA7D956267DCA8B54139A8C6BD9213547C7A9351D426B8BD451936C782A95B342A786CD1D128674CAB3954C6728B5D9A13638CA1D9B54727A9BDC51382645BDA93642178C895174236CDAB
123456789ABCD3416D9BA2C578DC258749316BA2A9C6B1D48357985A7C231D46B73D1BA8C56294B1634257D9A8C5D48936BA7C21C67D24958B1A385B9A1C673D4267A2C8D1B4935ABC71534628D9498B3DA2C5716
123456789ABCD3456789ABCD1256789ABCD1234789ABCD1234569ABCD12345678BCD123456789AD123456789ABC23456789ABCD1456789ABCD1236789ABCD1234589ABCD1234567ABCD123456789CD123456789AB
123456789ABCD3456789ABCD1256789ABCD1234789ABCD123456CD123456789ABABCD123456789D123456789ABC6789ABCD12345456789ABCD12323456789ABCD189ABCD1234567BCD123456789A9ABCD12345678
123456789ABCD3456789ABCD1256789ABCD1234ABCD12345678989ABCD1234567D123456789ABC456789ABCD123CD123456789AB789ABCD12345623456789ABCD16789ABCD12345BCD123456789A9ABCD12345678
123456789ABCD3456789ABCD126789ABCD123459ABCD12345678BCD123456789A23456789ABCD156789ABCD1234CD123456789AB89ABCD1234567456789ABCD123D123456789ABC789ABCD123456ABCD123456789
123456789ABCD3456789ABCD1289ABCD1234567CD123456789AB789ABCD12345623456789ABCD1ABCD12345678956789ABCD1234D123456789ABC456789ABCD1239ABCD12345678BCD123456789A6789ABCD12345
123456789ABCD3456789ABCD129ABCD1234567823456789ABCD189ABCD1234567ABCD123456789456789ABCD123D123456789ABC56789ABCD1234CD123456789AB6789ABCD12345BCD123456789A789ABCD123456
123456789ABCD6789ABCD12345BCD123456789A3456789ABCD1289ABCD1234567D123456789ABC56789ABCD1234ABCD12345678923456789ABCD1789ABCD123456CD123456789AB456789ABCD1239ABCD12345678

I double-checked this by applying the VPT's to the 10 ED grids and this generated the full set of 12386 solution grids.