Plans for the module on searching latin squares and generalisations.
More...
Go to the source code of this file.
Namespaces 
namespace  OKlib::LatinSquares 
 Tools for latin squares and generalisations and refinements.

namespace  OKlib 
 All components of the OKlibrary.

Detailed Description
Plans for the module on searching latin squares and generalisations.
 Todo:
 Update namespaces.
 Todo:
 Update milestones.
 Todo:
 Update the following todos.
 Todo:
 Review: Software and literature review.
 Todo:
 Connections to other modules
 Todo:
 Basic direct algorithms
 Todo:
 Active clausesets

By combinining injectivity (bijectivity) constraints, the extension problem for latin squares and the problem of finding mutually orthogonal sets of latin squares (MOLS) shall be provided as an active clauseset.

Perhaps the matching techniques underlying the injectivity constraints can be generalised?!

Perhaps is makes sense for an array v_ij of variables to have an active clauseset LS((v_ij)), expressing that the variables form a latin square.

The direct implementation of LS((v_ij)) uses INJ((v_1j, ..., v_nj) and INJ(v_i1, ..., v_in).

Such active clausesets do not offer polytime performance for (e.g.) satisfiability checking, but they might be useful if it has nevertheless "special knowledge". LS(V) could offer only incomplete services (then it should be polytime), or it might offer complete services (then it won't be polytime).
 Todo:
 Completing partial latin squares

Every partial latin squares of order n with n1 entries can be completed (and there exists an efficient algorithm for it): How do the various (generalised) SAT algorithms perform here?

Consider a partial latin square of order n with n+k entries. One could conjecture that it can be completed iff the alliance of active clausesets given by the bijectivityconstraints is not found inconsistent by r_k reduction? (The case k = 0 follows by [Andersen, Hilton, 1983].)
 Todo:
 Strong hypergraph colouring

A latin square of dimension n is nothing else than a hypergraph G_n with 2n hyperedges of size n for the rows and columns together with the strong ncolouring problem for hypergraphs (see Hypergraphs/Colourings/plans/StrongColouring.hpp).

What can be done specially for latin squares, which cannot be done in general for the strong hypergraph colouring problem? (For example regarding symmetries?)
 Todo:
 MOLS

MOLS((v_ijk)) can be expressed by

LS((v_ij1)), ..., LS((v_ijn))

for 1 <= k1 < k2 <= k introduce variables w_{ij(k1,k2)} with domains {1,...,n}^2 and w_{ij(k1,k2)} = (v1, v2) <> v_{ijk1} = v1 and v_{ijk2} = v2;

now require INJ(w_{ij(k1,k2)}) for every pair (k1,k2).

The second type of active clausesets can be captured by active clausesets MOS((v_ij), (v'_ij)) ("mutually orthogonal squares"; note that this notion makes sense for arbitrary squares). Thus MOLS((v_ijk)) becomes the conjunction of LS for all single squares and MOS for all pairs of squares.

The new variables w are only necessary if we want to use INJ directly on variables; expressing INJ "by hand", we can express MOS(v, v') as a conjunction of of (n^2 over 2) * n^2 = n^4 * (n^2  1) / 2 4clauses using only the variables v, v'.

If n is the uniform domain size (the order of the latin square), then for all 2sets {(p,q), (p',q')}, where p,q,p',q' in {1, ..., n}, and for all eps, eps' {1, ..., n} we get the 4clause (v_pq <> eps or v_p'q' <> eps or v'_pq <> eps' or v'_p'q' <> eps').
 Todo:
 Sizes

Thus the sizes for the direct clause representation are (using LS(n) for the clauseset expressing the condition on the existence of a latin square of order n, and MOS(n,k) for the condition on the existence of k squares of order n which are mutually orthogonal):

LS(n) has 2*n*binomial(n,2)*n = n^3 * (n1) = O(n^4) 2clauses (using n^2 variables, each with domain size n).

MOS(n, k) has binomial(k,2)*n^4*(n^21)/2 = k*(k1)*n^4*(n^21)/4 = O(k^2 * n^6) 4clauses (using k*n^2 variables, each with domain size n).

MOLS(n,k) has k * n^3 * (n1) = O(k * n^4) 2clauses and k*(k1)*n^4*(n^21)/4 = O(k^2 * n^6) 4clauses (using k*n^2 variables, each with domain size n).

For n=10 we get that MOLS(n,k) has k * 9000 2clauses (9000 for each LS), and k*(k1) * 247500 4clauses, and that with k * 100 variables of domain size 10.

For k=3 we get 27,000 2clauses and 1,485,000 4clauses with 300 variables of domain size 10, which is pretty big. In principle one can run a SAT solver on it, but likely without active clausesets we won't have a chance.
 Todo:
 N(n)

For n >= 1 let N(n) be the maximal number of MOLS. Thus

N(1) = 1

N(n) <= n  1 for n >= 2

N(n) = n  1 if n = p^k for a prime number p and a natural number k >= 1

N(6) = 1

This determines N(n) for 1 <= n <= 9. The first open case is N(10).

It is known

n notin {1, 2, 6} > N(n) >= 2

n >= 2: either N(n) = n  1 or N(n) <= n  4

N(10) <> 9 (computer experiments showed that there is no projective plane of order 10).
Thus 2 <= N(10) <= 6 (more recent results?). Can we improve this?!

The next case is N(12). It is known that 5 <= N(12) <= 11 (more recent results?); can we improve this?!

Apparently for all n >= 11 it is known N(n) >= 3 ?!

Two approaches possible: starting from above, showing that the problem is unsatisfiable, or starting from below, showing that the problem is satisfiable.)

In general we have:

N(n) = n  1 iff an affine plane of order n exists iff a projective plane of order n exists.

It is stated in [Beth, Jungnickel, Lenz] that the exact value of N(n) is only known for n = p^k, p prime number, k >= 0, and for n = 6.
 Todo:
 Experiments

So we could try decide MOLS(10,3) or MOLS(10,6)  in both cases any result SAT/UNSAT would yield a new bound (most interesting: MOLS(10,3) in UNSAT => N(10) = 3, MOLS(10,6) in SAT => N(10) = 6).

Not a new result, but still interesting (and publishable) would be, if a generalised SAT solver could show the unsatisfiability of some MOLS(10,k) for 7 <= k <= 9.
 Todo:
 Pairs of orthogonal latin squares

MOLS(n,2) in SAT for all n notin {1,2,6} yields interesting satisfiable problems.
 Todo:
 The upper bounds for N(k)

MOLS(n,n) in UNSAT for all n yields unsatisfiable problems, which could also be interesting (at least for active clausesets; real clausesets get very soon very big).
Definition in file general.hpp.