La mayoría de la gente conoce el sudoku como un producto terminado: una cuadrícula con algunos números ya escritos y una etiqueta de dificultad arriba. Pocos se preguntan de dónde sale esa cuadrícula. ¿Quién decidió qué casillas mostrar? ¿Por qué todo sudoku decente tiene exactamente una respuesta? ¿Por qué uno marcado como «fácil» puede tenerte atascado veinte minutos mientras otro casi vacío se resuelve enseguida? Detrás de estas preguntas hay unas matemáticas sorprendentemente profundas, incluida una famosa demostración por ordenador que necesitó un año de cálculo en un superordenador. En este artículo lo explicamos con palabras sencillas y luego lo convertimos en consejos prácticos para elegir y resolver sudokus.

¿Cuántas cuadrículas de sudoku existen?

Empecemos por las cuadrículas completas: tablas de 9×9 en las que cada fila, cada columna y cada caja de 3×3 contiene los números del 1 al 9 una sola vez. Bertram Felgenhauer y Frazer Jarvis las contaron por ordenador y publicaron el resultado en 2006 en la revista Mathematical Spectrum. Hay exactamente 6.670.903.752.021.072.936.960, es decir, unos 6,67 × 10²¹.

Sin embargo, muchas de esas cuadrículas son en realidad la misma disfrazada. Se pueden renombrar los números (convertir todos los 1 en 7, por ejemplo), intercambiar filas dentro de una banda de tres, intercambiar bandas enteras, hacer lo mismo con las columnas o reflejar la cuadrícula sobre su diagonal. Ed Russell y Frazer Jarvis contaron cuántas cuadrículas siguen siendo realmente distintas tras todas esas transformaciones, usando el lema de Burnside de la teoría de grupos. Según McGuire y sus colegas, el cálculo en sí tardó apenas un segundo. El resultado: 5.472.730.538 cuadrículas «esencialmente distintas».

Recuento de cuadrículas de sudoku completas
Qué se cuenta	Cantidad	Fuente
Cuadrículas completas de 4×4 (cajas de 2×2)	288	McGuire, Tugemann y Civario
Cuadrículas completas de 9×9	6.670.903.752.021.072.936.960	Felgenhauer y Jarvis (2006)
Cuadrículas de 9×9 esencialmente distintas	5.472.730.538	Russell y Jarvis (2007)

El mínimo de 17 pistas: por qué 16 es imposible

Un sudoku es una cuadrícula resuelta a la que se le han borrado la mayoría de los números. Si se borran demasiados, las pistas restantes ya no determinan una única respuesta. Entonces, ¿con cuántas pistas como mínimo puede construirse un sudoku correcto? Los aficionados encontraron decenas de miles de sudokus con 17 pistas. Gordon Royle los fue reuniendo y su lista llegó a contener 49.151 sudokus distintos de 17 pistas. Nunca nadie encontró uno válido con 16, pero que «nadie lo haya encontrado» no es una demostración.

La demostración llegó de la mano de Gary McGuire, Bastian Tugemann y Gilles Civario. Su preprint apareció en enero de 2012 y la versión revisada por pares se publicó en 2014 en la revista Experimental Mathematics. Su enfoque es fácil de enunciar y enormemente difícil de llevar a cabo: revisar una por una todas las cuadrículas solución posibles en busca de un sudoku de 16 pistas escondido.

La idea clave es el conjunto inevitable (unavoidable set). Imagina cuatro casillas repartidas en dos filas, dos columnas y dos cajas, con el patrón 3-8 / 8-3. Si intercambias los 3 y los 8 de esas cuatro casillas, obtienes otra cuadrícula perfectamente válida. Por tanto, si ninguna de esas cuatro casillas aparece como pista, el sudoku tiene dos soluciones. Cada cuadrícula completa contiene muchos conjuntos así, pequeños y grandes, y un sudoku correcto debe tener al menos una pista en cada uno. En matemáticas esto es un problema de conjunto de impacto (hitting set), y el equipo escribió un programa muy rápido, llamado checker, que enumera todos los conjuntos de impacto de 16 casillas de una cuadrícula y comprueba si alguno da una solución única.

