Pandiagonal Latin Squares

Programs which generate, solve, and analyze Sudoku puzzles

Re: Pandiagonal Latin Squares

Postby Mathimagics » Wed Jun 23, 2021 4:44 pm

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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Re: Pandiagonal Latin Squares

Postby coloin » Wed Jun 23, 2021 5:16 pm

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
coloin
 
Posts: 2083
Joined: 05 May 2005

Re: Pandiagonal Latin Squares

Postby 1to9only » Wed Jun 23, 2021 5:49 pm

coloin wrote: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 ...
1to9only
 
Posts: 3281
Joined: 04 April 2018

Re: Pandiagonal Latin Squares

Postby m_b_metcalf » Wed Jun 23, 2021 5:49 pm

Mathimagics wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 12289
Joined: 15 May 2006
Location: Berlin

Re: Pandiagonal Latin Squares

Postby Mathimagics » Wed Jun 23, 2021 6:18 pm

m_b_metcalf wrote:program's a work-in-progress ...

Sounds like one of mine :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Re: Pandiagonal Latin Squares

Postby 1to9only » Wed Jun 23, 2021 10:35 pm

1to9only wrote: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
1to9only
 
Posts: 3281
Joined: 04 April 2018

VPT Group Review

Postby Mathimagics » Fri Jul 16, 2021 9:52 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Pandiagonal Enumeration - Cyclic + Semicyclic grids

Postby Mathimagics » Mon Aug 23, 2021 3:38 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Re: Pandiagonal Latin Squares

Postby Serg » Tue Aug 24, 2021 12:41 pm

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

Serg
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: Pandiagonal Latin Squares

Postby Mathimagics » Tue Aug 24, 2021 2:56 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1812
Joined: 27 May 2015
Location: Canberra

Previous

Return to Software