En esta página
El sudoku no necesita operaciones aritméticas, pero posee una estructura matemática muy rica.
Los dígitos del 1 al 9 funcionan principalmente como nueve símbolos distintos. Lo importante no es cuánto valen, sino dónde pueden aparecer bajo las restricciones de filas, columnas y bloques.
Eso permite estudiar el puzzle desde varios campos: cuadrados latinos, combinatoria, satisfacción de restricciones, exact cover, grafos, búsqueda y complejidad computacional.
- filas: 1–9 una vez cada uno
- columnas: 1–9 una vez cada uno
- sin regla de cajas
- filas: 1–9 una vez cada uno
- columnas: 1–9 una vez cada uno
- cajas: 1–9 una vez cada uno
Por qué los números del sudoku son realmente símbolos
Si sustituyes todos los 1 por A, todos los 2 por B y así sucesivamente, la estructura lógica del sudoku no cambia.
Las reglas no dicen:
2 + 3 = 5.
Dicen, en esencia:
cada uno de los nueve símbolos debe aparecer exactamente una vez en cada fila, columna y bloque.
Por eso el sudoku clásico es un puzzle de restricciones y permutaciones, no de cálculo numérico.
Sudoku como cuadrado latino con restricciones
Un cuadrado latino de orden 9 contiene nueve símbolos distribuidos de forma que cada uno aparece exactamente una vez en cada fila y cada columna.
Toda cuadrícula completa de sudoku clásico cumple esas dos condiciones y añade otra:
- cada bloque 3×3 también contiene los nueve símbolos exactamente una vez.
Así que todo sudoku completo es un cuadrado latino con restricciones regionales adicionales.
No todo cuadrado latino 9×9 es sudoku porque puede incumplir los bloques.
Sudoku como problema de satisfacción de restricciones
En un Constraint Satisfaction Problem (CSP) tenemos:
- variables;
- dominios de valores posibles;
- restricciones que limitan combinaciones.
Sudoku encaja de forma natural:
- cada celda es una variable;
- su dominio inicial es un subconjunto de 1–9;
- las reglas relacionan las variables que comparten fila, columna o bloque.
Cuando un jugador elimina candidatos, está reduciendo dominios.
Cuando una celda queda con un único valor legal, su dominio se ha reducido a una sola posibilidad.
Este modelo ayuda a conectar el razonamiento humano con algoritmos generales de propagación de restricciones.
Las restricciones locales crean estructura global
Cada regla parece local: una celda entra en conflicto con sus pares de fila, columna y bloque.
Pero esas relaciones se solapan por toda la cuadrícula.
Una colocación en una esquina puede eliminar un candidato, esa eliminación puede crear un Single en otro bloque y ese Single puede desencadenar una cadena de consecuencias mucho más lejos.
Por eso un conjunto pequeño de restricciones locales produce una estructura global compleja.
Sudoku como problema de exact cover
Una cuadrícula completa de sudoku clásico puede codificarse como un problema de exact cover.
Cada posible asignación «la celda r,c contiene el dígito d» es una fila candidata del modelo.
En una cuadrícula 9×9 hay:
81 × 9 = 729 asignaciones posibles
antes de aplicar las pistas.
Cada solución completa debe satisfacer exactamente una vez cuatro tipos de condiciones:
- cada celda recibe un dígito — 81 restricciones;
- cada dígito aparece una vez en cada fila — 81;
- cada dígito aparece una vez en cada columna — 81;
- cada dígito aparece una vez en cada bloque — 81.
Total:
324 restricciones de exact cover.
Algoritmos como Algorithm X pueden buscar combinaciones de asignaciones que cubran esas 324 condiciones exactamente una vez.
Sudoku como problema de tipo grafo
También puede estudiarse mediante grafos o redes de relaciones.
A nivel de celdas, dos celdas que se ven entre sí no pueden contener el mismo dígito.
A nivel de candidatos, podemos modelar:
- conflictos;
- Enlaces fuertes;
- Enlaces débiles;
- implicaciones;
- componentes de Coloring;
- Cadenas.
Esta representación resulta especialmente intuitiva al estudiar técnicas avanzadas que ya hablan explícitamente de nodos y enlaces.
Búsqueda y backtracking
Un solver completo puede resolver Sudoku mediante búsqueda recursiva:
- elige una posibilidad no resuelta;
- asume temporalmente un valor;
- propaga sus consecuencias;
- si aparece una contradicción, retrocede;
- prueba otra rama;
- continúa hasta encontrar soluciones o demostrar que no existen.
Con buenas heurísticas y propagación, un sudoku 9×9 ordinario es muy manejable para un ordenador moderno.
Esto no significa que un jugador humano deba resolverlo así. Es simplemente una herramienta computacional para estudiar el espacio completo de soluciones.
Exact cover y backtracking no son opuestos
A veces se presenta Algorithm X como «el método inteligente» y backtracking como «fuerza bruta».
La separación no es tan simple.
Algorithm X también explora un árbol de elecciones y retrocede cuando una rama no puede completar la cobertura exacta. Su potencia procede de la representación del problema y de la eficiencia con la que selecciona, aplica y deshace restricciones.
Dancing Links (DLX) es una estructura de datos especialmente eficiente para implementar esas operaciones de Algorithm X.
Complejidad computacional del sudoku generalizado
Cuando se habla de que «Sudoku es NP-completo» hay que añadir un matiz importante.
El resultado de complejidad se refiere a una familia generalizada de sudokus de tamaño creciente, no a la afirmación práctica de que una cuadrícula fija 9×9 sea intratable para un ordenador.
El 9×9 tiene tamaño constante y los solvers modernos pueden resolverlo muy rápidamente.
La teoría de complejidad pregunta qué ocurre cuando el tamaño del problema puede crecer arbitrariamente.
En ese contexto, el sudoku generalizado es computacionalmente difícil en un sentido formal.
¿Cuántas cuadrículas completas de sudoku clásico existen?
El número exacto es:
6.670.903.752.021.072.936.960
aproximadamente:
6,671 × 10²¹.
más de seis sextillones de cuadrículas clásicas completas de Sudoku
Esta cifra cuenta cuadrículas completas diferentes celda por celda.
No cuenta puzzles parciales ni intenta identificar cuadrículas equivalentes mediante simetrías.
Cuadrículas de sudoku esencialmente diferentes
Muchas cuadrículas pueden transformarse unas en otras mediante operaciones que preservan la estructura del sudoku, por ejemplo:
- permutar los nueve símbolos;
- intercambiar filas dentro de una banda;
- intercambiar columnas dentro de una pila;
- intercambiar bandas completas;
- intercambiar pilas completas;
- transponer la cuadrícula;
- aplicar ciertas simetrías geométricas equivalentes.
Si agrupamos cuadrículas relacionadas por estas transformaciones, el número de clases esencialmente distintas desciende a:
5.472.730.538.
Eso sigue siendo más de cinco mil millones de estructuras fundamentales.
Por qué el recuento de cuadrículas solución no es el número de puzzles
Una cuadrícula completa puede producir muchísimos conjuntos distintos de pistas.
Algunos tendrán una solución única y otros no.
Algunos serán minimal, otros tendrán pistas redundantes.
Algunos ofrecerán una ruta humana interesante y otros serán pobres como puzzles.
Por tanto:
contar cuadrículas completas no equivale a contar sudokus publicables.
El espacio de puzzles posibles depende además de qué subconjuntos de celdas se revelan y de qué propiedades editoriales exigimos.
Simetría en las matemáticas del sudoku
La palabra simetría aparece en dos sentidos relacionados pero distintos.
Equivalencia entre cuadrículas solución
Aquí hablamos de transformaciones matemáticas que convierten una cuadrícula válida en otra sin cambiar la estructura esencial del problema.
Sirven para reducir recuentos y estudiar clases de equivalencia.
Simetría de la distribución de pistas
Aquí hablamos de la apariencia del puzzle parcial, por ejemplo pistas colocadas con simetría rotacional de 180°.
Es una preferencia de construcción y presentación, no una regla matemática necesaria para que la solución sea válida.
Las permutaciones ayudan a entender la equivalencia
Como los dígitos funcionan como símbolos, cualquier permutación consistente de 1–9 transforma una cuadrícula válida en otra válida.
Lo mismo ocurre con determinadas permutaciones de filas, columnas, bandas y pilas que respetan la estructura de bloques.
Estas operaciones forman una gran familia de simetrías del espacio de soluciones.
Estudiarlas permite distinguir entre:
- cuadrículas distintas en sentido literal;
- y estructuras que son la misma salvo por un renombrado o transformación válida.
Combinatoria de la selección de pistas
Incluso con una cuadrícula solución fija, elegir qué celdas mostrar crea un problema combinatorio enorme.
Hay:
2⁸¹
subconjuntos posibles de las 81 posiciones antes de imponer condiciones como unicidad o número de pistas.
La mayoría no son puzzles útiles.
La generación debe buscar dentro de ese espacio conjuntos que cumplan objetivos específicos.
Pistas mínimas como problema extremo
La pregunta «¿cuántas pistas como mínimo puede tener un sudoku único?» es un problema extremal.
No pregunta por un puzzle promedio, sino por la frontera más extrema posible bajo ciertas condiciones.
Para sudoku clásico 9×9, esa frontera es 17 pistas.
Demostrar que 16 era imposible exigió explorar combinaciones de pistas con herramientas como conjuntos inevitables y búsqueda exhaustiva.
Dificultad como modelo de computación humana
La dificultad no es una propiedad simple como el número de soluciones.
Un rating intenta modelar el trabajo que tendría que realizar cierto tipo de solver, especialmente uno parecido a un jugador humano.
Puede utilizar características como:
- técnicas necesarias;
- cantidad de pasos;
- dependencias;
- carga de reconocimiento;
- cuellos de botella;
- opciones productivas disponibles.
Así, valorar dificultad se parece a construir un modelo de coste computacional humano, no a contar pistas.
Por qué distintos solvers de sudoku sirven para trabajos distintos
Solver completo / contador de soluciones
Busca de forma exhaustiva el espacio necesario para responder preguntas de existencia y unicidad.
Puede utilizar backtracking, exact cover u otros algoritmos completos.
Solver de estilo humano
Aplica un repertorio explícito de técnicas de resolución y produce pasos explicables.
Sirve para enseñar, analizar rutas y comprobar si un puzzle requiere cierto tipo de lógica.
Analizador de dificultad
Evalúa la ruta producida por un solver de estilo humano y transforma sus propiedades en una puntuación o etiqueta de dificultad.
Generador
Construye o modifica puzzles y combina otros componentes para comprobar validez, unicidad, resolubilidad, dificultad y preferencias de diseño.
No existe una única arquitectura obligatoria, pero separar estos trabajos ayuda a evitar confundir «resolver una cuadrícula» con «explicar cómo la resolvería una persona».
FAQ
¿El sudoku se basa en aritmética?
No. Los dígitos funcionan como símbolos distintos y no necesitas sumar, restar, multiplicar ni dividir para resolver sudoku clásico.
¿Toda cuadrícula completa de sudoku es un cuadrado latino?
Sí. Cumple la condición de que cada símbolo aparece una vez en cada fila y columna, además de las restricciones 3×3.
¿Todos los cuadrados latinos 9×9 son cuadrículas válidas de sudoku?
No. También deben cumplir las nueve restricciones de bloques 3×3.
¿Cuántas cuadrículas completas de sudoku clásico existen?
6.670.903.752.021.072.936.960.
¿Cuántas cuadrículas completas esencialmente diferentes existen?
5.472.730.538 si agrupamos las cuadrículas relacionadas mediante las simetrías estándar del sudoku.
¿Por qué existen tantas cuadrículas si las reglas son tan sencillas?
Porque las restricciones permiten un espacio combinatorio enorme de permutaciones compatibles.
¿El sudoku es NP-completo?
El problema de decisión para Sudoku generalizado es NP-completo. Eso no significa que resolver una instancia fija 9×9 sea difícil para un ordenador moderno.
¿Algorithm X es una técnica humana de sudoku?
No en el sentido habitual. Es un algoritmo general para problemas de exact cover y resulta muy útil en solvers completos.
¿El enorme número de cuadrículas solución determina la dificultad de un puzzle?
No. La dificultad humana depende de la ruta lógica requerida por un conjunto concreto de pistas, no del tamaño total del espacio de cuadrículas válidas.
Qué aprender después
Lee Teoría del sudoku para el mapa general.
Después explora Cómo se generan los sudokus, Cómo se valora la dificultad del sudoku, Pistas mínimas, Simetría en sudoku y Cómo resuelven sudoku los ordenadores para profundizar en cada una de estas conexiones.