Cómo resolver Magic Puzzles

Finalmente, aquí­ va la solución prometida al problema 8 del IPST que me enviara Homero.

Les Recuerdo el acertijo:

Cada una de las piezas de la derecha contienen los números del 1 al 9. Se deben colocar estas piezas en la grilla de forma tal que los números en cada fila y en cada columna sean todos diferentes.

Intenten resolverlo antes de seguir leyendo.

Es probable que ustedes hayan tratado de solucionarlo como yo: Ver que piezas pueden ir en el centro, elegir una y ver que ocurre con las piezas vecinas. Esto que parece lógico, se termina complicando ya que las posibilidades de combinación son demasiadas.

Parece difícil... a menos que uno tenga una idea luminosa.

Nos cuenta Homero:


El problema se podí­a resolver fácilmente, tomando como punto de partida la siguiente idea: Para una pieza cualquiera del puzzle, en cada una de sus celdas siempre habrá uno de los siguientes tres números:

Esto es fácil de demostrar.
En primer lugar, para una pieza cualquiera del puzzle, denominaremos cada una de sus casillas con una letra distinta:

Supongamos que en la casilla marcada (de tipo e) va un número cualquiera, llamémoslo x.
Las dos columnas marcadas de amarillo necesariamente presentan una x cada una, y ambas x deben estar en piezas distintas. Para la tercera pieza de esas columnas, la única opción que queda para contener a x es justamente en su posición e.

De esto se puede concluir que los tres números que aparecen en la posición e, para tres piezas que forman una columna, son siempre los mismos. Mirando los números dados en el puzzle y las piezas disponibles, se concluye que estos tres números son 5, 7 y 8.
Razonando de manera análoga, se puede concluir que en la posición i sólo pueden ir los números 3, 6, y 1.

Si observamos con atención la casilla c, podemos notar que, como deben haber tres piezas horizontales juntas, esta casilla no puede valer ni 5, ni 7, ni 8. Con un razonamiento análogo para las columnas se concluye que tampoco puede valer 3, 6, ó 1. por lo tanto deben ser 2, 4 ó 9.

Razonando de forma parecida para el resto de las casillas, se concluye que los valores que cada una puede tomar son:

A partir de esta conclusión, el problema se puede resolver mucho más fácilmente. De hecho, a partir de este punto casi no es necesario volver a revisar las piezas disponibles. Lo dejo para quien quiera resolverlo a partir de allí.

Dicho por Homero