Después lo ejecutaron sobre las 5.472.730.538 cuadrículas esencialmente distintas. La búsqueda se realizó entre enero y diciembre de 2011 en el clúster Stokes del Irish Centre for High-End Computing (ICHEC). Consumió unos 7,1 millones de horas-núcleo, con una media de unos 3,6 segundos por cuadrícula. Los autores señalan que la primera versión de su programa, de 2006, habría necesitado unos 300.000 años-procesador. Los mejores algoritmos lo redujeron a unos 800. No apareció ningún sudoku de 16 pistas: 17 es el verdadero mínimo.

Hay además un hecho más sencillo con una demostración de una línea: un sudoku correcto debe mostrar al menos ocho de los nueve números. Si faltaran, por ejemplo, el 4 y el 6, podrías intercambiar todos los 4 y 6 de la solución y obtendrías una segunda respuesta válida.

Por qué importa la solución única (y por qué nunca hace falta adivinar)

Como dice Peter Norvig en su conocido ensayo sobre la resolución de sudokus: «Puzzles that appear in books and newspapers always have one unique solution» (los sudokus que aparecen en libros y periódicos siempre tienen una única solución). No es solo una convención. La unicidad es lo que convierte el sudoku en un pasatiempo de lógica y no de suerte.

Cuando un sudoku tiene exactamente una solución, el valor de cada casilla viene obligado por las pistas. Es decir, siempre existe una cadena de razonamientos desde el principio hasta el final, aunque sea larga y difícil de encontrar. Si tuviera dos soluciones, tarde o temprano llegarías a un punto en el que tanto el 2 como el 5 encajan en una casilla y nada en la cuadrícula te dice cuál elegir. Tendrías que adivinar, y la mitad de las veces la respuesta «correcta» del final del libro contradiría tu resultado, perfectamente lógico.

El ensayo de Norvig también muestra por qué hay que comprobar la unicidad a propósito. Su sencillo generador aleatorio rellena casillas hasta que hay al menos 17 ocupadas con al menos 8 números distintos. Es rápido, pero él advierte que el resultado no tiene garantizada una solución única: algunos de sus sudokus aleatorios tienen varias soluciones y una pequeña parte no tiene ninguna.

Simetría y sudokus hechos a mano

El pasatiempo que hoy llamamos sudoku apareció primero en Estados Unidos. Suele atribuirse a Howard Garns y la editorial Dell Magazines lo publicó en 1979 con el nombre de Number Place. La editorial japonesa Nikoli cuenta en su web que lo descubrió en una revista estadounidense, que lo presentó a sus lectores japoneses en 1984 y que más tarde abrevió el largo título japonés a «Sudoku». Según Nikoli, al principio tuvo poco éxito. En 1986 los editores añadieron la regla de que las pistas debían colocarse siguiendo un patrón simétrico, y a partir de entonces se convirtió en un éxito.

El patrón más común es la simetría de rotación de 180 grados: si giras la cuadrícula boca abajo, las casillas con pista caen sobre casillas con pista. Esto no afecta en nada a la lógica; es pura estética. Tiene, eso sí, un pequeño coste: se cree que el mínimo de pistas para un sudoku con esta simetría es 18, no 17.

Nikoli sigue creando sus sudokus a mano. En la página donde explica por qué, su redactor jefe Nobuhiko Kanamoto afirma: «Good Sudoku authors are always considering a solver’s feelings» (los buenos autores de sudokus siempre piensan en lo que siente quien los resuelve). Un autor humano puede planificar un recorrido satisfactorio: un comienzo suave, un paso ingenioso a mitad de camino y un final limpio. Un ordenador puede generar sudokus válidos sin fin, pero que transmitan esa sensación de diseño depende de lo cuidadosamente que se filtren.

Cómo suelen funcionar los generadores por ordenador

La mayoría de webs, aplicaciones y libros de sudoku utilizan generadores. Los detalles varían, pero el método habitual es este:

Construir una cuadrícula completa. Un algoritmo de vuelta atrás (backtracking) con decisiones aleatorias rellena un tablero vacío y produce así una solución válida al azar.
Quitar pistas. Las casillas se vacían de una en una (o por parejas simétricas si se busca simetría).
Comprobar la unicidad tras cada borrado. Un resolvedor cuenta las soluciones y se detiene en cuanto encuentra la segunda. Si hay más de una, la última pista vuelve a su sitio.
Calificar el resultado. Un segundo resolvedor que imita las técnicas humanas recorre el sudoku de los pasos fáciles a los difíciles y anota la técnica más difícil necesaria.

