El sudoku utiliza números, pero no es un puzzle de aritmética.
Para resolver una cuadrícula clásica nunca necesitas calcular una suma, un producto ni una fórmula numérica.
Los dígitos del 1 al 9 funcionan principalmente como nueve símbolos distintos.
Lo que hace matemáticamente interesante al sudoku es la estructura alrededor de esos símbolos:
- combinatoria;
- cuadrados latinos;
- satisfacción de restricciones;
- exact cover;
- relaciones de conflicto similares a grafos;
- simetría;
- búsqueda;
- enumeración.
Esta estructura ayuda a explicar por qué el sudoku es tan fácil de definir y, al mismo tiempo, tiene un espacio de soluciones tan enorme.
Sudoku como cuadrado latino con restricciones adicionales
Un cuadrado latino de orden 9 es una disposición 9×9 de nueve símbolos en la que cada símbolo aparece exactamente una vez en cada fila y cada columna.
Una cuadrícula completa de sudoku clásico cumple esas dos condiciones más la condición de bloques 3×3.
Por tanto:
Toda cuadrícula completa de sudoku clásico es un cuadrado latino con restricciones adicionales de bloques.
Pero:
No todo cuadrado latino 9×9 es una cuadrícula válida de sudoku.
Esta relación es matemáticamente importante.
Históricamente, sin embargo, no debería convertirse en la frase incorrecta:
«Euler inventó el sudoku».
Los cuadrados latinos forman parte del trasfondo matemático.
La historia directa del puzzle moderno se trata por separado en Historia del sudoku.
Satisfacción de restricciones
El sudoku es un ejemplo natural de problema de satisfacción de restricciones.
Piensa en cada celda como una variable.
Al principio, una celda sin resolver puede tener un dominio como:
{1,2,3,4,5,6,7,8,9}
Las pistas y las relaciones con otras celdas van reduciendo esos dominios.
Ejemplo:
candidatos de r4c7
{2,5,8}Si aparece un nuevo 8 en una de sus unidades relacionadas:
{2,5,8}
↓
{2,5}Si más adelante se elimina el 2:
{2,5}
↓
{5}La celda queda resuelta.
La notación de candidatos utilizada por una persona es, por tanto, una versión muy legible de reducción de dominios y propagación de restricciones.
Sudoku como exact cover
El sudoku clásico también puede expresarse como un problema de exact cover.
Una asignación completa debe cumplir requisitos como:
- cada celda recibe exactamente un dígito;
- cada fila contiene cada dígito exactamente una vez;
- cada columna contiene cada dígito exactamente una vez;
- cada bloque contiene cada dígito exactamente una vez.
En un sudoku clásico 9×9, las posibles colocaciones de candidatos pueden representarse frente a estas restricciones de exact cover.
Por eso algoritmos como Algorithm X y técnicas de implementación como Dancing Links son formas naturales de resolver sudoku mediante software.
Los jugadores no necesitan aprender exact cover.
Para software resulta útil porque ofrece otra forma de resolver completamente y contar soluciones.
Sudoku como problema de tipo grafo
Otro punto de vista trata las celdas o estados de candidatos como nodos conectados por conflictos.
A nivel sencillo de celdas:
Dos celdas relacionadas no pueden contener el mismo dígito.
Esto se parece a un problema estructurado de coloreado de grafos:
- las celdas son variables o nodos;
- los dígitos son etiquetas o colores;
- las relaciones entre celdas imponen exclusiones.
Los grafos a nivel de candidatos resultan todavía más útiles para:
- Enlaces fuertes;
- Enlaces débiles;
- Coloración;
- Cadenas.
No hace falta teoría de grafos para resolver un sudoku normal, pero la conexión ayuda a explicar por qué las técnicas avanzadas pueden representarse como redes de relaciones lógicas.
Búsqueda y backtracking
Un solver genérico también puede utilizar búsqueda recursiva.
Un esquema sencillo:
- elige una celda sin resolver;
- selecciona un candidato;
- propaga restricciones;
- continúa recursivamente;
- si el estado se vuelve imposible, vuelve atrás;
- prueba otro candidato.
Con buenas heurísticas puede resolver sudokus estándar 9×9 con mucha eficacia.
Más importante aún, una búsqueda completa puede responder preguntas que un analizador de técnicas humanas no está diseñado para responder directamente:
¿Existe alguna solución?
¿Existe una segunda solución?
Esto convierte la búsqueda completa en una capa de validación útil aunque el jugador nunca la vea.
¿Cuántas cuadrículas completas de sudoku existen?
Para el sudoku clásico 9×9, Bertram Felgenhauer y Frazer Jarvis calcularon:
6.670.903.752.021.072.936.960
cuadrículas solución completas válidas.
Aproximadamente:
6,671 × 10²¹
Son más de seis sextillones de cuadrículas completas.
El conteo considera diferentes muchas cuadrículas que son estructuralmente equivalentes mediante transformaciones.
Cuadrículas esencialmente diferentes
Las transformaciones que preservan el sudoku pueden convertir una cuadrícula completa válida en otra.
Algunos ejemplos:
- renombrar los dígitos de forma coherente;
- intercambiar filas dentro de una banda;
- intercambiar columnas dentro de una pila;
- intercambiar bandas completas;
- intercambiar pilas completas;
- transponer;
- aplicar rotaciones o reflexiones apropiadas.
Después de factorizar el grupo estándar de simetrías, el conteo clásico de cuadrículas completas esencialmente diferentes es:
5.472.730.538
Aun así, más de cinco mil millones.
El número exacto depende de qué transformaciones se consideren equivalentes; la cifra 5.472.730.538 utiliza el grupo estándar de simetría del sudoku.
Por qué estas cifras no son el número de puzzles de sudoku
Una cuadrícula completa es una cuadrícula solución.
Un puzzle es un subconjunto de pistas que apunta a una solución bajo determinadas condiciones editoriales.
Una misma cuadrícula solución puede admitir muchos subconjuntos de pistas.
Estos subconjuntos pueden diferir en:
- número de soluciones;
- minimalidad;
- simetría de pistas;
- dificultad;
- ruta de resolución humana;
- calidad estética.
Por tanto, el número de puzzles potenciales no es simplemente el número de cuadrículas solución.
La generación añade otra enorme capa combinatoria.
Simetría en la construcción de puzzles
Hay dos ideas de simetría que conviene separar.
Simetría matemática
Transformaciones que conservan la validez o equivalencia del sudoku.
Simetría de distribución de pistas
El constructor elige los dados siguiendo un patrón visual simétrico, a menudo simetría rotacional.
La segunda es una elección estética o de construcción.
No la exigen las reglas clásicas.
Nikoli adoptó históricamente la colocación simétrica de pistas como parte de su estilo, pero un puzzle asimétrico puede ser perfectamente válido.
Combinatoria y selección de pistas
Supón que empezamos con una solución completa.
Hay 81 posiciones de celda.
Cada posible conjunto de pistas selecciona un subconjunto de esas posiciones.
Pero la mayoría de subconjuntos no son adecuados como puzzles publicados.
Un conjunto objetivo puede necesitar:
- coherencia;
- unicidad;
- minimalidad opcional;
- resolubilidad humana;
- dificultad deseada.
Por eso generar sudoku no puede reducirse a:
Elegir N celdas al azar.
El espacio combinatorio es enorme y el espacio de puzzles buenos y publicables es mucho más pequeño.
Pistas mínimas como problema extremo
El resultado de las 17 pistas plantea otra pregunta matemática:
¿Hasta dónde puede reducirse un conjunto de pistas único?
La demostración de que no existe ningún puzzle único de 16 pistas necesitó cálculo exhaustivo y una formulación de tipo hitting set.
Es un ejemplo de cómo el diseño de un puzzle recreativo conecta con búsqueda combinatoria seria.
Dificultad como problema de computación humana
El tamaño matemático por sí solo no describe la dificultad.
Todos los puzzles clásicos comparten:
- 81 celdas;
- 9 dígitos;
- las mismas tres familias de unidades.
Y aun así la dificultad para una persona varía enormemente.
La investigación que compara métricas con datos de jugadores encuentra dos componentes importantes:
- complejidad de los pasos individuales;
- estructura de dependencias entre esos pasos.
Esto recuerda que la dificultad es en parte un modelo de cognición y búsqueda humana, no una propiedad estática como el número de pistas.
Por qué diferentes solvers de sudoku sirven para trabajos distintos
Los puntos de vista matemáticos explican por qué el software suele separar varias funciones.
Solver completo / contador de soluciones
Métodos posibles:
- backtracking;
- exact cover;
- SAT/CSP.
Responsabilidades:
- validez;
- existencia de solución;
- unicidad.
Solver de estilo humano
Responsabilidades:
- ruta de deducciones con nombre;
- candidatos;
- técnicas;
- metadata explicativa.
Generador
Responsabilidades:
- crear o seleccionar una cuadrícula solución;
- elegir pistas;
- llamar a la validación de unicidad;
- llamar al analizador humano;
- cumplir restricciones editoriales o de construcción.
Una única representación no tiene por qué servir igual de bien para todos los trabajos.
Preguntas frecuentes
¿El sudoku se basa en aritmética?
No. Los dígitos funcionan como símbolos.
¿Todo sudoku es un cuadrado latino?
Toda cuadrícula completa de sudoku clásico es un cuadrado latino con la restricción adicional de bloques.
¿Todos los cuadrados latinos son sudokus?
No.
¿Cuántas cuadrículas completas de sudoku clásico existen?
6.670.903.752.021.072.936.960.
¿Por qué hay «solo» unos 5.470 millones de cuadrículas esencialmente diferentes?
Porque muchas cuadrículas completas son equivalentes bajo simetrías que preservan el sudoku.
¿El enorme número de soluciones hace difícil al sudoku?
No directamente. La dificultad humana depende de las pistas concretas y de la ruta de deducciones.
Qué aprender después
Lee Cómo se generan los sudokus para ver cómo las cuadrículas solución matemáticas se convierten en puzzles jugables.
Lee Cómo se valora la dificultad del sudoku para conocer la parte humana del análisis computacional.