The New Sudoku Players' Forum

[1to9only]

Here are some PD11 grids:

Code: Select all

......A.........8................2............7....5.69................3........................4.1......3....6..........  12 ED=8.0/7.7/2.9
..5.............8............2.......................6.......74.....1.........AB..........3...................6.......8..  12 ED=8.0/2.9/2.9
...6.7.........2..........1.......9...4....86.....5....3..................A....................2.........................  12 ED=7.9/7.9/2.9
..........3..7...........................8...........A...........2..8...B...1...A.4....6.................6..9............  13 ED=7.8/7.8/2.9
....7....................B.......A................8.................8...............31..9............2.........3..6....B4  13 ED=7.8/7.8/2.9
.........................A..4.....1.............2......5.................9A.......2....6.5...................B....7.....3  13 ED=7.8/7.8/2.9
..........2.......3....................9....A......5.......A...........3.......B...1.......6........4.....6.......7......  13 ED=7.8/7.7/7.7
...8........................3.................3...................5..........87.......5.......1....B42...6..9............  13 ED=7.8/7.7/2.9
.........A........9...................7..B.........4....5.......6.........83....9...............4.......1..........5.....  13 ED=7.8/7.6/2.9
.................................93...B..7.......8...A..............2..6..3.......................4.........214..........  13 ED=7.8/7.6/2.9
..........2..63.......5....7............5...A...B......B.1..........9....................1...........................8...  13 ED=7.8/7.6/2.9
1....3...B..........4..5.......2........6..8..........7....7.............2.............A..................8..............  13 ED=7.8/7.6/2.9
..5.......2B.........A.69.......5................185............................7......6............4....................  13 ED=7.8/2.9/2.9
......A........1...6.....A...................................7.........3................8.........1.42.......B.9........3  13 ED=7.7/7.7/2.9
.......3..2..6.5................3....................8.....7...................5...4..9..1........B........1.............  13 ED=7.7/7.6/2.9


I think they all have unique solutions, but many may not be minimal, as I Ctrl-C the program when it takes too long to validate the grids with low number of clues.
Also, SE finds no basic fish.

[Mathimagics]

I think they all have unique solutions, but many may not be minimal ...

They are all valid. None are minimal.

There is mounting evidence (here) that suggests, for the all-cyclic cases (N < 13 in particular), a puzzle can't have more than N clues and be minimal.

The first grid has 4 redundant clues.

Minimal test log puzzle #1: Show

Code: Select all

PT="......A.........8................2............7....5.69................3........................4.1......3....6..........
testminimal11 pt

05:48:45 Base puzzle valid (12c)
05:48:45   .  clue( 5,10) = 6:  (R)
05:48:45   .  clue( 7, 6) = 3:  (R)
05:48:45   .  clue(10, 7) = 3:  (R)
05:48:45   .  clue(11, 1) = 6:  (R)
05:48:45 <done> removable Clues = 4


You can remove either of the "3"'s and either of the "6"'s ... giving a 10-clue puzzle:

Code: Select all

......A.........8................2............7....5..9................3........................4.1...........6..........

[Serg]

Hi, Mathimagics!

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

I confirm the 13 x 13 PLSs you posted are essentially different. (Two of them are cyclic PLS.)
But at the moment I don't know exact order of VPT group. This is my version of generators for VPT group.

Code: Select all

1. Cyclical shift of columns from left to right: (R,C) --> (R,C+1(mod 13))
2. Cyclical shift of rows from top to bottom:    (R,C) --> (R+1(mod 13),C)
3. Horizontal reflection:                        (R,C) --> (12-R,C)
4. "H transformation":                           (R,C) --> (R+C(mod 13),C-R+13(mod 13))
5. Multiplication                                (R,C) --> (2R(mod 13),2C(mod 13))
6. Multiplication                                (R,C) --> (3R(mod 13),3C(mod 13))
7. Multiplication                                (R,C) --> (5R(mod 13),5C(mod 13))
8. Multiplication                                (R,C) --> (7R(mod 13),7C(mod 13))
9. Multiplication                                (R,C) --> (11R(mod 13),11C(mod 13))

It looks like this list is minimal, i.e. no generator can be removed from the list.
You are familar with GAP. What is the order of the group generated by these transformations?

Serg

[denis_berthier]

Here are some PD11 grids:

Code: Select all

......A.........8................2............7....5.69................3........................4.1......3....6..........  12 ED=8.0/7.7/2.9
[...]

