lunes, 13 de febrero de 2006

Sudokumanía

Hoy hace un año que volví de Japón (es fácil acordarse porque el Windsor estaba ardiendo). Lo más curioso es que cuando estuve allí, había esos pasatiempos que eran como un cuadrado de nueve cuadrados con números por dentro. Yo me los estuve mirando un rato y pensé: esto a mí se me tendría que dar bien, si supiera qué restricciones tienen que cumplir los números.

Hoy, los sudoku nos rodean por doquier. Cómo puede haber ocurrido esto en menos de un año, no lo entiendo. Será el poder de los mass media (digo yo).

Lo más gracioso es que ya venden máquinas y programas para hacer sudoku. Vienen todos con simpáticos rótulos "Más de un millón de sudokus", "Más de cien mil sudokus" (a todo esto, los sudokus son como los raviolis, como lo digas correctamente todos los camareros te corrigen).

La pregunta es: ¿Cuál es el orden del grupo de simetrías de un sudoku?

O, dicho en lenguaje llano: si tenemos un sudoku que hemos copiado del periódico, ¿de cuántas formas podemos alterarlo mecánicamente para seguir obteniendo sudoku correctos? Es decir, ¿cuántos sudoku hacen falta realmente para poder generar un millón? ¿Quizás cien mil? ¿Ochenta mil? ¿Cuatrocientos veinte? ¿Doce? ¿Uno?

Bien, tenemos tres estrategias obvias: (a) cambiar unos números por otros, (b)reordenar filas o columnas y (c) darle vueltas al cuadrado.

(a) Si cambiamos todos los doses por ochos, los treses por cincos, etcétera, ¿seguiremos obteniendo un sudoku correcto? La respuesta es fácil notando que basta saber si intercambiar los unos con los nueves, por ejemplo, proporciona un nuevo sudoku correcto (porque todo elemento del grupo simétrico se escribe como producto de permutaciones de dos elementos, Sr. R, que no se acuerda usted del Álgebra II).

Eso está claro, porque en cada fila, en cada columna y en cada cuadro sólo hay un 1 y un 9; así que si los intercambiamos sigue habiendo un 1 y un 9, y todos los demás no los hemos tocado. Esto nos da un total de 9! renumeraciones.

(b) Si cambiamos de orden un bloque de tres filas con otro, entonces nada queda alterado: 3! ordenaciones distintas.
Si cambiamos un bloque de tres columnas con otro, lo mismo: 3! ordenaciones.
Dentro de cada bloque, también podemos permutar las tres filas o tres columnas que lo componen, eso nos da 3 bloques de 3! ordenaciones para las filas y otro tanto por columnas.

(c) Finalmente podemos rotar el cuadrado grande 4 veces. De esas 4, dos se pueden obtener como productos de las transformaciones que ya hemos hecho.

En total tenemos de esta forma 9! 3! (3! 3! 3!) 3! (3! 3! 3!) 2 sudoku "distintos", que son, tras un par de cuentecillas, algo más de 2 por 6^10 por 10^4. Y usando el logaritmo de 2 y el de 3 (o la calculadora de Windows, que es más prosaico), eso es 10^12,082, es decir, más de un billón.

Por lo que perdonen que no me sienta impresionado por el "millón de sudokus" que nos ofrece la máquina.


4 comentarios:

Jago dijo...

He a este momento encontrado su blog, tengo que ir ahora pero voy a leerlo manana, y muchas gracias por su link (no hablo espanol bien)

Pedro Terán dijo...

You needn't thank me! Your blog is pretty interesting, and I take this opportunity to recommend everybody to give it a chance.

(El enlace está en la columna de la derecha)

Sr. R dijo...

Efectivamente, el Sr. R tiene batante olvidada el álgebra II. Supongo que el trauma de haber padecido la asignatura produce una amnesia piadosa que borra todos los malos tragos.

"Uyyyyy, casi apruebas. Yo creo que con un pequeño empujón más..." (Santos González en Junio del 95 y Consuelo Martínez en Junio del 97)

Pedro Terán dijo...

Hay que ver. Con esa actitud, no creo que llegue nunca a colaborar con Efim Zelmanov.

Tendrá que conformarse con una buena briónisis de vez en cuando.