Técnicas de Resolución de Sudokus

Historia del sudoku

Es muy difícil, quizás imposible, fijar la fecha y el lugar exactos en los que el concepto original de Sudoku empezó, pero parece estar ligado a la apareció del primer "Magic Squares" (Cuadrados Mágicos). 

De acuerdo con la revista on-line "Convergence", la idea del cuadrado mágico fue transmitida a los árabes por los chinos, probablemente a través de la India, en el siglo VIII. Fue tratado por Thabit ibn Qurra, conocido por su fórmula para "números amistosos", a principios del siglo IX. Una lista de cuadrador de todos los órdenes desde 3 a 9 se muestra en La Enciclopedia, recopilada alrededor del año 990 por un grupo de eruditos árabes conocidos como Ikhwan al-safa (hermanos de la pureza). Por aquel entonces no aparecieron métodos generales de construcción. 

En 1225, coincidiendo con lo mencionado arriba, Ahmed al-Buni mostró cómo construir Cuadrados Mágicos mediante una sencilla técnica de bordeado, pero puede que él no descubriera el método sólo. Biggs, en referencia a un papel de Camman, sugiere que los métodos explicados por Moschopoulos deben tener origen Persa y estarían relacionados con los explicados por al-Buni. 

En cambio, Camman alega que los dos métodos dados por Moschopoulos para la construcción de cuadrados mágicos impares eran conocidos por los persas, citando un manuscrito Persa anónimo (Garrett Collection no. 1057, Universidad de Princeton). Aún así, este documento contiene ejemplos pero no métodos explícitos. 

Cuadrados Mágicos en la literatura Islámica 

De acuerdo con manuscritos médicos islámicos de la Biblioteca Nacional de Medicina, la primera aparición del Cuadrado Mágico (conocido en árabe como wafq) en la literatura islámica se da en el Jabirean Corpus (un grupo de escritos atribuidos a Jabir ibn Hayyan - conocido en Europa como Gebber -) y que generalmente se piensa que fueron escritos a finales del sigo IX o principios del X después de Cristo. 

El Jabirean Corpus recomendaba los Cuadrados Mágicos como hechizos para facilitar el nacimiento de niños- Estos cuadrados consistían en nueve celdas con los números del 1 al 9 ordenados con 5 en el centro de forma que el contenido de cada fila, columna y las dos diagonales sumaran 15. Los números estaban escritos en el abjad letter-numerals, y debido a que las cuatro esquinas contenían las letras ba', dal, waw [o "u"] y ha', este cuadrado en concreto se conocía como el cuadrado buduh. Al mismo tiempo, el concepto de Cuadrados Mágicos llegó a ser tan popular que se asignó propiedades de talismán al nombre buduh. 

En los años posteriores, los escritores islámicos desarrollaron una gran variedad de métodos para la formación de Cuadrados Mágicos más grandes, en los que no se repetía ningún número y en los que las sumas de cada fila, columna o diagonal eran las mismas. Eran particularmente populares los Cuadrados Mágicos con celdas de 4x4, 6x6 o 7x7, siendo los cuadrados de 10x10 producidos en el siglo XIII. También parece que los Cuadrados Mágicos pudieron haber sido introducidos en Europa a través de España por Abraham Ben Meir ibn Ezra (c. 1090-1167), astrólogo y filósofo hispano-judío. 

Ben Meir ibn Ezra tradujo varios trabajos árabes al hebreo y tuvo mucho interés en los Cuadrados Mágicos y la numerología en general. Viajó extensamente por Italia y más allá y debe haber sido una de las personas responsables de la introducción de los Cuadrados Mágicos en Europa. 

De los Cuadrados Mágicos a los Cuadrados Latinos y Greco-Latinos 

El concepto de Cuadrados Latinos se conoce por lo menos desde los tiempos medievales. Manuscritos árabes del siglo XIII se refieren a veces a los primeros Cuadrados Latinos, a menudo dándoles importancia mística "Kabblahlica". 

