Condiciones suficientes puede llenar una cuadrícula dado el contenido de la fila y la columna

No puede haber condiciones necesarias y suficientes fáciles de verificar , porque este problema es NP-completo.

(Supongo que podría imponer condiciones suficientes para que se pueda completar la cuadrícula que no son condiciones necesarias: por ejemplo, es trivial completar la cuadrícula si no se repite ningún número en dos filas o dos columnas).

Para mostrar esto, apelaremos a un conocido problema NP-completo: la terminación de cuadrados latinos . Este es un problema muy similar a éste. Un cuadrado latino es un$n \times n$cuadrícula llena de números$1$a través de$n$tal que cada número aparece exactamente una vez en cada fila y exactamente una vez en cada columna. En el problema de completar cuadrados latinos, se le proporciona una cuadrícula parcial como la siguiente:

$$\begin{bmatrix} 1 & & \\ & 3 & 1 \\ & & 2 \end{bmatrix}$$ y preguntó si podemos completarlo en un cuadrado latino llenando las celdas vacías.

Para codificar esto como una instancia del problema de fila y columna que define aquí, primero escriba los números restantes que necesitamos en cada fila y columna. En esto$3\times 3$ejemplo, eso es$\{2,3\}$por fila$1$,$\{2\}$por fila$2$,$\{1,3\}$por fila$3$,$\{2,3\}$para columna$1$,$\{1,2\}$para columna$2$, y$\{3\}$para columna$3$.

La otra cosa que debemos asegurarnos es que ninguno de estos valores se coloque en los lugares donde el cuadrado latino ya está lleno. Así que reemplace todos esos lugares por valores únicos:

$$\begin{bmatrix}101 & & \\ & 202 & 203 \\ & & 303\end{bmatrix}$$ y asegúrese de que esos valores deben colocarse allí agregando ese valor solo a la fila y la columna donde aparece.

Entonces obtenemos el conjunto final de restricciones de esa fila$1$debe tener$\{2,3,101\}$, fila$2$debe tener$\{2,202,203\}$, fila$3$debe tener$\{1,3,303\}$, columna$1$debe tener$\{101,2,3\}$, columna$2$debe tener$\{1,2,202\}$y columna$3$debe tener$\{3, 203,303\}$.

Entonces, si encuentra una forma rápida de verificar si se puede completar una cuadrícula con tales restricciones, puede usarla para verificar rápidamente si se puede completar un cuadrado latino, y luego puede reclamar su millón de dólares por demostrar que P = NP.