CONSTRUCCIÓN DE SUDOKUS A PARTIR DE CUADRADOS LATINOS

La resolucion de los famosos crucigramas numéricos conocidos con el nombre de sudokus es una afición que seduce dia a dia a miles de lectores de todo tipo de periódicos, revistas y demás prensa escrita o sitios de entretenimiento.

Desde que he sabido de la existencia de este tipo de acertijos o rompecabezas numéricos me he sentido atraido por los fundamentos matemáticos de su construcción.

Es fácil ver, cuando se han resuelto algunos de ellos, que un sudoku es simplemente un cuadrado latino. Los cuadrados latinos son viejos conocidos de los matemáticos aficionados y profesionales ya que, además de para los sudokus son también fundamentales en la obtención de cuadrados mágicos de cualquier orden y en la construcción de tablas para el diseño de experimentos.

Desde que los estudiara Leonhard Euler allá por el siglo XVIII en relación con un problema de matemáticas recreativas, los cuadrados latinos y los cuadrados grecolatinos o cuadrados de Euler, nombre con el que también son conocidos, han dado lugar a una abundante colección de resultados. En lo que sigue, vamos a mostrar algunos resultados propios mostrados ya en parte en nuestra exposición relativa a los cuadrados mágicos. Para permitir una lectura autónoma de este l tema transcribimos los conceptos fundamentales que lo sustentan

DEFINICIONES

Cuadrado Latino.- Matriz cuadrada de orden n en la que cada fila y cada columna son permutaciones de los elementos de un conjunto finito S compuesto de n elementos [3], [4].

Cuadrado Latino reducido.- (o Cuadrado Latino de forma estándar) Si los elementos de su primera fila y de su primera columna vienen dispuestos en el orden natural [3].

Transversal de un Cuadrado Latino.- Es el conjunto formado por n células o elementos del Cuadrado Latino para el que se cumple que

si : [3]


Cuadrados Latinos ortogonales.- Son un par de cuadrados latinos, , de orden n tales que:

. [3], [4]

Dos cuadrados latinos de tamaño n son ortogonales si cuando se superponen uno encima del otro, cada una de las p² parejas obtenidas ocurre una sola vez.
Un cuadrado latino A, de orden n, tiene otro ortogonal sii en A existen n transversales disjuntas.

Varios cuadrados latinos de un mismo orden se llaman ortogonales dos a dos si cualesquiera dos de ellos son ortogonales.. Un conjunto de n-1 cuadrados latinos mutuamente ortogonales (C.L.M.O.), (en inglés MOLS), se denomina completo.

Cuadrado Grecolatino.- (o Cuadrado de Euler) es el obtenido por la superposición de dos cuadrados latinos ortogonales entre si [5].

Sudoku.- Es un entretenimiento o pasatiempos matemático consistente en completar con números del 1 al n una tabla de n x n celdas (generalmente 9 x 9) de tal modo que en el resultado final ninguna fila, columna o subregión dada contenga mas de una vez alguno de los números indicados.

DESARROLLO

En primer lugar, consideramos la obtención de grupos de Cuadrados Latinos Ortogonales. Para n primo impar, consideremos un cuadrado de la forma (1) :



Conocido como matriz de Henkel [6] y que nosotros denominaremos cuadrado generatriz, por ser el origen de los demás ortogonales a él y también de otros conjuntos completos.

Para construir (n-2) Cuadrados Latinos Mutuamente Ortogonales entre sí y con A, obtenemos las imágenes



de los elementos de la primera columna de A considerando dicha tabla como la de multiplicar de un grupo.

La columna formada con cada conjunto de imágenes, , será la que indique la permutación que debemos realizar con las filas de A para obtener un cuadrado latino ortogonal con A.

Podemos ver que existen diversos conjuntos completos de Cuadrados latinos mutuamente ortogonales de orden 5, observando que las primeras columnas de los 4 cuadrados que forman el conjunto obtenido pueden hacerse corresponder con otros tantos elementos del grupo de las sustituciones S₄, que tiene 4! = 24 elementos.

Si p es un primo distinto de 2,un método sencillo de implementar para n = p² y que ilustramos para p = 3 n = 9, es el siguiente : Consideramos el cuadrado Ap de la ecuación G y su transformada (p-1)-ésima, junto con un cuadrado formado por los elementos 1 a n = p²



Como cuadrado latino inicial consideramos (*):



Para el que puede verse que está formado como producto directo de dos cuadrados latinos iguales de orden p = 3.
Un conjunto completo de C.L.M.O. de orden n = p² se obtiene con la siguiente pauta : Se toman los elementos 1 a n = p² de la primera columna y se colocan en una sola fila : 1 2 3 4 5 6 7 8 9

