 |
| Sudoku "difícil" resuelto por el autor |
En este período estival pasado, en que he comprado bastantes días el periódico local en papel (es curioso que haya que especificar esto), he dedicado algunas horas, bolígrafo en ristre, a resolver los sudokus que suele traer en sus páginas de pasatiempos.
En casi todos aparece una leyenda tipificándolos de "FÁCIL", "MEDIO" o "DIFÍCIL". Y un día me pregunté: ¿y cómo sabe el que da las pistas para resolverlo su nivel de dificultad? y, más ampliamente: ¿cómo se construyen los sudokus para saber que tienen solución (una o varias)? Y me puse a buscar las respuestas. No pensaba yo que me iba a adentrar en un curioso mundo de combinaciones y algoritmos (ahora que la palabreja está tan de moda). Vamos a ello.
Lo primero es constatar que el sudoku, entendido como pasatiempo, es un "invento" relativamente moderno. En el formato que ahora conocemos (el cuadrado de 9x9 con todas sus reglas) apareció por primera vez en 1979 en la publicación americana Dell Magazines, obra del arquitecto jubilado Howard Garns, y con el nombre de "Number Place". Al morir su creador en 1989, dejó de publicarse. Pero, en 1984, Maki Kaji, presidente del grupo japonés Nikoli, llevó la idea a Japón, se supone que encontró a alguien capaz de generar nuevos cuadrados y empezó a publicarlo en el Monthly Nikolist. De hecho, su nombre actual procede del japonés "Sūji wa dokushin ni kagiru" (数字は独身に限る) "los números deben ser únicos".
 |
| Primer sudoku en "The Guardian" 15 de mayo de 2005 |
"En 1997, el juez neozelandés residente en Hong Kong, Wayne Gould, vio un rompecabezas a medio terminar en una librería japonesa. Durante seis años, desarrolló un programa informático para producir rápidamente rompecabezas únicos. Sabiendo que los periódicos británicos tenían una larga trayectoria en la publicación de crucigramas y otros acertijos, promovió el Sudoku en The Times en Gran Bretaña, que lo lanzó el 12 de noviembre de 2004 (llamándolo Su Doku)... Los sudokus se extendieron rápidamente a otros periódicos como artículo habitual".
En España, el primer sudoku lo publicó "El Mundo" en su suplemento Magazine del domingo 5 de junio de 2005, y pasó al diario dos semanas después. (Es curioso que, comentándolo con amigos y conocidos, a casi todos nos parecía que el sudoku había aparecido en los periódicos españoles años antes de 2005).
Rápidamente se extendió a otros periódicos. "El Correo", por ejemplo, lo hizo el 31 de julio de 2005, con este sugestivo titular:
 |