Un Cuadrado Latino, conocido en árabe como wafq majazi, es un cuadrado que contiene celdas en el cual cada fila y cada columna tienen el mismo conjunto de símbolos, a diferencia del cuadrado mágico, en el que no hay repetición. Este conjunto de eventos continúa con el matemático y físico suizo Leonhard Euler (1707-1783). De acuerdo con el Archivo Euler, en su obra "De quadratis magicis" (En los cuadrados mágicos), presentada a la academia de San Petersburgo el 17 de octubre de 1776, Euler mostraba como construir Cuadrados Mágicos con un cierto número de celdas, en particular 9,16,25 y 36. 

En este documento, Euler empieza con los cuadrados Greco-Latinos y hace hincapié en los valores de las variables de forma que el resultado es un Cuadrado Mágico. El nombre de Cuadrados Latinos, sin embargo, es debido a un manuscrito de Euler sobre los Cuadrados Latinos, llamado "Recherches sur une nouvelle espece de quarre magique" (Investigaciones de una Nueva Especie de Cuadrados Mágicos). Euler puso letras del latín en una rejilla y lo llamó Cuadrado Latino. Posteriormente, cuando se añadieron letras griegas, se llamó cuadrado Greco-Latino. 

Mientras dedicaba los últimos años de su vida trabajando con las diferentes posibilidades de los Cuadrados Mágicos, Euler se encontró con el especial problema de combinar dos conjuntos de n símbolos cada uno de forma que en ninguna fila o columna se repitieran una pareja de símbolos. Demostró métodos para la construcción de Cuadrados Greco-Latinos en los que n es impar o un múltiple de 4. Observando que no existen cuadrados de orden 2 y sin poder construir un cuadrado de orden 6, conjeturó que no existían cuando n ? 2 (mod 4). 

La no-existencia de cuadrados de orden 6 fue confirmada de forma definitiva en 1901 por el matemático francés Gaston Tarry, a través de una enumeración exhaustiva de todas las posibles combinaciones de símbolos. Fue 58 años después, en 1959, y con la ayuda de ordenadores, cuando dos matemáticos americanos, Bose y Shrikhande, encontraron algunos contraejemplos a la conjetura de Euler. El mismo año, Parker encontró un contraejemplo de orden 10. En 1960, Parker, Bose y Shrikhande demostraron que la conjetura de Euler era falsa para todos los n >= 10. De esta forma, los Cuadrados Greco-Latinos existen para cualquier orden n >= 3 excepto n = 6. 

El nacimiento del Sudoku como lo conocemos hoy 

Los rompecabezas Sudoku son, en realidad, un caso especia de los Cuadrados Latinos; cualquier solución de un Sudoku es un Cuadrado Latino. El Sudoku impone la restricción adicional de que los subgrupos de 3x3 deben contener también los dígitos 1-9 (en la versión estándar). 

Este tipo particular de rompecabezas, tal y como lo conocemos, se publicó por primera vez al final de la década de los 70 en la revista "Math Puzzles and Logic Problems" (Rompecabezas Matemáticos y Problemas Lógicos) de Dell Magazines. El nombre que Dell le dio a estos rompecabezas fue "Number Place", que es como dicha compañía los ha seguido nombrando hasta hoy. Dell tomó el concepto de Cuadrado Latino de Euler y lo aplicó a una rejilla de 9x9 con la adición de nueve subrejillas o cajas, cada una de las cuales contiene todos los números del 1 al 9. 

Como vemos, el concepto de Sudoku no se inventó en Japón, como mucha gente cree, pero sí que lo fue el nombre. En 1984, Nikoli, la compañía líder en creación de puzzles de Japón, descubrió los "Number Place" de Dell y decidió presentarlos a los fans japoneses de los rompecabezas. Los rompecabezas, que inicialmente se llamaron Suuji Wa Dokushin Ni Kagiru ("los números deben ser únicos" o "los números deben existir sólo una vez") pronto se volvieron muy populares. 

En 1986, después de añadir muchas mejoras, sobretodo creando patrones simétricos y reduciendo el número de pistas que se daban, el sudoku llegó a ser una de los rompecabezas más vendidos en Japón. Cuando se dio cuenta que uno de los principales problemas del Sudoku era su largo nombre, Kaji Maki, el presidente de Nikoli, lo abrevió a Sudoku (Su = número, dígito; Doku = único, soltero). Hoy en día hay más de 600.000 copias de revistas de Sudoku publicadas mensualmente en Japón. En todo ese tiempo, prácticamente nadie en Europa conocía o había prestado atención a los Sudokus. 