I think they all have unique solutions, but many may not be minimal, as I Ctrl-C the program when it takes too long to validate the grids with low number of clues.
Also, SE finds no basic fish.

They all are in W3 or W2 and I found no Fish either.

The first grid has 4 redundant clues.
[...]
You can remove either of the "3"'s and either of the "6"'s ... giving a 10-clue puzzle:

Code: Select all

......A.........8................2............7....5..9................3........................4.1...........6..........

The original puzzle is solved in W3.

Deleting only one clue at a time, we get 4 cases:

Code: Select all

......A.........8................2............7....5..9................3........................4.1......3....6.......... ; allows some whip eliminations, but not in T&E(1)
......A.........8................2............7....5.69................3........................4.1......3............... ; allows some whip eliminations, but not in T&E(1)
......A.........8................2............7....5.69.........................................4.1......3....6.......... ; allows some whip eliminations, but not in T&E(1)
......A.........8................2............7....5.69................3........................4.1...........6.......... ; allows some whip eliminations, but not in T&E(1)

Deleting 2 clues at a time, we get 4 more cases:

Code: Select all

......A.........8................2............7....5..9.........................................4.1......3....6.......... ; no whip elimination, not in T&E(1)
......A.........8................2............7....5..9................3........................4.1...........6.......... ; no whip elimination, not in T&E(1)
......A.........8................2............7....5.69.........................................4.1......3............... ; no whip elimination, not in T&E(1)
......A.........8................2............7....5.69................3........................4.1...................... ; no whip elimination, not in T&E(1)

1to9only, I think this explains why computation times explode when you try to eliminate more clues from the original puzzle.

For a puzzle, not being in T&E(1) means it is very unlikely a human player can solve it (except if there is some miraculous pattern to make it simpler).

This suggests that, when looking for interesting puzzles from a solving perspective (for which minimality is totally irrelevant), a better criterion for stopping the deletion of candidates in a top-down algorithm would be just before it puts the puzzle out of T&E(1). As checking membership in T&E(1) is fast - much faster than checking minimality - this should allow to produce interesting puzzles more easily.

[Mathimagics]

It looks like this list is minimal, i.e. no generator can be removed from the list.
You are familar with GAP. What is the order of the group generated by these transformations?

Hi Serg!,

The group order is 16224, and I can confirm that your minimal generator set is correct, well done!

