SelfOrthogonal.hpp File Reference

On investigations regarding self-orthogonal latin squares. More...

Go to the source code of this file.

Detailed Description

On investigations regarding self-orthogonal latin squares.

Searching pandiagonal latin squares
  • According to [Constructions for pandiagonal strongly symmetric self-orthogonal diagonal Latin squares, Chen, Li, Zhang].
  • There PSSSODLS(n) is defined, which we treat as the set of all "pandiagonal strongly symmetric self-orthogonal diagonal Latin squares of order n":
    1. "Diagonal" means that diagonal and "back-diagonal" (from right-top to left-bottom) contains all numbers.
    2. "Self-orthogonal": the matrix is orthogonal (see above) to its transposed.
    3. The set of all self-orthogonal diagonal Latin squares of order n is SODLS(n).
    4. "Strongly symmetric" means we have l_{i,j} + l_{n-1-i,n-1-j} = n-1, using indices 0,...,n-1 for the square l.
    5. This additional condition yields SSSODLS(n).
    6. "Pandiagonal" means if for each w in {0,1...,n-1}, using arithmetic modulo n in the indices, we have sum_{i=0}^{n-1} l_{i,i+w} = sum{i=0}^{n-1} l_{i,w-i} = n*(n-1)/2.
  • Problem 4.2 in the paper asks whether PSSSODLS(n) is non-empty for n=12,24 or n congruent 3 (mod 6) (where n >= 9).
  • Results mentioned in the paper:
    1. SOLS(n) as well as SODLS(n) is non-empty iff n notin {2,3,6}.
    2. SSSODLS(n) is non-empty iff n cong 0,1,3 mod 4 and n#3.
    3. For n cong 1,5 mod 6, n >= 5, PSSSODLS(n) is not empty.
    All these constructions should be implemented at the Maxima-level (see below).
  • Regarding the non-emptiness of PSSSODLS(n) the following is known:
    1. n=1 is non-empty.
    2. There are no SOLS for n in {2,3} and thus PSSSODLS(n) is empty here.
    3. PSSSODLS(4) is empty ("easy to see").
    4. PSSSODLS(5) non-empty by above general result.
    5. PSSSODLS(6) empty, since SOLS(6) empty.
    6. PSSSODLS(7) non-empty by above general result.
    7. PSSSODLS(8) non-empty; the example from the paper for an element is available as psssodls_8_ls (in ComputerAlgebra/CombinatorialMatrices/Lisp/LatinSquares/BasicNotions.mac).
    8. PSSSODLS(n) non-empty 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):
    1. Given A in PSSSODLS(m) and B in PSSSODLS(n), there is C in PSSSODLS(m*n) (Construction 2.2).
    2. Given A in SSSODLS(n), there is B in PSSSODLS(8*n) (Construction 2.3).
    3. Given A in SSSODLS(n), there is B in PSSSODLS(4*n) (Construction 2.5).
  • Since our indices are 1-based, we use the standard matrix-indices, starting with 1, and also the values of latin squares are 1-based.
  • 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).
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 non-boolean variables:
    1. Given the current availability of tools and methods, it seems easiest for now to jump directly to the boolean level, specifying some reasonable encodings.
    2. 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).
    3. The "formulas" (clause-sets with possible extensions, like pseudo-boolean conditions) F_i(n) have var(F_i(n)) <= t_i(n), where F_i(n) is satisfiable iff PSSSODLS(n) is non-empty, and where for a total satisfying assignment via ip_i we get a solution.
    4. I (OK) see three possible t_i (t_1,t_2,t_3):
      1. t_1 just uses the so-called direct encoding, i.e., the variables ls(i,j,k), already used in ComputerAlgebra/Satisfiability/Lisp/Generators/LatinSquares.mac.
      2. t_2 uses the unary encoding, that is, variables uls(i,j,k) for field (i,j) and 1 <= k <= n-1, 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 p-1, i.e., 0-based. 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.
      3. t_3 uses both variable-types at the same time, with the linking ls(i,j,k) <-> (not uls(i,j,k) and uls(i,j,k-1)) (where for k=1 the undefined term "uls(i,j,k-1)" 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".
  • Bijectivity-constraints:
    1. The latin-square conditions as well as the diagonality-condition are bijectivity-conditions (in the affected lines all values are used precisely once).
    2. We need special tools for handling such conditions.
    3. How strong is the dependency on the encoding (direct versus unary)?
    4. "Orthogonal" bijectivity-conditions interfere -- what can be said w.r.t. the prime implicates?
  • Strong symmetry:
    1. For appropriate pair of values x, y we have x+y=n-1 (using 0-based values).
    2. For both encodings this can be expressed directly (without using some form of addition).
  • Self-orthogonality:
    1. 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.
    2. For arbitrary square matrices we have here just (i,j)#(i',j').
    3. However for latin squares this can be strengthened to i::i' *and* j::j'.
  • Pan-diagonality:
    1. This can be expressed by cardinality-conditions using the unary encoding.
  • We have thus four blocks of conditions (bijectivity, strong symmetry, self-orthogonality, pan-diagonality): Are there interesting combinations of these components (where we have good representations)?
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?
    1. What are the symmetries of the problem (being a psssodls and a Sudoku)?
    2. We can replace numbers i by 10-i.
    3. And we can transpose the matrix.
    4. Is that it?
    5. 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.