The New Sudoku Players' Forum

[Mathimagics]

Of those 5 unrated puzzles posted by 1to9only, #1 to #4 have only 11 distinct clue values, so are clearly invalid ...

#5 is legal, and has one solution, so it's valid!

[coloin]

It took me a while to find the puzzle list you all were refering to and ... indeed #1 - #4 dont have 12 clue values...
somehow its facinating that SE cant compute the ratings of these very non minimal puzzles

Code: Select all

#5 ..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8.......3.............  25 unrated

[1to9only]

somehow its facinating that SE cant compute the ratings of these very non minimal puzzles

Code: Select all

#5 ..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8.......3.............  25 unrated

It is unrated because I stopped the process after 10-15 mins. It just needs a bit more compute time!! I think SE will need a few hours ...

[m_b_metcalf]

Of those 5 unrated puzzles posted by 1to9only, #1 to #4 have only 11 distinct clue values, so are clearly invalid ...

#5 is legal, and has one solution, so it's valid!

OK, that's why I find backdoors for #1, #2 and #4. #5 is OK and I checked on #3 again, and now find it has no unique solution (program's a work-in-progress).

Mike

[Mathimagics]

program's a work-in-progress ...

Sounds like one of mine

[1to9only]

It is unrated because I stopped the process after 10-15 mins. It just needs a bit more compute time!! I think SE will need a few hours ...

Maybe, I was hasty, stopping the program too soon!! Previouslly unrated #5 has a rating (it took about 10 mins!!):

Code: Select all

..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8.......3.............  25 ED=9.7/1.5/1.5


[Mathimagics]

1. Standard Generating Set

A minimal VPT generator set, that conforms to Atkin's definitions, consists of 5 generators (for all prime N):

Code: Select all

1a. [TC] Cyclical shift columns:  (R, C) --> (R, C+1)
1b. [TR] Cyclical shift rows:     (R, C) --> (R+1, C)
2.  [V]  Vertical reflection (*): (R, C) --> (R, -C)
3.  [H]  House shift:             (R, C) --> (R+C, C-R)
4.  [M]  Multiplication by K:     (R, C) --> (KR, KC)


Notes:

• all arithmetic is done modulo N

• the value K in the M-transformation is a generator for the multiplicative group modulo N. If N is not prime, or a power of a prime, then additional M-transformation generators are required, eg N = 35 = 5 x 7 requires K = 2 and K = 6

• (*) note that transformation V keeps column 0, and reflects columns 1 to N-1. It is equivalent to a normal (full) reflection followed by a right-shift

It should be obvious that the TR and TC transformations generate all of the Atkin translation transformations (R + a, C + b). Also, if K is a generator for the multiplicative group modulo N, then the M(K) transformation generates all of the Atkin multiplication transformations (mR, mC).

List of generators for N < 50: Show

Code: Select all

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


2. Reduced Generating Set

It was discovered, quite by accident, that the VPT group could be generated by just 2 or 3 transformations:

Code: Select all

1.  [R]  Vertical reflection:     (R, C) --> (R, N-1-C)
2.  [H]  House shift:             (R, C) --> (R+C, C-R)
3.  [M]  Multiplication by K:     (R, C) --> (KR, KC)


Notes:

• we have omitted [TR] and [TC], and replaced [V] with [R]

• the M transformation can be omitted whenever K = 2 is a generator for the multiplicative group modulo N

Remarkably, then, only two transformations are needed to generate the VPT group for N = 13, 19, 25, 29, 37 ...


3. House Shift Transformation

As reported by Atkin, the [H] transformation maps rows to right-diagonals, right-diagonals to columns, columns to left-diagonals, and left-diagonals to rows. For this reason I call it the "house shift".

These mappings are not fixed, however. If they were fixed, then applying [H] to any grid 4 times would restore the original grid. The order of the group {H} that is generated by [H] would be 4.

For N = 13, the order of the group {H} is 12, and for N = 17 it is 16.

