The New Sudoku Players' Forum

[Mathimagics]

I have been looking into this topic, which was was briefly mentioned back in 2006, when the existence of a Pandiagonal Sudoku Square was reported. More on that a little bit later on ...

A Latin Square is pandiagonal if every left and right diagonal also has distinct digits. Here is an example (N = 7):

Code: Select all

   +---+---+---+---+---+---+---+
   | 1 | 5 | 3 | 4 | 6 | 7 | 2 |
   +---+---+---+---+---+---+---+
   | 3 | 4 | 6 | 7 | 2 | 1 | 5 |
   +---+---+---+---+---+---+---+
   | 6 | 7 | 2 | 1 | 5 | 3 | 4 |
   +---+---+---+---+---+---+---+
   | 2 | 1 | 5 | 3 | 4 | 6 | 7 |
   +---+---+---+---+---+---+---+
   | 5 | 3 | 4 | 6 | 7 | 2 | 1 |
   +---+---+---+---+---+---+---+
   | 4 | 6 | 7 | 2 | 1 | 5 | 3 |
   +---+---+---+---+---+---+---+
   | 7 | 2 | 1 | 5 | 3 | 4 | 6 |
   +---+---+---+---+---+---+---+


Note that we generalise the idea of a diagonal by allowing "wraparound". These are also called broken diagonals. Thus there are N left diagonals and N right diagonals. For N = 5, the left diagonals are:

Code: Select all

  X . . . .     . X . . .     . . X . .     . . . X .     . . . . X
  . . . . X     X . . . .     . X . . .     . . X . .     . . . X .
  . . . X .     . . . . X     X . . . .     . X . . .     . . X . .
  . . X . .     . . . X .     . . . . X     X . . . .     . X . . .
  . X . . .     . . X . .     . . . X .     . . . . X     X . . . .


So a PD latin square is essentially a 4-house "Sudoku Variant". The grid can be partitioned into sets of N houses, one set each for rows, cols, left diagonals, right diagonals.

Unfortunately, PD Latin squares are very rare. They can only occur when N is not divisible by 2 or 3. For N = 5, 7, and 11 there are very few (2, 4 and 8 respectively), and they are all cyclic, which means each row/col is a cyclic shift of the first row/col.

However, for N = 13, it suddenly gets interesting. There are 12,386 ED grids, most (90%) of them being non-cyclic, so suitable for puzzle creation.

For N > 13 (N = 17, 19, 23, 25 etc), the number of grids expands, but enumerating them becomes computationally difficult. The "disjoint template" method can quickly find all N=13 grids, but N=17 is very much harder.

N = 13 also seems to be a good size for P&P solving (not too unwieldy) ...


Here is an example grid for N =13. I use {1-9,ABCD} to represent the digits 1 to 13:

Pandiagonal LS, N=13: Show

Code: Select all

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


[Mathimagics]

My friend Serg will no doubt be interested in what VPT's there are for Pandiagonal Latin Squares!

From an old paper (*) I found that there are 4 types of VPT. If we label the row and columns {0, N-1}, and assume that N is prime, the transformations are:

• type G: geometric, reflection/rotation etc. (4 ways)

• type T: translation. For any pair a, b both in [0, N-1] we can map cell (R, C) to (R + a, C + b), modulo N. (N x N ways)

• type M: multiplicative. For any k with gcd(N, k) = 1, then we can map cell (R, C) to (kR, kC), modulo N. (N-1 ways)

• type H: house cycle. Cell (R, C) maps to (R + C, C - R) modulo N. This maps rows to right-diagonals, right-diagonals to columns, columns to left-diagonals, left-diagonals to rows (2 ways).

So, for our preferred size of N = 13, this gives (4 x 13^2 x 12 x 2) VPT's in total, which is 16,224. (I have confirmed this result using the GAP package).

With just 12386 ED grids, and 16224 VPT's, we should be able to obtain a complete analysis of the grids in reasonable time ...


(*) https://www.sciencedirect.com/science/article/pii/089812218390130X (p271)

[Mathimagics]

The steps taken so far, for N = 13:

• I began by generating the templates, and found a total of 4524 (348 for each cell in row 1). Every template represents a distinct solution to the n-Queens problem for a 13x13 chessboard, but not ALL Queens problem solutions correspond to templates, because we wrap the chessboard around a cylinder (the broken diagonals).

• DLX was used to enumerate all sets of 13 mutually disjoint templates, and this process identified 12,386 cases. This value corresponds to the number of "inequivalent" grids reported in the reference paper (see link in the previous post). I [u]think[/i] that this the correct value for the number of ED grids.

• I then wrote a script to generate permutations for the transformations described above, suitable for input into the GAP package, and found that the order of the group is indeed 16224

• GAP reports the individual VPT's in cyclic form. For grid-processing we prefer a permutation format, that is, a cell-to-cell mapping. After some tears, gnashing of teeth, etc, I finally got this done, and have now verified that all the VPT's work exactly as expected!

Next step is to use the VPT's to count the grid automorphisms ...

[coloin]

Commendeble that you can replicate the results !