Ese sería el orden de las filas para el primero de los cuadrados latinos. El siguiente, obtenido a partir de él , se formaría reordenando como sigue el cuadrado formado por los p² elementos :

Formación de la 1ª columna

De la fila 1 se toma el elemento 1 1
De la fila 2 se toma el elemento 2 5
De la fila 3 se toma el elemento 3 9

Formación de la 2ª columna

De la fila 2 se toma el elemento 3 6
De la fila 3 se toma el elemento 1 7
De la fila 1 se toma el elemento 2 2

Formación de la 3ª columna

De la fila 3 se toma el elemento 2 8
De la fila 1 se toma el elemento 3 3
De la fila 2 se toma el elemento 1 4

Tenemos así el esquema :



Sobre el que podemos aplicar de nuevo el algoritmo anterior, y así sucesivamente, para obtener el conjunto :

{A = {1, 2, 3, 4, 5, 6, 7, 8, 9};
B = {1, 5, 9, 6, 7, 2, 8, 3, 4};
C = {1, 7, 4, 2, 8, 5, 3, 9, 6};
D = {1, 8, 6, 5, 3, 7, 9, 4, 2};
E = {1, 3, 2, 7, 9, 8, 4, 6, 5};
F = {1, 9, 5, 8, 4, 3, 6, 2, 7};
G = {1,4,7,3,6,9,2,5,8};
H = {1,6,8,9,2,4,5,7,3}}

Cuyos elementos nos dan el orden de las filas para cada uno de los n-1 C. L. ortogonales de orden 9.
Es interesante resaltar que añadiendo al conjunto anterior el elemento {1,1,1,1,1,1,1,1,1} y considerando el producto :


donde cada componente c_i se obtiene por el producto de los componentes a_i y b_i de acuerdo a la tabla de multiplicar representada por el cuadrado latino inicial, tenemos un grupo multiplicativo finito de orden 9. Lo anterior se cumple para otros conjuntos completos de Cuadrados Latinos Mutuamente Ortogonales.

Pueden verse otros resultados en los artículos titulados "Cuadrados latinos para obtener cuadrados mágicos" y "Cuadrados mágicos a partir de cuadrados latinos"

Con el desarrollo teórico expuesto, casi tenemos ya los fundamentos para poder construir una tabla base para diversos sudokus de orden 9. Nos falta únicamente ver como resolvemos la restricción de que en determinadas subtablas de orden 3 no se repita ninguno de los dígitos del 1 al 9.

A partir de un cuadrado latino como el señalado por (*) y de otro ortogonal a él, como por ejemplo:



Podemos obtener sin dificultad una tabla base para la construcción de numerosos sudokus.

Consideramos el cuadrado latino inicial:




Y una tabla vacía de 3 x 3 subtablas de 3 x 3 celdas (numeradas según el esquema representado en la figura adjunta)



Y sobre las que vamos colocando los elementos de acuerdo al orden marcado por el cuadrado ortogonal considerado.



Esto es, tomando las columnas del cuadrado latino ortogonal al de inicio, el primer uno se coloca en la posición 1 del cuadrado uno, el segundo 1 en la posición 8 del cuadrado dos, el tercer uno en la posición 6 del cuadrado tres, y así sucesivamente



hasta llegar al final:



Si permutamos varios elementos entre si, como por ejemplo el 1 con el 7 y el 3 con el 5, dentro de todas y cada una de las subtablas, añadiremos dificultad al juego.



Borrando en cada subtabla una cantidad determinada de celdas tendremos ya dispuesto un sudoku para que lo resuelva alguno de nuestros familiares, amigos o alumnos:



Finalmente y para completar la jugada, a continuación te ofrecemos la posibilidad de jugar al sudoku en línea durante el tiempo que quieras (pero controlando que no sea mucho pues hay otras cosas que hacer)

BIBLIOGRAFIA

[1] "Mathematical Recreations & Essays" de W. W. Rouse Ball y H. S. M. Coxeter

[2] "Problemas y experimentos recreativos" de Ya. I. Perelman.

[3] "Análisis Combinatorio" de K. Ribnikov, Editorial Mir.

[4] "Matemática Discreta" de N. L. Biggs, Editorial Vicens Vives.

[5] "Nuevos pasatiempos matemáticos" de M. Gadner, Alianza editorial.

[6] "Special matrices and their applications in numerical mathematics" de M. Fiedler.