Propagación de restricciones
Cada casilla tiene un conjunto de candidatos {1..9}. Colocar un número lo elimina de la fila, columna y bloque 3×3. Si solo queda un candidato, la casilla está resuelta. Repetir hasta estabilidad.
Cuando la propagación no basta
Algunos puzles exigen adivinar. Backtracking: elegir la casilla con menos candidatos, probar uno, propagar. ¿Falla? Volver y probar el siguiente.
Dancing Links (DLX)
El Algorithm X de Knuth modela sudoku como Exact Cover: 729 tuplas (casilla, valor), 324 restricciones. DLX encuentra la selección que satisface cada restricción exactamente una vez. Resuelve los peores puzles en microsegundos.
Lecciones de game design
Los puzles resolubles solo por propagación se sienten lógicos. Los que fuerzan adivinar frustran. Los buenos diseñadores comprueban resolubilidad sin adivinar — la misma disciplina hace justos los niveles de Signal//Lock.
El límite matemático de 17 pistas
En 2012, se demostró mediante supercomputación que un Sudoku requiere un mínimo de 17 pistas para tener una solución única. Menos de 17 cifras garantizan múltiples soluciones, invalidando el puzzle. Este descubrimiento fijó el límite inferior para los algoritmos de generación y el estudio de grafos aplicado a celdas.
De Euler al diseño moderno
Aunque basado en los Cuadrados Latinos de Leonhard Euler, el Sudoku moderno fue creado por Howard Garns en 1979. Fue en Japón donde Maki Kaji estandarizó la simetría y el diseño manual de puzzles, asegurando que cada uno pueda resolverse mediante deducción lógica pura sin necesidad de adivinar.
El enfoque de satisfacibilidad
Muchos resolutores modernos emplean problemas de satisfacibilidad booleana (SAT) en lugar de simple búsqueda. Al convertir la rejilla en fórmulas lógicas, los algoritmos CDCL aprenden de las contradicciones encontradas. Esto permite resolver variantes complejas con miles de restricciones de forma casi instantánea, superando con creces la fuerza bruta tradicional.
El mínimo de 17 pistas
En 2012, Gary McGuire demostró computacionalmente que es imposible crear un Sudoku con solución única usando solo 16 pistas. Tras millones de horas de procesamiento, se confirmó que 17 es el límite matemático inferior; cualquier cifra menor resulta inevitablemente en múltiples soluciones válidas, invalidando el puzle.