On investigations regarding selforthogonal latin squares.
More...
Go to the source code of this file.
Detailed Description
On investigations regarding selforthogonal latin squares.
 Todo:
 Searching pandiagonal latin squares

According to [Constructions for pandiagonal strongly symmetric selforthogonal diagonal Latin squares, Chen, Li, Zhang].

There PSSSODLS(n) is defined, which we treat as the set of all "pandiagonal strongly symmetric selforthogonal diagonal Latin squares of
order n":

"Diagonal" means that diagonal and "backdiagonal" (from righttop to leftbottom) contains all numbers.

"Selforthogonal": the matrix is orthogonal (see above) to its transposed.

The set of all selforthogonal diagonal Latin squares of order n is SODLS(n).

"Strongly symmetric" means we have l_{i,j} + l_{n1i,n1j} = n1, using indices 0,...,n1 for the square l.

This additional condition yields SSSODLS(n).

"Pandiagonal" means if for each w in {0,1...,n1}, using arithmetic modulo n in the indices, we have sum_{i=0}^{n1} l_{i,i+w} = sum{i=0}^{n1} l_{i,wi} = n*(n1)/2.

Problem 4.2 in the paper asks whether PSSSODLS(n) is nonempty for n=12,24 or n congruent 3 (mod 6) (where n >= 9).

Results mentioned in the paper:

SOLS(n) as well as SODLS(n) is nonempty iff n notin {2,3,6}.

SSSODLS(n) is nonempty iff n cong 0,1,3 mod 4 and n#3.

For n cong 1,5 mod 6, n >= 5, PSSSODLS(n) is not empty.
All these constructions should be implemented at the Maximalevel (see below).

Regarding the nonemptiness of PSSSODLS(n) the following is known:

n=1 is nonempty.

There are no SOLS for n in {2,3} and thus PSSSODLS(n) is empty here.

PSSSODLS(4) is empty ("easy to see").

PSSSODLS(5) nonempty by above general result.

PSSSODLS(6) empty, since SOLS(6) empty.

PSSSODLS(7) nonempty by above general result.

PSSSODLS(8) nonempty; the example from the paper for an element is available as psssodls_8_ls (in ComputerAlgebra/CombinatorialMatrices/Lisp/LatinSquares/BasicNotions.mac).

PSSSODLS(n) nonempty for n cong 0 mod 4, n >= 8, n notin {12,24}, as shown in Theorem 1.5 the paper.

Constructions in the paper (apparently m,n > 1):

Given A in PSSSODLS(m) and B in PSSSODLS(n), there is C in PSSSODLS(m*n) (Construction 2.2).

Given A in SSSODLS(n), there is B in PSSSODLS(8*n) (Construction 2.3).

Given A in SSSODLS(n), there is B in PSSSODLS(4*n) (Construction 2.5).

Since our indices are 1based, we use the standard matrixindices, starting with 1, and also the values of latin squares are 1based.

Via psssodls_p(A) we can check whether matrix A is a PSSSODLS.

In [Discrete Mathematics using Latin Squares, Laywine, Mullen] the term "pandiagonal" is a strengthening of "diagonal", that is, for all pandiagonals all values must be different. This is stronger than the above notion of "pandiagonal", which only requires the sum of the entries in the pandiagonals to behave as if all values would be different.

In ComputerAlgebra/CombinatorialMatrices/Lisp/LatinSquares/BasicNotions.mac we use "strictly pandiagonal" and "pandiagonal" (this in the above sense).
 Todo:
 SAT translations

See ComputerAlgebra/Satisfiability/Lisp/Generators/LatinSquares.mac for the framework.

And see "Different encodings" and "Further conditions" in ComputerAlgebra/Satisfiability/Lisp/Generators/plans/LatinSquares.hpp for the implementation of SAT translations.

We want to construct formulas Fpsssodls_n, which are satisfiable iff PSSSODLS(n) is not empty, and where from a solution an element is constructible.

Handling the nonboolean variables:

Given the current availability of tools and methods, it seems easiest for now to jump directly to the boolean level, specifying some reasonable encodings.

That is, we consider some t_i(n) <= VA, which are sets of boolean variables, together with a map ip_i ("interpretation"), which maps total assignments over V_n to elements of PSSSODLS(n).

The "formulas" (clausesets with possible extensions, like pseudoboolean conditions) F_i(n) have var(F_i(n)) <= t_i(n), where F_i(n) is satisfiable iff PSSSODLS(n) is nonempty, and where for a total satisfying assignment via ip_i we get a solution.

I (OK) see three possible t_i (t_1,t_2,t_3):

t_1 just uses the socalled direct encoding, i.e., the variables ls(i,j,k), already used in ComputerAlgebra/Satisfiability/Lisp/Generators/LatinSquares.mac.

t_2 uses the unary encoding, that is, variables uls(i,j,k) for field (i,j) and 1 <= k <= n1, where value 1 <= p <= n is encoded by uls(i,j,k) being true for exactly k < p. This is unary when considering the actual value as p1, i.e., 0based. And we have the property that if uls(i,j,k) is true, then also for all k' < k, and if it's false, then also for all k' > k.

t_3 uses both variabletypes at the same time, with the linking ls(i,j,k) <> (not uls(i,j,k) and uls(i,j,k1)) (where for k=1 the undefined term "uls(i,j,k1)" is not there).

According to our general approach for "good translations", the target is to achieve a hardness as low as possible (not using "too many" clauses).

This is applied (currently) to the components of the translation, where the components should be as "big as possible".

Bijectivityconstraints:

The latinsquare conditions as well as the diagonalitycondition are bijectivityconditions (in the affected lines all values are used precisely once).

We need special tools for handling such conditions.

How strong is the dependency on the encoding (direct versus unary)?

"Orthogonal" bijectivityconditions interfere  what can be said w.r.t. the prime implicates?

Strong symmetry:

For appropriate pair of values x, y we have x+y=n1 (using 0based values).

For both encodings this can be expressed directly (without using some form of addition).

Selforthogonality:

This can be expressed in general as the conditions that for different cells (i,j), (i',j') with equal values the transposed cells (j,i), (j',i') must have different values.

For arbitrary square matrices we have here just (i,j)#(i',j').

However for latin squares this can be strengthened to i::i' *and* j::j'.

Pandiagonality:

This can be expressed by cardinalityconditions using the unary encoding.

We have thus four blocks of conditions (bijectivity, strong symmetry, selforthogonality, pandiagonality): Are there interesting combinations of these components (where we have good representations)?
 Todo:
 Further properties

The example psssodls_9_ls is also a Sudoku (as realised by MH).

Are there other psssodls of this dimension which are also Sudoku?

What are the symmetries of the problem (being a psssodls and a Sudoku)?

We can replace numbers i by 10i.

And we can transpose the matrix.

Is that it?

By these operations we get altogether 4 variations of psssodls_9_ls.

Are there also psssodls of dimension 9 which are not Sudoku?

And what about different dimensions?
Definition in file SelfOrthogonal.hpp.