Un ordenador puede resolver un sudoku 9×9 extremadamente rápido, pero no existe un único “algoritmo de sudoku”. Diferentes solvers están diseñados para trabajos distintos.
Un solver completo intenta determinar si un puzzle tiene cero, una o múltiples soluciones.
Un solver de estilo humano intenta explicar el puzzle mediante técnicas lógicas con nombre y en un orden útil.
Un generador, validador o sistema de rating puede necesitar ambos.
Sudoku como problema de restricciones
Para cada celda, el programa mantiene un dominio de valores posibles.
Las constraints exigen:
- un dígito por celda;
- cada dígito una vez por fila;
- una vez por columna;
- una vez por box.
Cuando se fija un valor, los incompatibles se eliminan en otros lugares. Esto es propagación de restricciones, el equivalente computacional de actualizar candidatos después de una colocación humana.
Propagación de candidatos
Un solver sencillo puede repetir:
- calcular candidatos legales;
- colocar celdas forzadas;
- eliminar candidatos bloqueados por nuevas colocaciones;
- repetir hasta que no quede progreso directo.
Esto resuelve puzzles fáciles, pero no garantiza resolver cualquier sudoku válido.
Un solver completo necesita una forma de explorar alternativas cuando la propagación se detiene.
Backtracking
Backtracking es uno de los enfoques completos más simples.
- elige una celda no resuelta;
- prueba un candidato legal;
- propaga restricciones;
- si aparece una contradicción, deshaz la elección;
- prueba otro candidato;
- continúa hasta completar el grid o agotar alternativas.
Las implementaciones buenas eligen primero una celda muy restringida para reducir el branching.
Backtracking no es lo mismo que cómo VeyraPlay enseña a una persona. Es un método de búsqueda eficiente para una máquina.
Conteo de soluciones
Para validar unicidad, un solver no debe detenerse simplemente al encontrar una solución.
Puede seguir buscando hasta determinar:
- que no existe solución;
- que existe exactamente una;
- o que aparece una segunda solución, suficiente para demostrar que el puzzle no es único.
Esto es fundamental para generación y para usar con seguridad técnicas de unicidad.
Sudoku como exact cover
El sudoku clásico 9×9 puede codificarse como un problema de exact cover.
Hay cuatro familias de requisitos:
- 81 constraints de celda: cada celda recibe un valor;
- 81 de fila-dígito;
- 81 de columna-dígito;
- 81 de box-dígito.
Total:
81 × 4 = 324 constraintsHay 729 asignaciones fila/columna/dígito posibles:
9 × 9 × 9 = 729 filas candidatasAlgorithm X
Algorithm X es un procedimiento recursivo para resolver exact-cover.
En cada paso:
- elige una constraint aún no satisfecha;
- selecciona una fila candidata que la cubra;
- elimina las filas incompatibles y las constraints ya satisfechas;
- continúa recursivamente;
- retrocede si la elección conduce a un callejón sin salida.
Sudoku encaja especialmente bien porque cada colocación (fila, columna, dígito) satisface exactamente cuatro de las 324 constraints.
Dancing Links (DLX)
Dancing Links es una estructura de datos popularizada para implementar Algorithm X de forma eficiente.
Permite quitar y restaurar rápidamente filas/columnas de la matriz exact-cover durante la búsqueda.
No es un algoritmo diferente de Algorithm X:
- Algorithm X = estrategia de búsqueda exact-cover;
- DLX = técnica de representación/actualización que la hace rápida.
Constraint programming y modelos tipo SAT
Sudoku también puede expresarse como:
- Constraint Satisfaction Problem (CSP);
- SAT/Boolean constraints;
- integer programming;
- graph coloring y otras formulaciones.
Cada modelo traduce las mismas reglas a un lenguaje que un solver general puede procesar.
Esto es útil en investigación, verificación y sistemas donde Sudoku es solo una instancia de un motor de restricciones más amplio.
Solvers de estilo humano
Un human-style solver aplica técnicas como:
Singles → Locked Candidates → Subsets → Fish → Wings → Chains...
No busca solo la solución final. Registra qué deducción es válida en cada estado y puede elegir una política de pasos.
Eso permite:
- explicar soluciones;
- producir hints;
- construir ejercicios;
- valorar dificultad por técnicas;
- validar que un puzzle requiere realmente una idea concreta.
Por qué un solver completo y uno de estilo humano deberían estar separados
El solver completo responde:
¿cuántas soluciones tiene esta cuadrícula?
El human-style responde:
¿cómo puede progresar un solver lógico bajo este repertorio de técnicas?
Un puzzle puede tener una única solución y, sin embargo, ser imposible de resolver para un human-style solver limitado a técnicas sencillas.
Separar ambos conceptos evita confundir validez matemática con experiencia de resolución.
Cómo usa los solvers un generador
Un generador puede usar:
- un solver completo para comprobar unicidad después de quitar clues;
- un solver human-style para medir dificultad y ruta lógica;
- reglas editoriales para simetría, estilo y calidad;
- repetición hasta alcanzar el objetivo.
El solver no “diseña” automáticamente una buena experiencia; verifica propiedades dentro de un proceso de generación.
¿Los ordenadores adivinan?
Depende del solver.
Un algoritmo de búsqueda puede explorar alternativas mediante backtracking. Eso es completamente válido para un programa que necesita exhaustividad.
Un human-style solver puede configurarse para evitar búsqueda y producir solo deducciones explicables.
Por eso decir “el ordenador adivina” es demasiado impreciso: la pregunta correcta es qué modelo de resolución está utilizando.
FAQ
¿Cuál es el algoritmo más rápido para sudoku?
No hay una única respuesta universal. Backtracking optimizado, exact cover/DLX, SAT y otros métodos pueden resolver 9×9 muy rápido. La elección depende de si quieres velocidad, conteo de soluciones, explicación o integración con otro sistema.
¿Cuáles son las 324 constraints de exact cover?
81 de celda, 81 fila-dígito, 81 columna-dígito y 81 box-dígito.
¿Por qué hay 729 filas candidatas?
Porque existen 9 filas × 9 columnas × 9 posibles dígitos para una colocación (r,c,d).
¿Algorithm X es lo mismo que Dancing Links?
No. DLX es una implementación eficiente de las operaciones que usa Algorithm X.
¿Los solvers humanos usan backtracking?
Un solver diseñado para imitar resolución lógica normalmente no. Un solver completo sí puede usarlo internamente para verificar soluciones.
Qué aprender después
Continúa con Cómo se generan los sudokus, Sudoku y matemáticas y Cómo crear un sudoku para conectar estos algoritmos con construcción y dificultad.