Las matemáticas del Sudoku
Un tablero de Sudoku es un pequeño objeto matemático, y se ha demostrado mucho sobre él. Estos son los principales resultados, del más sencillo al más profundo, cada uno con su demostración: completa cuando cabe en unas líneas, su idea cuando hizo falta un largo artículo o un ordenador.
Equivalencia directa
El Sudoku es un problema de coloración de grafos
Teorema. Resolver un sudoku es colorear con 9 colores un grafo de 81 vértices, respetando los colores que imponen los números dados. Cada vértice tiene exactamente 20 vecinos.
Tomemos un vértice por casilla y unamos dos vértices cuando sus casillas comparten fila, columna o caja. Los nueve números se convierten en nueve colores, y colorear el grafo es dar un color a cada vértice sin que dos vecinos tengan el mismo.
Demostración
De una solución a una coloración: demos a cada vértice el color del número de su casilla. Dos casillas vecinas comparten fila, columna o caja, así que tienen números distintos, y sus vértices reciben colores distintos.
De una coloración a una solución: las nueve casillas de una fila son todas vecinas entre sí, así que necesitan nueve colores distintos. Como solo hay nueve, cada uno aparece exactamente una vez en la fila. Lo mismo vale para cada columna y cada caja: leyendo los colores como números, se obtiene una solución.
La cuenta de las vecinas
Una casilla tiene otras 8 en su fila, 8 en su columna y 8 en su caja. Pero 2 casillas de su caja están también en su fila, y 2 en su columna: se han contado dos veces.
8 + 8 + 8 − 2 − 2 = 20
El grafo tiene, pues, 81 × 20 ÷ 2 = 810 aristas, cada una contada desde sus dos extremos. Y como una fila necesita nueve colores y nueve bastan, el grafo necesita exactamente nueve: su número cromático es 9.
En My Sudoku
Visto así, un Solitario desnudo es un vértice cuyos 20 vecinos ya usan 8 de los 9 colores: solo le queda uno.
Fuente: Wikipedia: Mathematics of Sudoku.
Codificación lógica
El Sudoku es un problema de cobertura exacta
Teorema. Una solución de Sudoku es una elección de 81 filas, entre las 729 de una matriz de ceros y unos con 324 columnas, que cubre cada columna exactamente una vez.
Cada jugada del Sudoku coloca un número d en una casilla (f, c), y cada colocación cumple cuatro restricciones a la vez:
- casilla: la casilla (f, c) tiene un número;
- fila: el número d está en la fila f;
- columna: el número d está en la columna c;
- caja: el número d está en la caja de (f, c).
Cada tipo aparece 81 veces: 81 casillas, y 9 números para cada una de las 9 filas, las 9 columnas y las 9 cajas.
4 × 81 = 324 restricciones · 81 × 9 = 729 colocaciones
Escribamos una matriz con una fila por colocación y una columna por restricción, con un 1 donde la colocación cumple la restricción. Cada fila tiene exactamente cuatro unos. Colocar un 7 en F2C5, por ejemplo, cubre cuatro columnas:
- casilla F2C5
- un 7 en la fila 2
- un 7 en la columna 5
- un 7 en la caja 2
Demostración
Una cobertura exacta elige filas de la matriz de modo que cada columna tenga exactamente un 1 entre ellas. Las 81 restricciones de casilla dan a cada casilla exactamente un número; las de fila, columna y caja ponen cada número exactamente una vez en cada fila, columna y caja. Eso es una solución del Sudoku y, a la inversa, las 81 colocaciones de una solución cumplen cada restricción una vez. Los números dados son filas elegidas de antemano.
cobertura exacta ⟺ solución: 81 filas de 729
En My Sudoku
Muchos programas de resolución trabajan con esta forma, entre ellos el algoritmo X de Donald Knuth y sus Dancing Links («enlaces danzantes»): siempre exploran primero la restricción con menos opciones. La búsqueda de My Sudoku hace lo mismo con las restricciones de casilla: prueba primero la casilla con menos números posibles.
La matriz muestra también que los dos solitarios son una sola idea: un Solitario desnudo es una restricción de casilla, y un Solitario oculto una de fila, columna o caja, a la que solo le queda una colocación. En ambos casos, una columna con un solo 1.
Fuentes: Donald E. Knuth, Dancing Links (2000), Wikipedia: Mathematics of Sudoku.
Recuento por ordenador, con las simetrías
Hay 6.670.903.752.021.072.936.960 tableros
Teorema. Hay exactamente 6.670.903.752.021.072.936.960 formas de llenar un tablero de 9 × 9 según las reglas, unas 6,67 × 10²¹. Dejando de lado las simetrías, 5.472.730.538 son esencialmente distintas.
Bertram Felgenhauer y Frazer Jarvis los contaron en 2005; Ed Russell y Frazer Jarvis contaron poco después los esencialmente distintos.
¿Por qué no (9!)⁹?
Cada fila puede ordenarse de 9! = 362.880 formas, así que cabría esperar (9!)⁹ tableros, unos 1,1 × 10⁵⁰. Pero esa cifra cuenta nueve filas cualesquiera apiladas, con números repetidos en columnas y cajas: las restricciones no son independientes, y el número real es mucho menor.
Una parte comprobable: un múltiplo de 9!
Renombremos los números de un tablero: cada 1 pasa a ser un 5, cada 5 un 2, y así sucesivamente, según una de las 9! formas de permutar los nueve números. Cada fila, columna y caja sigue teniendo cada número una vez: el resultado también es un tablero. Dos renombramientos distintos de un tablero dan dos tableros distintos, y renombrar un tablero renombrado da otro de la misma familia. Los tableros se reparten, pues, en familias de exactamente 9! tableros, y su número es múltiplo de 9!:
6.670.903.752.021.072.936.960 = 9! × 18.383.222.420.692.992
Cómo se hizo el recuento
Felgenhauer y Jarvis fijaron la primera caja como 1 a 9 en orden de lectura, lo que da cuenta del 9!, y contaron las formas de completar las tres primeras filas: 2.612.736, es decir, 56 × 6⁶. Muchas se parecen, pues una se convierte en otra al intercambiar columnas o renombrar números, y se pueden completar de tantas formas como ella; agrupándolas, hicieron que un ordenador contara, para cada grupo, las formas de llenar las seis últimas filas. El total se descompone así, y su último factor es un número primo:
9! × 72² × 2⁷ × 27.704.267.971
Los tableros esencialmente distintos
Reflejar un tablero en su diagonal, intercambiar dos bandas o dos pilas de cajas, dos filas de una misma banda o dos columnas de una misma pila, o renombrar sus números da un tablero que en el fondo es el mismo. Estas operaciones forman un grupo de 9! × 3.359.232 elementos. Dividir el recuento entre ese número da unos 5.472.448.000: se acerca, pero no es exacto. Algunos tableros son simétricos y quedan iguales con alguna operación, así que su familia es más pequeña que el grupo y la división se queda corta con ellos. El lema de Burnside, que cuenta los tableros que cada operación deja iguales, corrige la cuenta:
5.472.730.538 tableros esencialmente distintos
La misma cuenta a mano, en 4 × 4
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 2 | 1 |
Con cuatro números y cajas de 2 × 2, toda la cuenta cabe en unas líneas. Llenemos la primera caja: 4! = 24 formas y, renombrando los números, podemos suponer que es 1 2 / 3 4. El resto de la fila 1 tiene entonces 3 y 4, y el resto de la fila 2, 1 y 2, en un orden u otro: 4 formas. Lo mismo con el resto de las columnas 1 y 2: 4 formas. De estas 16 combinaciones, 12 dejan exactamente una forma de llenar la última caja, y 4 no dejan ninguna:
24 × 12 = 288 tableros
Entre los cuadrados latinos
Un tablero es un cuadrado latino de orden 9, cada número una vez por fila y por columna, con la regla de las cajas además. Hay 5.524.751.496.156.892.842.531.225.600 cuadrados latinos de orden 9: las cajas solo conservan uno de cada 828.000, más o menos.
Fuentes: Frazer Jarvis, Sudoku enumeration problems, OEIS A002860, Wikipedia: Mathematics of Sudoku.
Demostración en pocas líneas
Los números dados muestran al menos ocho cifras distintas
Teorema. En un sudoku con solución única, al menos ocho de las nueve cifras aparecen entre los números dados.
Ocho cifras distintas, no ocho números dados.
Demostración
Supongamos que dos cifras, por ejemplo el 4 y el 7, no aparecen entre los números dados. Tomemos una solución e intercambiemos en ella todos los 4 y los 7.
Cada fila tenía un 4 y un 7, y los sigue teniendo: solo han cambiado de sitio. Lo mismo ocurre en cada columna y cada caja, así que el nuevo tablero también es una solución. Difiere del primero allí donde había un 4 o un 7, y respeta todos los números dados, porque ninguno es un 4 ni un 7. El sudoku tendría dos soluciones. Así que entre los números dados puede faltar como mucho una cifra.
Justo en el límite
El sudoku de 17 números dados que aparece más abajo está justo en el límite: sus números dados muestran ocho cifras, sin ningún 6.
En un tablero de N × N, el mismo razonamiento exige N − 1 símbolos distintos entre los números dados.
Fuente: Wikipedia: Mathematics of Sudoku.
Demostración por construcción
Cuatro casillas pueden bastar para estropear un sudoku
Teorema. Si cuatro casillas en las esquinas de un rectángulo, en dos filas, dos columnas y dos cajas, tienen a b / b a en una solución y ninguna es un número dado, el sudoku tiene una segunda solución.
Demostración
| a | b |
| b | a |
| b | a |
| a | b |
Intercambiemos a y b en las cuatro casillas. Cada una de las dos filas sigue teniendo un a y un b, y cada una de las dos columnas también. Las cuatro casillas están de dos en dos en dos cajas, y cada pareja tiene un a y un b: tras el intercambio, las cajas siguen siendo correctas. Nada más cambia: el nuevo tablero también es una solución, y respeta todos los números dados, porque ninguna de las cuatro casillas lo es.
Los conjuntos inevitables
Un conjunto de casillas así, de las que al menos una debe ser un número dado, se llama conjunto inevitable. Aquí, un sudoku con 77 números dados, con solo cuatro casillas vacías, tiene dos soluciones: la cantidad de números dados dice poco; su lugar, mucho.
Nunca menos de cuatro casillas
A la inversa, dos soluciones distintas de un mismo sudoku difieren siempre en al menos cuatro casillas. Así que un sudoku con 78 números dados o más nunca tiene dos soluciones, y el rectángulo es la ambigüedad más pequeña que existe.
Miremos las casillas en las que difieren las dos soluciones. Una fila no puede contener solo una: sus otras ocho casillas tendrían las mismas ocho cifras en ambas soluciones, y quedaría la misma novena cifra para la última. Así que una fila, o una columna, que contiene una de estas casillas contiene al menos dos. Tomemos una, x. Su fila contiene otra, y; su columna otra, z; y la fila de z otra, w. Esa casilla w no es x, que no está en la fila de z, ni y, que está en la fila de x. Son cuatro casillas distintas.
En My Sudoku
La técnica del Rectángulo único le da la vuelta: como un sudoku bien hecho solo tiene una solución, ese rectángulo nunca puede formarse, y se pueden eliminar los candidatos que lo formarían.
Fuente: Wikipedia: Mathematics of Sudoku.
Demostración exhaustiva por ordenador
Un sudoku necesita al menos 17 números dados
Teorema. Un sudoku de 9 × 9 con solución única tiene al menos 17 números dados. Los hay con 17; ninguno con 16.
Gary McGuire, Bastian Tugemann y Gilles Civario lo demostraron en 2012 mediante una búsqueda informática exhaustiva. Se conocen decenas de miles de sudokus con 17 números dados.
Idea de la demostración
La demostración se basa en los conjuntos inevitables vistos antes: conjuntos de casillas de un tablero que los números dados deben tocar, porque si no sus cifras podrían reordenarse en una segunda solución. Unos números dados que determinan un tablero deben tocar cada uno de sus conjuntos inevitables: forman un conjunto de impacto (hitting set) de esa familia. La búsqueda fue así:
- para cada uno de los 5.472.730.538 tableros esencialmente distintos, hallar muchos de sus conjuntos inevitables;
- enumerar todos los conjuntos de 16 casillas que los tocan todos, la parte difícil, para la que los autores diseñaron un algoritmo nuevo;
- comprobar si las cifras del tablero en esas 16 casillas lo determinan;
- nunca ocurrió.
Es una demostración de verdad, pero que solo un ordenador puede llevar a cabo: nadie podría comprobarla a mano.
La misma demostración en miniatura
En los tableros de 4 × 4, la misma búsqueda es diminuta. Entre los 288 tableros, ninguno queda determinado por 3 de sus casillas, mientras que algunos lo quedan por 4: allí el mínimo es 4, algo que un ordenador comprueba en un instante probando todos los casos.
Minimal no es mínimo
Un sudoku es minimal cuando quitar cualquiera de sus números dados deja pasar una segunda solución, y mínimo cuando ningún sudoku tiene menos: 17. Un sudoku puede ser minimal con 25 números dados, sin que ninguno pueda quitarse, mientras otros se las arreglan con menos.
Salvo los del nivel Muy fácil, los sudokus de My Sudoku son minimales: llena un tablero al azar y luego quita los números uno a uno en orden aleatorio, volviendo a poner cualquiera cuya retirada deje pasar una segunda solución. Sus sudokus suelen quedarse con 22 a 27 números dados.
Fuentes: Gary McGuire, Bastian Tugemann, Gilles Civario, There is no 16-Clue Sudoku (2012), Wikipedia: Mathematics of Sudoku.
Demostración por reducción
El Sudoku es NP-completo
Teorema. Decidir si un sudoku parcialmente lleno de n² × n² casillas, con cajas de n × n, tiene solución es un problema NP-completo.
Takayuki Yato y Takahiro Seta lo demostraron en 2003, partiendo de los cuadrados latinos. Un problema es NP-completo cuando tiene dos propiedades: está en NP, es decir, una solución propuesta se comprueba rápido, y es NP-difícil, es decir, todo problema de NP puede traducirse a él en tiempo polinómico. La demostración tiene dos partes.
Parte A: el Sudoku está en NP
Tomemos un tablero lleno de lado N = n². Para comprobarlo, se recorren sus N filas, sus N columnas y sus N cajas, y se compara con los números dados. Comprobar que una fila tiene una vez cada símbolo del 1 al N requiere unas N operaciones; las filas requieren entonces unas N × N, y lo mismo las columnas y las cajas:
3 × N × O(N) = O(N²)
Es un número de operaciones proporcional a las N² casillas del tablero. Encontrar una solución puede ser difícil; comprobar una es rápido.
Parte B: el Sudoku es NP-difícil
Un cuadrado latino de orden N llena una cuadrícula de N × N con N símbolos, cada uno una vez por fila y por columna: las reglas del Sudoku, sin las cajas.
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
Charles Colbourn demostró en 1984 que decidir si un cuadrado latino parcialmente lleno puede completarse es NP-completo. Yato y Seta transforman cualquier cuadrado latino parcialmente lleno L en un sudoku parcialmente lleno S(L), en tiempo polinómico: los números dados de S(L) están dispuestos de modo que sus casillas libres solo pueden llenarse como puede completarse L. Cada forma de completar L da exactamente una solución de S(L), y viceversa (una reducción parsimoniosa):
L se puede completar ⟺ S(L) tiene solución
Un método rápido para el Sudoku daría, pues, un método rápido para los cuadrados latinos. Como completar un cuadrado latino es NP-completo, el Sudoku es NP-difícil; con la parte A, NP-completo.
Lo que no significa
No significa que los sudokus de 9 × 9 sean difíciles: su tamaño es fijo, y un ordenador resuelve cualquiera en un instante. La NP-completitud se refiere a toda la familia, a medida que n crece: no se conoce ningún método que resuelva cada tablero en un tiempo polinómico en su tamaño, y encontrarlo demostraría que P = NP, una de las grandes preguntas abiertas de las matemáticas, con un premio de un millón de dólares del Instituto Clay.
Una segunda solución: ASP-completo
Yato y Seta demuestran más: dado un sudoku y una de sus soluciones, decidir si tiene otra es igual de difícil. El problema es ASP-completo (del inglés Another Solution Problem, «problema de otra solución»). Es la pregunta que se hace todo creador de sudokus, porque un sudoku bien hecho tiene una única solución.
Por eso el generador de My Sudoku no deja nada al azar: tras cada número que quita, una búsqueda intenta encontrar una segunda solución, deteniéndose en la primera que encuentra, y si la encuentra, el número vuelve a su sitio.
Fuentes: Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles, IEICE Transactions on Fundamentals E86-A (2003), Charles J. Colbourn, The complexity of completing partial Latin squares (1984), Wikipedia: Mathematics of Sudoku.
En resumen
| Resultado | Tipo de demostración |
|---|---|
| El Sudoku es un problema de coloración de grafos | Equivalencia directa |
| El Sudoku es un problema de cobertura exacta | Codificación lógica |
| Hay 6.670.903.752.021.072.936.960 tableros | Recuento por ordenador, con las simetrías |
| Los números dados muestran al menos ocho cifras distintas | Demostración en pocas líneas |
| Cuatro casillas pueden bastar para estropear un sudoku | Demostración por construcción |
| Un sudoku necesita al menos 17 números dados | Demostración exhaustiva por ordenador |
| El Sudoku es NP-completo | Demostración por reducción |