We might reasonably assume, then, that {H(N)} generates a group of order phi(N).

So for prime N, that means order{H(n)} = N-1. For N = 19 we would expect that to be 18 ...

But we actually find that order{H(19)} = 72.

Order{H(N)}: Show

Code: Select all

N =  13:    12
N =  17:    16
N =  19:    72
N =  23:    88
N =  25:    20
N =  29:    28
N =  31:    40
N =  35:    24
N =  37:    36
N =  41:    20
N =  43:    56
N =  47:   184
N =  49:   168
N =  53:    52
N =  55:    40
N =  59:   232
N =  61:    60
N =  65:    12
N =  67:   264
N =  71:   280
N =  73:    72
N =  77:   120
N =  79:   312
N =  83:   328
N =  85:    16
N =  89:    88
N =  91:    24
N =  95:    72
N =  97:    96
N = 101:   100
N = 103:   408
N = 107:   424
N = 109:    36
N = 113:    28
N = 115:    88
N = 119:    48
N = 121:   440
N = 125:   100
N = 127:    56


I can find no OEIS sequence that corresponds to these values. For prime N, when N = 8k +1 or 8k + 5, then often order{H(N)} = N-1, but not always. N = 41 is one example.

[Mathimagics]

The following table summarises enumeration results obtained for various N (up to 31), showing the numbers of cyclic and semicyclic grids.

Cyclic grids are listed as type "C". Semicyclic grids are divided into two categories - type "SN" refers to grids that are semicyclic in the "normal" sense. They are cyclic in either rows, columns, left- or right-diagonals. Type "SX" refers to grids that are cyclic wrt extended knights moves, eg (R,C) (R+1,C+X)(R+2,C+2X), etc

Code: Select all

 +----+-------------------------------+-------------------------+
 |    |          Total grids          |         ED grids        |
 +----+-------------------------------+-------------------------+
 |  N |    C              SN       SX |   C          SN    SX   |
 +----+-------------------------------+-------------------------+
 | 13 |   10            1352      208 |   2           5     1   |
 | 17 |   14           33048      952 |   3          27     4   |
 | 19 |   16          172672     2432 |   2          84     7   |
 | 23 |   20        22408624     9200 |   3        5712    17   |
 | 25 |   10       313235960    11240 |   2       79156    16   |
 | 29 |   26     83574766152    91176 |   4    12874403    79   |
 | 31 |   28   1729670668496   334800 |   4               173   |
 +------------------------------------+-------------------------+


The OEIS sequence A343867 reflects the total semicyclic grid counts (SN + SX). Prior to these computations, counts were only available for N up to 23. The values that I obtained for N = 25, 29 and 31 are new entries.

ED grid counts were obtained by VPT orbit-tracing. The only entry missing is the ED count for SN grids with N = 31. This is a lengthy computation that will take some considerable time.

[Serg]

Hi, Mathimagics!
Congratulations on your new results!
Do you know numbers of all different grids and ED grids?

Serg

[Mathimagics]

Hi, Serg!

The number of type "A" (acyclic) grids is known only for the case N = 13, which is why the sequence A338620 shows no additional values.

The properties of cyclic and semicyclic grids allows for explicit enumeration methods. Semicyclic grids (both SN and SX) can be written as special exact cover problems for which the DLX method can be used. That is the method I used.

To count all solution grids for N = 17 using exact cover seems a huge task. For example, I tested just one instance with the first 3 rows fixed, and that took 8 days!

The disjoint-templates approach seems to be the only viable option. That would still take many core-years, but it is a job suitable for splitting, so with a few willing participants we might be able to knock it off sooner ...

I should point out that it is not difficult to find examples of acyclic grids, for N ≥ 17. One can use exact cover to find grids that are orthogonal to a cyclic PLS, and many of the grids found will be acyclic.

But N = 13 also tells us that not all acyclic grids are orthogonal. There are 2 ED acyclic grids, but only one is orthogonal.