Primer sudoku de "El Correo" |
Y, efectivamente, después de conocer la historia, vamos a hablar de lógica, algoritmos y matemáticas. Aunque, en sentido estricto, el sudoku tiene poco de matemáticas entendidas como cálculo; de hecho, puede hacerse un sudoku con 9 colores o 9 símbolos diferentes que no sean números (la razón que se esgrime para el éxito del sudoku en Japón es que los pasatiempos en japonés que usan letras=caracteres kanji, como los crucigramas, son muy difíciles de resolver si no tienes una gran destreza lectora/escritora en ese idioma). Lo que sí hay es mucha lógica.
Pero ya se ha comentado más arriba que, en 1997, Wayne Gould desarrolló un programa informático para agilizar los cálculos y obtener muchos sudokus "válidos".
En el magnífico artículo de Jean-Paul Delahaye titulado "The Science behind Sudoku", publicado en la revista Scientific American de junio de 2006 se da el siguiente algoritmo para resolver cualquier sudoku (puedes leer el artículo completo aquí):
"Los programas de búsqueda de soluciones pueden emplear varios métodos, pero el más común es el retroceso (backtracking), una forma sistemática de prueba y error en la que se proponen soluciones parciales y luego se modifican ligeramente tan pronto como se demuestra que son erróneas.
El algoritmo básico de retroceso funciona así: el programa coloca el número 1 en la primera celda vacía. Si la elección es compatible con las pistas existentes, continúa a la segunda celda vacía donde coloca un 1. Cuando encuentra un conflicto (lo que puede ocurrir muy rápidamente), borra el 1 que acaba de colocar e inserta un 2 o, si también es inválido, un 3 o el siguiente número válido. Después de colocar el primer número válido posible, pasa a la siguiente celda y comienza nuevamente con un 1. Si el número que se debe cambiar es un 9 (que no se puede aumentar en uno en una cuadrícula de Sudoku estándar), el programa retrocede y aumenta el número en la celda anterior (el penúltimo número colocado) en uno. Luego avanza hasta encontrar un conflicto. (El programa a veces retrocede varias veces antes de avanzar)
En un programa bien escrito, este método explora exhaustivamente todas las hipótesis posibles y así termina por encontrar la solución, si existe. Y si existen múltiples soluciones, como sería el caso de un sudoku "defectuoso", el programa las encuentra todas".
Si te ha resultado un poco farragosa la lectura del método y no acabas de ver claro que lleve a un final exitoso, yo también dudé. Pero, para un curioso, no hay nada como un reto. Así que, armado de lápiz y goma de borrar decidí aplicarlo a uno de los sudokus publicados. Eso sí, elegí uno catalogado como "FÁCIL" por si ayudaba en la resolución. Te anticipo que no llegué hasta el final del algoritmo, pero la experiencia fue curiosa. Observa la foto:
A la izquierda está mi aplicación del método iterativo. Como ves, llegué hasta la 7ª fila completando números de forma válida, eso sí, borrando y yendo hacia atrás en muchas ocasiones. Pero, después del 7, en la siguiente casilla vacía sólo encajaba el 9. Y eso obligaba a que en la siguiente fuera un 1, incompatible con el 1 de su columna. O sea, que había que borrar e ir hacia atrás...
Decidí entonces completar el sudoku aplicando mi método habitual, para ver dónde estaba el error. Y lo puedes ver a la derecha. En el cuadrado derecho de la segunda fila, el orden correcto era "7-5-4" en lugar del "4-5-7" que había resultado en una de mis iteraciones. Curiosamente, los bloques izquierdo y central coinciden al 100%, y es solo el bloque de la derecha el que cambia.
O sea, que el algoritmo funciona, pero se necesita la potencia de iteración de un ordenador (y su infinita paciencia) para llegar a las soluciones.
Y esa es una buena pregunta: ¿cuántos sudokus posibles hay? Ya hay quien lo ha calculado matemáticamente y la respuesta es descomunal: 5.472.730.538, más de 5.000 millones (eliminando lo que se llaman configuraciones equivalentes, como las que resultan de intercambiar el orden de algunas filas o columnas, por ejemplo). O sea que no hay problema de "suministro" de sudokus.
En cuanto a la catalogación de un sudoku en FÁCIL, MEDIO o DIFÍCIL, no tengo tan claro cómo se hace. La misma duda le surgió a Nuha Nishat, estudiante de Robótica en la Universidad del Estado de Oregón. En 2020 hizo un programa en Python para aplicar el método de backtracking en los sudokus publicados. Aplicó su programa a 4 sudokus, uno de cada nivel de dificultad, y estos fueron los resultados:
Como era de esperar, el sudoku FÁCIL no necesitó muchos "retrocesos": 121. Pero el que mayor número de retrocesos necesitó fue el catalogado como MEDIO (17.281). Muchos más que el DIFÍCIL (10.364) y que el ENDIABLADO (8366). La propia Nuha se mostraba sorprendida por estos resultados y prometía nuevas pruebas (artículo completo aquí), aunque no he visto que publicara nada más sobre el tema.
Para terminar, una imagen de cómo sería un sudoku de 9 colores resuelto; el de la izquierda solo con los colores y el de la derecha uno diferente, con colores y números, que facilita la comprobación:
_____________________________________________________________
Posdata: Diferentes investigaciones científicas sugieren que la realización de crucigramas o sudokus son excelentes para potenciar la acción cognitiva del cerebro. En este sentido, podrían ayudar a prevenir enfermedades mentales como la demencia o el Alzheimer. ¡Oído cocina!
______________________________________________________________
Suelo resolver sudokus, comodamente sentado en la baza, para ayudarme a transitar por el esteñimiento. Si son muy dificiles tengo que echar mano del tanteo, como los PCs.
ResponderEliminarRaras veces los resuelvo en una sola sesion y, segun su dificultad, puedo necesitar hasta 5. Asi que los clasifico en 2, 3 o 4 kakas.
Mas de una vez me he planteado cual es la configuracion minima (datos-colocacion) necesaria para una solucion unica (teorema de existencia y unicidad!). Mi conjetura es que hacen falta 9 cifras distintas, sin coincidir ni en fila, ni en columa ni en cuadrado 3x3
Querido anónimo escatológico: En el artículo de la Scientific American que se menciona en el post, se dice que se ha demostrado (no me preguntes cómo) que el mínimo número de números que, dados en una configuración inicial, garantizan una solución única son 17.
EliminarMe extrañaba que hasta ahora no hubieras hecho sudokus. LLevo haciéndolos desde su aparición en España y puedo asegurar que hacer al menos uno al día ayuda a mantener la mente activa. He podido comprobar que no todos tienen la misma "calidad", al margen de que pongan que son fáciles, difíciles o muy difíciles; los que publica El País me parecen muy buenos y se nota en la satisfacción que te queda cuando lo resuelves. Según vas cogiendo el hábito vas creando tu propio método, que en ningún caso tiene una mecánica tan definida como lo que apuntas, pero acaba siendo efectiva. Puedo vanagloriarme de hacerlos directamente a bolígrafo y que enseñé a mi suegra cuando tenía 85 años y está enganchada, aunque no con los más difíciles, lo que demuestra que no hay edad ni conocimientos previos que impidan meterse en este mundo.
ResponderEliminarEntre los crucigramas, que también me gustan si son buenos, y los sudokus creo que me quedo con los sudokus. Ánimo y a por ellos. Un abrazo.
Recuerdo, Carmelo, cómo cuando había un tiempo entre clase y clase en la Facultad, nos dedicábamos a resolver un pasatiempo de El País, no recuerdo el nombre ni muy bien en qué consistía, pero en el que tú siempre ganabas...
EliminarOtro artículo interesante para el grupo de salvajes nómadas que te siguen en busca de satisfacer sus ansias de conocimiento. Antes de los smartphones, resolver sudokus era mi forma de entretenimiento habitual en la playa bajo la sombrilla. También desarrollé mi propio método, que posiblemente coincida con el método ADM con tres o cuatro reglitas para ir colocando números en los espacios vacíos. Pero llega un momento en que tengo que apostar por un número de dos posibles; hay un número significativo de sudokus en que ambos números son válidos y dan una solución diferente del sudoku, aunque parecidas. Si tuviera que catalogar un sudoku como fácil, medio o difícil, lo haría en base a dos parámetros. Primero el número inicial total de números que aparecen. Por ejemplo en el fácil que presentas, hay 33 números puestos. Segundo el número de cuadrados vacíos o con un solo número. Cuantos más cuadrados vacíos, más posibilidades hay que elucubrar si no dispones de un libro de sudokus resueltos en el que puedas encontrar una analogía intercambiando filas, columnas o haciendo una trasposición. Uy, que escribir de esto me devuelve a la playa y estoy llenando de arena el teclado. Un abrazo.
ResponderEliminarVaya, parece que hay cierta correlación entre sudokus y Carmelos...
EliminarA mí también me ha pasado llegar a un punto de "bifurcación" en el que hay que elegir... lo que hago en esos casos es seguir con lápiz para, si llego a un callejón sin salida, dar marcha atrás, borrar números y probar la otra alternativa.
Empecé con Sudokus, pero hace mucho tiempo que me pasé al Sudoku Killer (en lugar de darte celdas resueltas como pista, te dan la suma de los números que ocupan dos, tres, cuatro,… celdas. A veces solo una celda). En mi opinión, son MUCHO más bonitos
ResponderEliminarYo también soy de los que hago sudokus diarios. De hecho, tengo una app (lo que permite las anotaciones de los posibles valores de cada casilla). Con el tiempo, he ido adquiriendo una técnica que seguro que alguno de vosotros también utiliza. Primero, intento completar cifras que por lógica tienen que ocupar una posición concreta. Por ejemplo, si en el primer cuadrante hay un "1" en la primera fila y en el tercer cuadrante hay un "1" en la tercera, en el segundo cuadrante tiene que estar en la segunda fila. Si en esa fila ya hay dos números, el "1" tiene que ir en el hueco que queda. Y así con los 9 números en vertical y en horizontal. Eso suele permitir rellenar rápidamente varios números. Luego miro ciertas combinaciones de eliminación. Por ejemplo, si en la primera fila del primer cuadrante hay dos casillas libres y los únicos números posibles son el 2 y el 3, eso implica que esos dos números ya no pueden estar en la primera fila de los otros dos cuadrantes y tampoco en ninguna otra casilla libre del primer cuadrante. Hay otros trucos que se van aprendiendo con el tiempo. Lo malo es que hacer un sudoku ya no me lleva mucho tiempo y ya no es tan divertido.
ResponderEliminar