¿Qué hay detrás del Sudoku? Conteos combinatorios, coloreo de grafos, Exact Cover (DLX), medición de dificultad, unicidad y simetrías
matemática del sudoku • combinatoria • coloreo de grafos • exact cover (dlx) • unicidad
El Sudoku se asienta en la combinatoria. El número de cuadrículas 9×9 completas (válidas) ronda 6,67×1021. El conteo considera permutaciones de filas/columnas, bandas y pilas, y reduce simetrías. Los generadores suelen construir primero una solución completa y luego “retiran” pistas para obtener un rompecabezas lógico y de solución única.
Modelamos Sudoku como un problema de satisfacción de restricciones: 81 variables con dominio {1,…,9} y restricciones de unicidad por fila, columna y subcuadro 3×3. La resolución aplica filtrado de dominios, consistencia y búsqueda guiada. Las técnicas humanas (Naked/Hidden Singles, Pairs, X-Wing) son vistas “amigables” de estas operaciones lógicas.
Convertimos el tablero en un grafo de conflicto: nodos=celdas; aristas=misma fila/columna/caja. El objetivo es colorear con 9 colores (1–9) sin que nodos adyacentes compartan color. La caja 3×3 densifica el grafo, de ahí que patrones globales como X-Wing o Swordfish sean tan útiles.
Sudoku se reduce a Exact Cover: cada restricción debe satisfacerse exactamente una vez. Construimos una matriz binaria 729×324 con las cuatro familias de restricciones (celda, fila-dígito, columna-dígito, caja-dígito). El algoritmo DLX (Dancing Links) de Knuth explora esta matriz con retroceso muy eficiente, base de muchos solucionadores de alto rendimiento.
La dificultad no es “más vacíos = más difícil”. Importan (1) el contenido de información de las pistas (entropía media de candidatos), y (2) el coste de búsqueda (profundidad de cadenas lógicas necesarias). Un buen rompecabezas produce un flujo de información estable y evita callejones sin salida arbitrarios.
Un Sudoku de calidad es de solución única. En el 9×9 clásico, el mínimo conocido de pistas para garantizar unicidad es 17; con 16 no existe ejemplo clásico único. La simetría (rotaciones/reflexiones) aporta estética, pero demasiada simetría puede inducir soluciones múltiples si no se controla con restricciones adicionales.
Sudoku es la cara lúdica de ideas potentes: combinatoria, grafos, CSP y Exact Cover. Diseñar y resolver bien consiste en orquestar el flujo de información. Ponlo en práctica ahora en Ozerlyn Sudoku.