Cuadrado latino parcial débilmente no completa

Question

Una celda vacía en un parcial de cuadrado latino (pLs) se dice que es obligado si se tiene un único admisible de entrada (compatible con la definición de un cuadrado latino). Tratando de completar un determinado pLs, uno puede comenzar sucesivamente llenado en estos forzado de entradas.

Si el pLs es completable, esto puede llevar a las dos situaciones siguientes:

1. El pLs puede ser completado solamente por forzar. Tal pLs por lo general se llama fuertemente completable. Ejemplo: $\left(\begin{array}{ccc} 1&-&- \\-&3&- \\ -&-&- \end{array}\right)$; la media de entrada en la fila superior está obligada a ser la 2, y así sucesivamente.
2. Los pLs no puede ser completado solamente por forzar. En algún momento uno tiene que hacer un análisis de caso (puede que todavía existe un único término. Tal pLs por lo general se llama débilmente completable. Ejemplo: $\left(\begin{array}{ccccc}-&-&-&-&5\\-&1&4&-&-\\3&-&5&-&-\\4&-&2&-&-\\-&-&-&2&4\end{array}\right)$; no forzar la entrada, pero sin embargo tiene una única conclusión.

Sin embargo, estoy interesado en parcial de los cuadrados latinos que no completable. Si tratamos de llenar un no-completable pLS forzando, nos topamos con cualquiera de las dos situaciones siguientes:

3. Forzando conduce a una contradicción (es decir, hay una celda sin admisible de entrada). Podríamos llamar un pLs fuertemente no-completable.
   Ejemplo: $\left(\begin{array}{ccc}1&-&-\\-&3&-\\-&-&1\end{array}\right)$; tanto la izquierda y la derecha de la entrada en la fila del medio se ven obligados a ser de 2.
4. Forzar no conduce a una contradicción; en algún momento tenemos que hacer un análisis de caso para mostrar que los pLs no es completable. Vamos a llamar a un pLs débilmente no completable.
   Ejemplo: ???

Pregunta: Todos los no-completable pLs yo conozco son fuertemente no-completable. Hay ejemplos conocidos de débil no completable parcial de los cuadrados latinos (tal vez incluso trivial que me falta)? Hay una manera sistemática para construir estos ejemplos? Más en general, tiene la noción de 4. se ha estudiado antes?

Answer 1

Cuadrado latino de finalización puede ser considerado como un problema de satisfacción de restricciones, que pueden ser resueltos por un retroceso enfoque. En su idioma, un PLS es débilmente no completable si no es completable, sino que requiere retrocede.

Gomes y Selman hablar de esto en su libro la Estructura de problemas en la Presencia de Perturbaciones' (http://www.cs.cornell.edu/selman/papers/pdf/97.aaai.problem.pdf). Ellos consideran que el número de backtracks requerido en contra de la fracción de entradas completadas en el PLS. Empíricamente se observa una "fase de transición" en torno a un 42% de preasignación, donde PLS pasar de ser en su mayoría completable, principalmente, insaciable. El número de backtracks requiere picos alrededor de este punto de transición. No proporcionan ejemplos.

Answer 2

PS