4
$\begingroup$

An empty cell in a partial Latin square (pLs) is said to be forced if it has a unique admissible entry (compatible with the definition of a Latin square). Attempting to complete a given pLs, one can start by successively filling in these forced entries.

If the pLs is completable, this can lead to the following two situations:

  1. The pLs can be completed solely by forcing. Such pLs are usually called strongly completable. Example: $\left(\begin{array}{ccc} 1&-&- \\-&3&- \\ -&-&- \end{array}\right)$; the middle entry in the top row is forced to be 2, and so on.
  2. The pLs cannot be completed solely by forcing. At some point one has to make a case analysis (there might still exist a unique completion). Such pLs are usually called weakly completable. Example: $\left(\begin{array}{ccccc}-&-&-&-&5\\-&1&4&-&-\\3&-&5&-&-\\4&-&2&-&-\\-&-&-&2&4\end{array}\right)$; no forced entry, but nevertheless has a unique completion.

However, I'm interested in partial Latin squares that are not completable. If we attempt to fill a non-completable pLS by forcing, we run into either of the following two situations:

  1. Forcing leads to a contradiction (i.e. there is a cell with no admissible entry). We might call such a pLs strongly non-completable.
    Example: $\left(\begin{array}{ccc}1&-&-\\-&3&-\\-&-&1\end{array}\right)$; both the left and right entry in the middle row are forced to be 2.
  2. Forcing does not lead to a contradiction; at some point we have to make a case analysis to show that the pLs is not completable. Let's call such a pLs weakly non-completable.
    Example: ???

Question: All non-completable pLs I know of are strongly non-completable. Are there known examples of weakly non-completable partial Latin squares (maybe even a trivial one I'm missing)? Is there a way to systematically construct such examples? More generally, has the notion 4. been studied before?

$\endgroup$
1
$\begingroup$

$$\left(\begin{array}{ccccc}1&2&3&-&-\\2&3&1&-&-\\3&1&2&-&-\\-&-&-&-&-\\-&-&-&-&-\end{array}\right)$$

$\endgroup$
  • $\begingroup$ That counts as a trivial example, thanks! $\endgroup$ – David Aug 19 '17 at 9:53
2
$\begingroup$

Latin square completion can be considered as a constraint satisfaction problem, which can be solved by a backtracking approach. In your language, a PLS is weakly non-completable if it is not completable but requires backtracks.

Gomes and Selman discuss this in their paper 'Problem Structure in the Presence of Perturbations' (http://www.cs.cornell.edu/selman/papers/pdf/97.aaai.problem.pdf). They consider the number of backtracks required against the fraction of completed entries in the PLS. Empirically they observe a 'phase transition' at around 42% preassignment, where PLS go from being mostly completable to mostly uncompletable. The number of backtracks required peaks around this transition point. They do not provide any examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.