Ralentizando la progresión del Alzheimer 

A finales de 2004, Wayne Gould, un juez retirado de Hong Kong, fan de los rompecabezas y programador, visitó Londres intentando convencer a los editores de "The Times" que publicaran Sudokus. Gould, que había escrito un programa de ordenador que generaba Sudokus de diferentes niveles de dificultad, no pedía dinero por los rompecabezas. 

El Times decidió darle una oportunidad y el 12 de noviembre de 2004 publicó su primer Sudoku. La publicación de un Sudoku en el "London Times" fue sólo el principio de un enorme fenómeno que rápidamente se extendió por toda Gran Bretaña y países como Australia y Nueva Zelanda. Tres días después, el "Daily Mail" empezó a publicar Sudokus con el nombre "Codenumber". El Daily Telegraph de Sydney los siguió el 20 de Mayo de 2005. 

A finales de mayo de 2005 el rompecabezas se publicaba de forma regular en varios periódicos nacionales del Reino Unido, incluyendo "Daily Telegraph", "The Guardian", "The Sun" y "The Daily Mirror". Pero eso no fue todo. En julio de 2005, el Canal 4 incluyó un Sudoku diario en su teletexto y Sky One lanzó el Sudoku más grande del mundo (un Sudoku cuadrado de 84 metros tallado en una cara de una colina en Chipping Sodbury, cerca de Bristol). La BBC Radio 4's Today empezó a leer números en voz alta en la primera versión radiofónica del Sudoku. 

Famosas celebridades británicas, como Big Brother's Jade Goody y Carol Vorderman (cuyo libro "Cómo hacer Sudoku" es el libro más vendido en el país), han declarado sus beneficios como entrenamiento mental. Incluso la revista "Teachers", financiada por el gobierno, recomienda el Sudoku como un ejercicio mental en las clases y se ha insinuado que la resolución de Sudokus puede ayudar a frenar la progresión de enfermedades como el Alzheimer. 

De vuelta a Manhatan 

En abril de 2005 el Sudoku completó el círculo volviendo a Manhattan como un elemento habitual del New York Post. El lunes 11 de julio, se extendió la moda del Sudoku a otras partes de EEUU cuando tanto el "The Daily News" como el "USA today" lanzaron Sudokus el mismo día. 

En ambos casos los sudokus aparecían en lugar de los crucigramas tradicionales. Hoy en día hay clubes de Sudoku, chats, libros de estrategia, videos, juegos para móviles, juegos de cartas, competiciones e incluso un programa de televisión. El Sudoku ha aparecido en los periódicos de todo el mundo y se le describe en los medios de todo el mundo como "el cubo Rubik del siglo XXI" y como el "rompecabezas que más rápido ha crecido del mundo". 

El Sudoku es un rompecabezas que se resuelve mediante lógica (no son necesarios ni adivinar ni la aritmética). La idea básica para completar los rompecabezas es encontrar celdas para las que conocemos un único candidato.

Lo Básico

Las reglas del Sudoku son que debemos rellenar con un número cada celda de la cuadrícula, utilizando los números del 1 al 9. Las restricciones son que sólo podemos usar cada número una sola vez en cada fila, cada columna y cada uno de los recuadros de 3x3.

Echemos un vistazo a este puzzle incompleto...

Los tres interrogantes se encuentran en sitios en los que no hay ningún valor, pero en los que fácilmente podemos encontrar un número para cada uno. Si el resto de la línea o recuadro está completo, con un simple proceso de eliminación sabremos cual es el valor que falta. 

En este caso, el único número que falta de la fila horizontal es el 3. 

El número que falta en la columna es el 9. 

En del recuadro es un 4.

Técnicas Fáciles

La mayor parte de Sudokus de los que podemos encontrar en los periódicos se pueden resolver con dos sencillas técnicas:

• Técnica 1: Posición Única

• Técnica 2: Candidatos Únicos