The Atkin paper states that the group order (number of VPT's) is always 8 x Phi(N) x N^2, where Phi(N) is the Euler totient function, which for prime N is just (N-1).

So for prime N the number of VPT's is 8 x (N-1) x N^2

With N=13, |VPT| = 8 x 12 x 13^2 = 16224

[Mathimagics]

.
Here is what I hope is the final word on the ED grids for N = 13. There are 10, and they are listed below with a tag indicating their "degree of cyclitude" ( )

Ok, I made that word up! The tags are:

• C (cyclic) = cyclic 5 ways

• S (semi-cyclic) = cyclic 1 way

• A (acyclic) = cyclic in NO way

We now know that there are 5 senses (not 4) in which a grid can be deemed cyclic. The 4 obvious ones are wrt rows, columns, left-diagonals, right-diagonals.

The 5th sense I will leave as an exercise for now ... ( )

Can anybody (except Serg, who now knows what I know) work out what that is?

I will give one clue: the 2nd grid in this list is only cyclic in the 5th sense!

ED list: Show

Code: Select all

123456789ABCD3412785ACD96B8BA3124756CD9798BACD6435126A5CDB93124785CD6938BA7124D67541298BA3C9341276CD58BAB12784A56CD9328BA35CD79641CD98BA3124756A5CD69B4312874769CD12B83A5 # A
123456789ABCD34128BCA7D956267DCA8B54139A8C6BD9213547C7A9351D426B8BD451936C782A95B342A786CD1D128674CAB3954C6728B5D9A13638CA1D9B54727A9BDC51382645BDA93642178C895174236CDAB # S
123456789ABCD3416D9BA2C578DC258749316BA2A9C6B1D48357985A7C231D46B73D1BA8C56294B1634257D9A8C5D48936BA7C21C67D24958B1A385B9A1C673D4267A2C8D1B4935ABC71534628D9498B3DA2C5716 # A
123456789ABCD3456789ABCD1256789ABCD1234789ABCD1234569ABCD12345678BCD123456789AD123456789ABC23456789ABCD1456789ABCD1236789ABCD1234589ABCD1234567ABCD123456789CD123456789AB # C
123456789ABCD3456789ABCD1256789ABCD1234789ABCD123456CD123456789ABABCD123456789D123456789ABC6789ABCD12345456789ABCD12323456789ABCD189ABCD1234567BCD123456789A9ABCD12345678 # S
123456789ABCD3456789ABCD1256789ABCD1234ABCD12345678989ABCD1234567D123456789ABC456789ABCD123CD123456789AB789ABCD12345623456789ABCD16789ABCD12345BCD123456789A9ABCD12345678 # S
123456789ABCD3456789ABCD126789ABCD123459ABCD12345678BCD123456789A23456789ABCD156789ABCD1234CD123456789AB89ABCD1234567456789ABCD123D123456789ABC789ABCD123456ABCD123456789 # S
123456789ABCD3456789ABCD1289ABCD1234567CD123456789AB789ABCD12345623456789ABCD1ABCD12345678956789ABCD1234D123456789ABC456789ABCD1239ABCD12345678BCD123456789A6789ABCD12345 # S
123456789ABCD3456789ABCD129ABCD1234567823456789ABCD189ABCD1234567ABCD123456789456789ABCD123D123456789ABC56789ABCD1234CD123456789AB6789ABCD12345BCD123456789A789ABCD123456 # S
123456789ABCD6789ABCD12345BCD123456789A3456789ABCD1289ABCD1234567D123456789ABC56789ABCD1234ABCD12345678923456789ABCD1789ABCD123456CD123456789AB456789ABCD1239ABCD12345678 # C


[Mathimagics]

Code: Select all

1. Cyclical shift of columns from left to right: (R,C) --> (R,C+1(mod 13))
2. Cyclical shift of rows from top to bottom:    (R,C) --> (R+1(mod 13),C)
3. Horizontal reflection:                        (R,C) --> (12-R,C)
4. "H transformation":                           (R,C) --> (R+C(mod 13),C-R+13(mod 13))
5. Multiplication                                (R,C) --> (2R(mod 13),2C(mod 13))
6. Multiplication                                (R,C) --> (3R(mod 13),3C(mod 13))
7. Multiplication                                (R,C) --> (5R(mod 13),5C(mod 13))
8. Multiplication                                (R,C) --> (7R(mod 13),7C(mod 13))
9. Multiplication                                (R,C) --> (11R(mod 13),11C(mod 13))

It looks like this list is minimal, i.e. no generator can be removed from the list.

This list is a lot smaller than my original one, but it turns out not to be minimal!

Since 2 is a primitive root modulo 13, we don't need items 6,7,8,9. And so just 5 transformations are enough to define the VPT group.

Most N of interest are prime, and only one "multiplication" transformation is required. Note that 2 is NOT always a primitive root, so I have given a table below with suitable choices of M.

For compound N, M must be a generator for the multiplicative group modulo N. Sometimes 2 values, and thus 2 transformations are needed. For any N < 100 that has pandiagonal squares, in every case only 1 or 2 M-transformations are needed.

We can write a generic minimal VPT generator set as follows:

Code: Select all

1. Cyclical shift of columns from left to right: (R, C) --> (R, C+1)
2. Cyclical shift of rows from top to bottom:    (R, C) --> (R+1, C)
3. Horizontal reflection:                        (R, C) --> (N-1-R, C)
4. "H transformation":                           (R, C) --> (R+C, C-R+N)
5. Multiplication                                (R, C) --> (MR, MC)


Where all arithmetic is done mod N, and the "M" in the 5th element is valid. Here is a list of valid M for N < 50:

List of M values: Show

Code: Select all

N =  13: M = 2
N =  17: M = 3
N =  19: M = 2
N =  23: M = 5
N =  25: M = 2
N =  29: M = 2
N =  31: M = 3
N =  35: M = 2, 6
N =  37: M = 2
N =  41: M = 6
N =  43: M = 3
N =  47: M = 5
N =  49: M = 3


Note that N = 35 has pandiagonal squares, and has two prime factors, and this means we need 2 transformations (2 M-values). All other N < 50 require only 1 M-transformation.

[Mathimagics]

.
Just when I thought I had nailed down the minimal set of generators, there is one more surprise!

It seems that the M-transformation, for M = 2, is equivalent to some combination of transformations 1 to 4.

So, if M = 2 is a generator (or one of the generators) for the multiplicative group, then we can omit that M-transformation.

For N < 50, only 4 or 5 transformations are needed to generate the VPT group:

• for N = {13, 19, 25, 29, 37}, no M-transformation needed

• for N = {17, 31, 43, 49} add M = 3 transformation

• for N = {23, 47} add M = 5 transformation

• for N = {35, 41} add M = 6 transformation

[Serg]

Hi, Mathimagics!

It seems that the M-transformation, for M = 2, is equivalent to some combination of transformations 1 to 4.

I confirm that for 13 x 13 PLSs 4 transformations only are sufficient to generate all VPTs.

But what orders have VPT 4 subgroups generated by 4 generators?

Code: Select all

1. Cyclical shift of columns from left to right: (R,C) --> (R,C+1(mod 13))              - 13 ways
2. Cyclical shift of rows from top to bottom:    (R,C) --> (R+1(mod 13),C)              - 13 ways
3. Horizontal reflection:                        (R,C) --> (12-R,C)                     -  2 ways
4. "H transformation":                           (R,C) --> (R+C(mod 13),C-R+13(mod 13)) -  ? ways

Does "H transformation" itself generates subgroup of order 48 (to produce 16224 VPTs)?
Does "H transformation" subgroup contain "Transposition" transformation?

Serg

[Mathimagics]

Hi Serg,

Taken individually:

• T (cyclic shifts) generates a group of size N^2

• R (reflection) generates a group of size 2

• H generates a group of size Phi(N) = N-1

• M[k] generates a group of size Phi(N) = N-1 (if k is a generator)

The Atkin paper states (Corollary 2.9, more or less):

• the subgroup generated by {M} has order Phi(N).

• the group generated by {M, R, H} modulo that subgroup has order 8

• the VPT group is the semi-direct product of the subgroups {M, R, H} and {T}

I don't understand this level of group theory fully, but the effect of combining {M, R, H} gives a group of order 8 x Phi(N). Adding {T} then gives 8 x Phi(N) x N^2.

Now, while investigating all of this with GAP, I uncovered some more surprising properties:

• the T (cyclic shift) transforms are redundant

• H = M[2] (the group generated by H is isomorphic to that generated by M[2])

This means that N=13 (and any prime N for which 2 is a generator) can be defined with just 2 transformations, {R, H}.

Where 2 is not a generator (mult group mod N) we need just 3 transformations, {R, H, M[k]}, where k is a generator. For example, N=17 requires {R, H, M[3]}.

Note that N = 35 requires 2 generators (mult mod N), but one of these can be 2, the other 6, so that {R, H, M[6]} generates the VPT group.

All N < 50 have been GAP tested, and the results verified.

[1to9only]

I just came across these on github, may be of interest:
https://github.com/ipgmvq/semi_cyclic_pandiagonal_latin_squares_order_13
https://github.com/ipgmvq/non_cyclic_pandiagonal_latin_squares_order_13

[Mathimagics]

Thanks for those links!

I do hope this is evidence you are pondering the curly question I posed above (how that grid is semi-cyclic?) If so, you are well on the way to solving the riddle!

I see the name Makarova mentioned therein. Serg and I have heard of her already, on the issue of semi-cyclic PLS's. She has posted stuff on OEIS quite recently.

On the other subject (non-cyclic PLS construction), it should be noted that the algorithm of Dabbaghian & Wu's is not universal. It only works for N prime and of the form 6k + 1. So, N = 17, the next size of interest after N = 13, is not suitable.

It's amazing, though, that so much active research is going on in parallel here!

[m_b_metcalf]

The first unrated grid crashed the program with an 'out of memory' error! The other unrated grids were stopped after about 5-10 minutes of processing!

Thanks for providing these challenging puzzles. I'm using them to try out my new program and, FWIW, it finds that the first, second and fourth unrated puzzles can be solved by back doors (9 at r/c 1 9 for the first two, 8 at r/c 1 8 for the other). For the moment, I can't solve the other two.

Regards,

Mike

[1to9only]

For the moment, I can't solve the other two.

I think unrated #3 has multiple solutions (according to PD13 GUI), and unrated #5 is valid (has unique solution).

[m_b_metcalf]

For the moment, I can't solve the other two.

I think unrated #3 has multiple solutions (according to PD13 GUI), and unrated #5 is valid (has unique solution).

Progress: I can now solve all of your 26 hard puzzles, except the first three. The third unrated puzzle has, according to me, a unique solution.

Mike