Los sudokus de Ozerlyn Games siguen estos principios: cada sudoku tiene una solución única y está asignado a un nivel de dificultad, de modo que puede resolverse solo con lógica.

La dificultad depende de la técnica, no del número de pistas

Es tentador suponer que menos pistas significa un sudoku más difícil. Como regla aproximada tiene algo de cierto, pero no es fiable. En un estudio de 2012 publicado en Scientific Reports, María Ercsey-Ravasz y Zoltán Toroczkai midieron la dificultad de los sudokus con un modelo matemático y comprobaron que los sudokus de 17 y 18 pistas que probaron eran más fáciles que los más difíciles de 21 o 22 pistas. Su conclusión: la dificultad depende también de dónde están colocadas las pistas, no solo de cuántas hay.

Veamos una comparación en palabras. El sudoku A tiene solo 24 pistas, pero están repartidas de tal manera que, en cada momento, algún número tiene un único sitio posible en una fila, columna o caja. Basta con ir encontrando «únicos ocultos» (hidden singles) hasta llenar la cuadrícula. El sudoku B tiene 30 pistas y, sin embargo, tras una docena de colocaciones fáciles cada casilla restante tiene dos o tres candidatos y ya no queda ningún único. Para avanzar hace falta un X-Wing o una cadena. Pese al número de pistas, A es fácil y B es difícil.

Por eso los sistemas de calificación serios miden las técnicas necesarias. El más conocido es la puntuación Sudoku Explainer (SE), que valora un sudoku según el paso más difícil necesario para resolverlo: los únicos puntúan bajo, las parejas y los X-Wing más alto, y las cadenas y las redes de forzado (forcing nets) aún más. Nuestro artículo ¿Qué es el SE rating del sudoku? explica la escala en detalle, y con la calculadora de SE rating puedes puntuar cualquier sudoku tú mismo.

Qué significa todo esto para ti como jugador

Elige los sudokus por su calificación, no por lo vacíos que parezcan. Una cuadrícula con pocas pistas no es necesariamente difícil, ni una llena es necesariamente fácil.
Si un sudoku «fácil» se te hace difícil, probablemente solo estás buscando únicos desnudos (casillas con un solo candidato). Los sudokus fáciles suelen depender de los únicos ocultos. Pregúntate «¿dónde puede ir el 7 en esta caja?» en lugar de «¿qué número cabe en esta casilla?».
Si sientes que tienes que adivinar, se te ha pasado algo. Con una solución única siempre hay un siguiente paso lógico. Revisa tus anotaciones antes de arriesgarte.
La unicidad también es una herramienta. Los jugadores avanzados aprovechan que el sudoku tiene una sola solución para descartar patrones como el rectángulo 3-8 / 8-3 de antes. En esa idea se basa la técnica del «rectángulo único» (unique rectangle).

Para ponerlo en práctica, juega un sudoku de tu nivel en nuestra página de sudoku online o imprime algunos desde sudokus para imprimir y resuélvelos a lápiz. Fíjate en cada uno en cuál es el paso más difícil.

Fuentes

Gary McGuire, Bastian Tugemann, Gilles Civario: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics 23(2), 2014, pp. 190–217.
El mismo artículo como preprint gratuito: arXiv:1201.0749 (incluye los recuentos de cuadrículas, la lista de 49.151 sudokus de Royle y los detalles del cálculo).
Bertram Felgenhauer, Frazer Jarvis: Mathematics of Sudoku I, Mathematical Spectrum 39(1), 2006. Resumen del método: Universidad de Cornell, «Counting Sudoku solutions».
Ed Russell, Frazer Jarvis: Mathematics of Sudoku II, Mathematical Spectrum 39(2), 2007. Panorama general: Mathematics of Sudoku (Wikipedia).
María Ercsey-Ravasz, Zoltán Toroczkai: The Chaos Within Sudoku, Scientific Reports 2, 725, 2012.
Peter Norvig: Solving Every Sudoku Puzzle.
Nikoli: Sudoku (historia del pasatiempo) y Why hand made?
Sudoku (Wikipedia): historia, Howard Garns y el Number Place de Dell.

Cómo se crea un buen sudoku: 17 pistas, una sola solución y dificultad real