Marcar las Casillas

Muchos de los jugadores de Sudoku en papel tienden a utilizar sus propios sistemas para ayudarse a completar los Sudokus. Muy pocos son los que completan la cuadrícula escribiendo directamente los números finales. La forma más común de marcar las casillas es escribir pequeños números (que normalmente se llaman "marcas de lápiz") que en realidad significan "este número sigue siendo posible para esta casilla". Podemos llegar a la conclusión que una celda sólo puede contener el "5 y el 8" pero no cual de los dos. Si escribimos un pequeño 58 en la celda, seguramente después encontraremos otro lugar que nos permita eliminar una de las marcas (5 u 8). De esta forma, si elimináramos el 5, sabríamos que esta celda sólo podría contener el 8, de forma que podremos borrar ambas marcas y escribir un 8 más grande.

No es necesario rellenar todas las marcas (los buenos jugadores piensan que esto les ralentiza en los puzzles más fáciles, pero lo necesitan hacer en los puzzles más difíciles).

Muchas de las siguientes técnicas no proporcionan una posición directa, pero nos pueden ayudar permitiendonos eliminar alguna de las marcas.

La utilización de las marcas hace muy sencillo encontrar los Candidatos Únicos (ver el 3 del bloque de 3x3 de arriba a la derecha).

En playSudoku.biz tenemos una herramienta dedicada especialmente a esto, llamada"marcadores" que es muy similar a las marcas de lápiz, con la ventaja de no tener que utilizar la goma de borrar.

Técnicas Medias

Yendo un poco más lejos, hay algunas técnicas extra que nos pueden ayudar a encontrar emplazamientos válidos o a eliminar algunas de las marcas. Obviamente, éstas son difíciles de utilizar sin las marcas en lápiz.

• Técnica 3: Líneas de Candidatos

• Técnica 4: Parejas dobles

• Técnica 5: Líneas múltiples

Técnicas Avanzadas

Siguiendo la progresión, podemos encontrar otras técnicas para ayudarnos en la resolución.

• Técnica 6: Parejas o Tripletas Desnudas

• Técnica 7: Parejas o Tripletas Escondidas

Técnicas de Maestro

Una vez dominadas las anteriores técnicas, podemos ir un poco más lejos y aplicar técnicas más complicadas.

• Técnica 8: X-Wing

• Técnica 9: Swordfish

• Técnica 10: Forcing Chains

Todavía Más Difícil

Conociendo ya estas técnicas, ¿seremos capaces de resolver todos los posibles Sudokus? Bueno, talvez si, tal vez no. La gran mayoría de rompecabezas no requieren las técnicas más complicadas, pero hay algunos que no se pueden resolver simplemente con lógica, y que requieren algún tipo de "adivinación" para resolverlos. Algunos argumentan que la adivinación es una forma de lógica.

Nishio es una forma de adivinacion, en la que vemos una adivinación que causa una contradicción, significando que podemos eliminarla. Continuando con esto, es posible resolver Sudokus completos a partir de adivinaciones, pero nos puede costar mucho.

• Técnica 11: Nishio

• Técnica 12: Adivinación

Resolución por ordenador

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.

Aunque lejos de la eficiencia computacional, este método encontrará la solución si se permite el suficiente tiempo de computación. Un programa más eficiente podría dejar una huella de valores potenciales para las celdas, eliminando valores imposibles hasta que sólo un valor quedase para una celda determinada. Entonces se rellenaría esa celda y se usaría esa información para más eliminaciones y así, sucesivamente hasta el final. Esto emularía más exactamente lo que un resolutor humano haría sin el método de ensayo y error.

Codificar la búsqueda para imposibilidades basadas en contingencias e incluso múltiples contingencias (como sería requerido para los Sudoku más difíciles) es bastante complejo de construir a mano. De cualquier modo, tales complicaciones son innecesarias si todo lo que el programador desea hacer es encontrar una solución eficientemente. Una forma más eficiente de construir soluciones involucra herramientas de programación más avanzadas.

Algunos programas así construidos, que emulan la resolución humana, permiten estimar la dificultad que tendrá un humano para encontrar la solución.