They can only occur when N is not divisible by 2 or 3. For N = 5, 7, and 11 ... [and 13,17.... onwards]

perhaps for the layman you could explain why this is so, i can see the 2 but not the 3 !
ie ... why not N=9 or 15 I suppose ?

[Mathimagics]

Hi coloin!

For a simple mathematical introduction to pandiagonal LS's, and how to go about proving there are no solutions if N is divisible by 3, have a look at this PDF.

It is worth pointing out also that for N = 12, there are in fact some grids with the property that all partial diagonals are distinct, but not fully pandiagonal.

Example: Show

Code: Select all

   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 1 | 5 | B | 8 | 9 | 3 | 4 | A | 7 | C | 6 | 2 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 6 | A | 1 | 7 | 4 | C | B | 3 | 8 | 2 | 9 | 5 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | C | 3 | 2 | A | 6 | 7 | 8 | 5 | 9 | 1 | 4 | B |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | B | 6 | 8 | 9 | 3 | 2 | 1 | 4 | A | 7 | 5 | C |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 4 | 9 | 7 | 1 | 5 | B | C | 6 | 2 | 8 | A | 3 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 5 | 2 | C | 4 | A | 8 | 7 | 9 | 3 | B | 1 | 6 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 8 | 4 | 9 | 2 | B | 5 | 6 | C | 1 | A | 3 | 7 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 2 | B | 6 | 3 | 8 | A | 9 | 7 | 4 | 5 | C | 1 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | A | 7 | 5 | B | 1 | 4 | 3 | 2 | C | 6 | 8 | 9 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 9 | 1 | 4 | C | 7 | 6 | 5 | 8 | B | 3 | 2 | A |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 7 | C | 3 | 6 | 2 | 9 | A | 1 | 5 | 4 | B | 8 |
   +---+---+---+---+---+---+---+---+---+---+---+---+
   | 3 | 8 | A | 5 | C | 1 | 2 | B | 6 | 9 | 7 | 4 |
   +---+---+---+---+---+---+---+---+---+---+---+---+


Cheers
MM

[Serg]

Hi, Mathimagics!

My friend Serg will no doubt be interested in what VPT's there are for Pandiagonal Latin Squares!

From an old paper (*) I found that there are 4 types of VPT. If we label the row and columns {0, N-1}, and assume that N is prime, the transformations are:

• type G: geometric, reflection/rotation etc. (4 ways)

• type T: translation. For any pair a, b both in [0, N-1] we can map cell (R, C) to (R + a, C + b), modulo N. (N x N ways)

• type M: multiplicative. For any k with gcd(N, k) = 1, then we can map cell (R, C) to (kR, kC), modulo N. (N-1 ways)

• type H: house cycle. Cell (R, C) maps to (R + C, C - R) modulo N. This maps rows to right-diagonals, right-diagonals to columns, columns to left-diagonals, left-diagonals to rows (2 ways).

So, for our preferred size of N = 13, this gives (4 x 13^2 x 12 x 2) VPT's in total, which is 16,224. (I have confirmed this result using the GAP package).

With just 12386 ED grids, and 16224 VPT's, we should be able to obtain a complete analysis of the grids in reasonable time ...


(*) https://www.sciencedirect.com/science/article/pii/089812218390130X (p271)

Yes, of course pandiagonal Latin Squares are interesting (and new to me). But I doubt - are referred VPTs all possible VPTs? I think this question is not evident ...

Serg

[Mathimagics]

Hi Serg!

are referred VPTs all possible VPTs? I think this question is not evident ...

The linked document is a paper by Atkin et.al published in 1983. Section 2 (Transformations of PL-squares) is about the definition of the VPT group, and a proof that it is complete, so no other universal transformations are possible. I don't fully understand the proof, group theory not being my strongest suit, as we all know (!). But I can follow its structure and it looks ok to me.

My transformation list (the generators for the group) is taken directly from the four given just below Lemma 2.2, and immediately before the proof of completeness begins.

Cheers
MM

[tarek]

Well done MM. Great to see you still active on the variant front with this!!!

[denis_berthier]

.
What is this doing in the "Software" section? Shouldn't it be in the "Other logic games" section?

Anyway...
Latin Squares, seen on a flat square grid, have a natural extension: X Latin Squares, with additional constraints along the 2 diagonals.
If you (doubly) wrap the plane into a torus, the natural extension becomes Pandiagonal Latin Squares, with additional constraints along all the diagonals.

With so many constraints, I wonder how hard a Pandiagonal Latin Squares puzzle can be. Do you have any collection of them (say of size 11, to stay as close as possible to Sudoku)?

For me, it would be relatively easy to add these constraints and to be directly able to apply whips to these puzzles.

What's more delicate about such puzzles is the Subsets. In addition to the classical ones, there are the obvious corresponding ones using only orthogonal sets of diagonals. However, there are also those than can mix all kinds of lines (rows, columns, diagonals) both in the base sets and in the cover sets; this seems to me to be much more complex than the aquarium in Sudoku.

[Mathimagics]

.What is this doing in the "Software" section? Shouldn't it be in the "Other logic games" section?

