Friday, April 06, 2007

Insospechados secretos del Sudoku

Hace tiempo, mi amiga ucraniana, Marianna, me mostró un libro con cientos de problemas de Sudoku. Le dije que ya había visto ese tipo de "acertijos" pero que no le entendía realmente por qué se estaban poniendo tan de moda. Así, ella tomó el libro, lo abrió en alguna de las páginas y me enseñó cómo se resolvían dichos problemas. Fue claro que se trataba de un juego de lógica, en donde hay que asumir que en algunas casillas hay ciertos números, el cual en ocasiones no resulta cierto, y entonces hay que asumir entonces otros. Un error en una casilla puede llevar a tener que cambiar todo lo que hemos asumido y que parecía correcto. Aunque en ese momento me pareció interesante el acertijo, no me terminó por convencer. Quizás ya tengo suficiente con el ajedrez como para ahora pretender intentar esto, que sin duda, lleva su tiempo.

El objetivo del Sudoku es rellenar una cuadrícula de 9×9 celdas (81 casillas) dividida en subcuadrículas de 3×3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. Aunque se podrían usar colores, letras, figuras... Lo que importa es que sean nueve elementos diferenciados. El motivo de usar números es que se memorizan mejor. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. Un Sudoku está bien planteado si la solución es única.

Este rompecabezas numérico puede haberse originado en Nueva York en 1979. Entonces, la empresa Dell Magazines publicó este juego, ideado por Howard Garns, bajo el nombre de Number Place (el lugar de los números). Es muy probable que el Sudoku se crease a partir de los trabajos de Leonhard Euler, famoso matemático suizo del siglo XVIII. Dicho matemático no creó el juego en sí, sino que utilizó el sistema llamado del cuadrado latino para realizar cálculos de probabilidades.

Posteriormente, la editorial Nikoli lo exportó a Japón, publicándolo en el periódico Monthly Nikolist en abril de 1984 bajo el título "Sūji wa dokushin ni kagiru", que se puede traducir como "los números deben estar solos". Fue Kaji Maki, presidente de Nikoli, quien le puso el nombre. Posteriormente, el nombre se abrevió a Sūdoku (sū = número, doku = solo); ya que es práctica común en japonés tomar el primer kanji de palabras compuestas para abreviarlas.

En 1986, Nikoli introdujo dos innovaciones que garantizarían la popularidad del rompecabezas: el número de cifras que venían dadas estaría restringida a un máximo de 30 y sería "simétrico" (es decir, las celdas con cifras dadas estarían dispuestas de forma rotacionalmente simétrica). Esto no siempre se cumple en los sudokus actuales. En 1997 Wayne Gould preparó algunos sudokus para el diario The Times, que los publicó bastante más tarde, en diciembre de 2004. Tres días después, The Daily Mail publicó sus sudokus con el nombre codenumber. En 2005 muchos otros periódicos de todo el mundo empezaron a incluir sudokus a diario en sus páginas.

En el año 2005, la ICPC (International Collegiate Programming Contest) incluyó entre sus 9 problemas el Sudoku. En el año 2005 también ve a la luz el primer libro sobre Sudokus que publica un español, "Los mejores Sudokus", con 200 SuDokus agrupados en 4 niveles de dificultad, con una extensa descripción de la historia de este pasatiempo así como de sus reglas y un ejemplo paso a paso para su resolución. A este primero le siguieron 3 volúmenes más.

Una solución de un Sudoku correcta genera un cuadrado latino, el cual es una matriz de n×n elementos, en la que cada casilla está ocupada por uno de los n símbolos de tal modo que cada uno de ellos aparece exactamente una vez en cada columna y en cada fila. por ejemplo:

| a b c |
| b c a |
| c a b |

El nombre de Cuadrados Latinos se origina con Leonhard Euler quién utilizó caracteres Latinos como símbolos. Por cierto, en estos días se cumplen 300 años del nacimiento de Euler.

Un cuadrado latino se dice que esta reducido (o normalizado o de forma estandarizada) si la primera fila y la primera columna están en orden natural. Por ejemplo, el primer cuadrado esta reducido, porque la primera fila y la primera columna son a, b, c. Evidentemente, es posible hacer un cuadrado latino permutando (reordenando) las filas y las columnas.

Existen varios métodos de resolución de Sudokus. Si se desea hacerse por computadora, es claro que Prolog es el lenguaje ideal. ¿La razón? La posibilidad de backtracking (búsqueda de regreso cuando algo falla).

Dice Wikipedia: "Para los programadores es relativamente sencillo construir una búsqueda por el método de backtracking o "vuelta atrás". Ésta asignaría, típicamente, un valor (supongamos que 1, o el más cercano a 1 disponible) a la primera celda disponible (supongamos que la superior izquierda) y entonces continuar asignando el siguiente valor disponible (supongamos que 2) a la siguiente celda disponible. Esto continuaría hasta que se descubriera una duplicación, en cuyo caso, el siguiente valor alternativo se colocaría en el primer campo alterado. En el caso de que ningún valor cumpliera la restricción se retrocedería hasta la casilla anterior y se probarían los siguientes números". Y no le falta razón, pero habría que ver si se puede resolver en un tiempo finito mediante esta técnica.

Como sea, todo me hace sospechar que un programa que resuelva Sudokus es ideal para ser escrito en Prolog.

2 comments:

Yixus said...

También me parece que Prolog es una gran opción para dicho método; talvez LISP sea también cómodo. Pero como tú lo dices, me parece un algoritmo muy bruto. Sería interesante probarlo para ver si tarda menos que una persona. Haciendo un cálculo muy (MUY) somero, creo que el programa podría hacer billones de pruebas.
Cuando yo los resuelvo "a mano", no coloco ningún número que no esté 100% seguro que ahí va, de modo que nunca tengo que regresar, por eso creo que el backtracking descrito es sumamente ineficiente. No sé mucha teoría de los sudokus, pero alguna vez leí que podían resolverse con "técnicas matriciales". Del mismo modo, no sé cómo los generan (y este problema me parece más interesante, pues me pregunto si se aseguran de que exista solución única y de que ésta se pueda encontrar a mano).

Sudoku Think Outside the Box said...

Te invito a ver en facebook: Sudoku Thinking Outside The Box...donde en una manera práctica podrás resolver cualquier nivel de este interesante juego.