...Uno puede sentarse
y jugar al Sudoku y entretenerse con él, y
nada más. Y de hecho, esto es lo que hace la
mayoría de la gente. Pero, al mismo tiempo,
resulta desafiante pensar algunas preguntas que uno
puede hacerse alrededor del Sudoku.
a) ¿Cuántos juegos de Sudoku posibles
hay?
b) ¿Se terminarán en algún momento?
c) ¿Alcanzará para entretener a esta
generación? O en todo caso... ¿cuándo
empezarán a repetirse?
d) La solución a la que uno llega (cuando
llega a alguna)... ¿es única?
e) ¿Cuántos numeritos tienen que venir
“de fábrica” para que la respuesta
sea única? O sea, cuántas casillas tienen
que estar completas de entrada, para que uno pueda
empezar a jugar con confianza de que el problema tenga
una única solución?
f) ¿Hay un número mínimo de
datos que tienen que darnos? ¿Y un número
máximo?
g) ¿Hay algún método para resolverlos?
h) ¿Se pueden hacer Sudoku de otros tamaños?
¿Cuántos habrá de 4 x 4? ¿Y
de 16 x 16?
i) ¿Se podrán inventar Sudoku de 7
x 7? ¿O de 13 x 13? ¿Por qué
no? O, ¿por qué sí? Y en todo
caso, ¿cuadrados de cuántas filas y
columnas se pueden considerar?
En fin, hay muchísimas preguntas que uno puede
hacer, y estoy seguro que usted, mientras las iba
leyendo, pensó otras que le interesan más
a usted. Y, en realidad, eso es lo único que
importa.
Con todo, quiero aportar algunas respuestas, a las
que se puede acceder en cualquier libro que se especialice
en este pasatiempo japonés, o bien en Internet
(ver aparte algunas de las páginas más
destacadas) o incluso en la famosa revista Scientific
American que le dedicó una nota de varias páginas
en la edición que saldrá ahora, en junio
del 2006.
Algunos datos sobre el Sudoku
Me interesa antes que nada hacer algunas reflexiones
con quien está leyendo este texto. Suponga
que usted tiene resuelto uno de los Sudoku y decide
cambiar dos números de posición. Esto
es: cada vez que aparece un número uno, usted
lo cambia por un ocho. Y al revés lo mismo,
es decir, cada vez que aparece un ocho usted lo cambia
por un uno. Obviamente, aunque parezcan dos juegos
distintos, son el mismo. Es decir, como juegos, son
diferentes, pero en esencia, uno sabe que uno proviene
de otro intercambiando un par de números por
lo que cualquier dificultad que tuviera el primero,
lo tiene el segundo. Y viceversa. Ahora bien: cuando
tengamos que contar todos los Sudoku que hay, a estos
dos últimos ¿los contamos dos veces
o reconocemos que es el mismo con dos “apariencias”
diferentes?
Por otro lado, supongamos que uno tiene resuelto
un Sudoku e intercambia (sólo por poner un
ejemplo) las filas uno y tres. ¿Cambia el resultado
final? ¿Agrega o quita alguna dificultad? ¿Y
si uno intercambiara la cuarta y la quinta columnas?
¿Varía en algo el planteo inicial? ¿Se
trata acaso, de dos juegos diferentes?
Uno puede decir que sí, que son dos juegos
diferentes porque las columnas están cambiadas
o los dígitos están intercambiados.
Aceptemos esta respuesta entonces. En ese caso, si
bien es difícil calcular el número de
Sudoku sin usar algunas herramientas matemáticas
y de lógica (y por supuesto, computadoras rápidas)
el número de Sudoku que se pueden encontrar
se estima que es:
6.670.903.752.021.072.936.960 o sea, más de
6.670 trillones de posibles juegos.
En cambio, si uno restringe los casos como los que
planteé recién, y no considera distintos
a los que surgen –por ejemplo– de intercambiar
dos dígitos, o dos columnas o dos filas, entonces
el número de juegos posibles se reduce muchísimo:
5.472.730.538
o sea, un poco menos de 5500 millones. Con todo,
lo interesante de este número es que, como
dice Jean-Paul Delahaye en el artículo a punto
de aparecer en el Scientific American, es menor que
el número de personas que habitamos la Tierra,
calculado en más de 6300 millones.
Con estos datos, está claro que es difícil
que uno pueda considerar que se van a acabar los juegos
en esta generación. De hecho, creo que estamos
en condiciones de jugar tranquilos sin que podamos
llegar a descubrir alguna de las posibles repeticiones.
Otra de las preguntas pendientes, habla sobre la
unicidad en la respuesta. ¿Qué quiere
decir esto? Supongamos que a usted le dan un juego
de Sudoku que tiene repartidos ciertos dígitos
en algunas casillas. Por supuesto, no hay garantía
de que la configuración que le dieron tenga
solución. Es decir, usted podría encontrarse
con algunos datos contradictorios. Pero suponiendo
que están bien, y que no hay contradicciones,
¿cómo sabe que la solución que
encontró es la única que hay?
En realidad, esa es una muy buena pregunta, porque
al haber tantos juegos de Sudoku posibles, hay que
recurrir a una computadora para poder testear –en
general– si hay más de una solución.
Podría haber más. De hecho, ustedes
mismos pueden inventar uno de estos juegos que tenga
más de una solución.
Sin embargo, la unicidad de la solución debería
ser un requerimiento básico. Es decir: se supone
que si el juego está bien planteado, tiene
una solución única. Eso forma parte
del atractivo del Sudoku. Si no, sería como
jugar al “bingo” y, cuando uno cree que
ganó y grita “¡Bingo!”, hay
otro que “gana” junto con usted.
Ahora bien: ¿cuántos números
tienen que venir ya impresos antes de empezar el juego?
¿Los contó alguna vez? ¿Siempre
hay la misma cantidad?Lo interesante es que el número
de datos con el que ya viene cada Sudoku, varía
con el juego. No hay un número pre-determinado
que sea “el” correcto. Pero, como usted
mismo puede intuir, algunos números tienen
que aparecer porque, en el caso extremo, si no hubiera
ninguno habría muchísimos resultados
posibles. Ni bien usted pone un dígito, ya
eso hace disminuir la cantidad de posibles respuestas
y, al ir agregando cada vez más, va restringiendo
las soluciones posibles, hasta llegar a un número
de datos que garantice una solución única.
Otro problema es el que se llama la minimalidad.
Es decir, ¿cuál es el número
mínimo de datos que hay que poner para que
haya una sola solución? Hasta hoy, junio del
2006, el problema no tiene respuesta. La conjetura
más aceptada, es que hacen falta 17 (diecisiete).
Hay varios matemáticos en el mundo pensando
y discutiendo el caso, y uno de ellos, el irlandés
Gary McGuire de la Universidad Nacional de Irlanda,
Maynooth, está liderando un proyecto que trata
de probar que hay ejemplos de Sudoku que con 16 (dieciséis)
datos garantizan una solución única.
Hasta acá, según él mismo escribió,
ha fallado en el intento, y es por eso que 17 es el
número aceptado hasta hoy.
Hay muchas preguntas abiertas (sin respuesta) aún
hoy, y hay varios casos más sencillos que se
pueden atacar (4 x 4, por ejemplo). Lo que me resulta
interesante es mostrar cómo un juego tan inocente
y que sólo parece un pasatiempo, tiene detrás,
también, tanta matemática. |