Probably a fair point, but I would really classify it under "Sudoku Variants", since it is really just like a JSB (Jigsaw Sudoku with Boxes) puzzle, in that it partitions the grid into 4 x N houses, so has the basic rule of "Fill in the grid so that every row, column, XX and YY have the digits 1-N with no repeats".


I decided in the end to put the analytical material in "Software", where it has some relevance, as we are using software tools to analyze the solution space, and to place puzzle discussion in "Sudoku Variants" ...

With so many constraints, I wonder how hard a Pandiagonal Latin Squares puzzle can be. Do you have any collection of them (say of size 11, to stay as close as possible to Sudoku)?

Oh, puzzles can be hard, don't worry about that! creint and I have both produced N=13 puzzles that take our SAT/DLX solvers HOURS to solve, and are almost certainly not solvable by humans. 1to9only has developed an "serater" also ...

More constraints often leads to the possibility of less givens, which, perversely offers a much greater range of difficulty. This phenomenon was evident with SudokuP analysis, as I recall.

Regarding grid size, I chose N=13 because it is the first N for which there is sufficient solution grid variety. 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?

Cheers
MM

[Mathimagics]

Back to VPT group analysis!

I have checked all ED grids (N = 13) and found that every grid has at least one automorphism. The results are:

Code: Select all

  ------------
  |Aut|  Grids
  ------------
     2    8112
     6    2704
    26     624
    52     312
    78     416
   156     208
  2028       8
  8112       2
  ------------
         12386
  ------------


These results look to be consistent with the Atkin paper:

For n = 13 there are 12,386 inequivalent squares; 10 are cyclic in both directions, and 1560 are semi-cyclic (cyclic in a single direction).

Cyclic = |Aut| = {2028, 8112}, semi-cyclic = {26, 52, 78, 156}.

[denis_berthier]

With so many constraints, I wonder how hard a Pandiagonal Latin Squares puzzle can be. Do you have any collection of them (say of size 11, to stay as close as possible to Sudoku)?

Oh, puzzles can be hard, don't worry about that! creint and I have both produced N=13 puzzles that take our SAT/DLX solvers HOURS to solve.
I settled on N=13 because it is the first N for which there is sufficient solution grid variety. 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.
But if you have a collection for N=13, with varied levels of difficulty, I could give them a try. Not immediately; I first need to code the additional constraints.
This being said, I don't know if there is any relationship between SAT/DLX difficulty and my W classification. It'd be interesting to check that.
BTW, in the classical Sudoku case, did you check if there was any correlation being the SER (or W) and the SAT/DLX ratings?

[Mathimagics]

But if you have a collection for N=13, with varied levels of difficulty, I could give them a try. Not immediately; I first need to code the additional constraints.

Here is a singles-only puzzle and a reduction of the same puzzle, which should give you a suitable range of puzzles to test. Givens are represented as {1-9, A-D}.

Code: Select all

1.7..9...CD.....2........DA.8..5..C9..........2....4.AB..6..1...9.........3...C..4.A......1...A......CD.35..97.....2CB.D...2.......6....3........A.62.5..8........B..57..
.....9...CD.....2.........A.8..5...9..........2......A......1.............3......4........1..........CD.3...9..........D...........6.............A.6..............B..57..

BTW, in the classical Sudoku case, did you check if there was any correlation being the SER (or W) and the SAT/DLX ratings?

SAT and DLX solvers don't provide any rating information, we just know that the longer they take, the "harder" the puzzle is computationally ... and that usually means very much harder for humans ...

[denis_berthier]

Here is a singles-only puzzle and a reduction of the same puzzle, which should give you a suitable range of puzzles to test. Givens are represented as {1-9, A-D}.

I expected a larger collection, with intermediate levels of difficulty. If I start spending time on coding the additional constraints, I'd like to be sure there's enough material to exploit them. Do you have a generator that can create enough (minimal) puzzles that are not morphs of each other? Even for ordinary LatinSquares, I don't know any available one.

BTW, in the classical Sudoku case, did you check if there was any correlation being the SER (or W) and the SAT/DLX ratings?

SAT and DLX solvers don't provide any rating information, we just know that the longer they take, the "harder" the puzzle is computationally ... and that usually means very much harder for humans ...

You might be surprised how different ratings (say computation time in your case, though I admit it's never a good rating) can be totally uncorrelated. I remember a guy who published in a scientific journal a super extra intelligent rating based on super extra new chaos concepts - and the hardest Sudoku he found was solvable by Singles. Not going so far, the rating produced by gsf's generator is largely uncorrelated with the usual SER or W ratings.

[999_Springs]

denis_berthier (and anyone else watching this thread), here is mathimagics's other thread on this topic, which is in the sudoku variants section, that goes into some more detail which you may have missed. only a few puzzles have been posted and the hardest ones seem to take more than a day to test for minimality or validity which i find amazing

I remember a guy who published in a scientific journal a super extra intelligent rating based on super extra new chaos concepts - and the hardest Sudoku he found was solvable by Singles.

Difficult Sudokus Created by Replica Exchange Monte Carlo Method is your reference