Para un sudoku estándar 9×9 que deba tener exactamente una solución, el número mínimo demostrado de pistas iniciales es:
17
Existen puzzles únicos con 17 pistas.
No existe ningún sudoku clásico único con 16 pistas.
Esta segunda afirmación fue establecida mediante una búsqueda computacional exhaustiva por Gary McGuire, Bastian Tugemann y Gilles Civario.
El resultado responde una pregunta matemática muy concreta. No significa que 17 pistas produzcan los mejores puzzles, los más difíciles ni los que un generador debería intentar crear preferentemente.
¿Qué se considera una pista?
Una pista es un dígito presente antes de que el jugador empiece.
También puede llamarse dado o número dado.
Un puzzle de 17 pistas comienza con:
- 17 celdas resueltas;
- 64 celdas vacías.
La solución completa sigue conteniendo 81 dígitos.
El número de pistas describe el estado inicial, no el tamaño de la solución.
Por qué la unicidad forma parte de la pregunta
Si la unicidad no importase, podríamos eliminar muchas pistas y dejar un estado inicial con enormes cantidades de soluciones posibles.
Eso no respondería al problema clásico del mínimo de pistas en sudoku.
La pregunta real es:
¿Cuál es el conjunto de pistas más pequeño que todavía determina una y solo una cuadrícula completa válida de sudoku clásico 9×9?
Esto combina dos requisitos:
- las pistas iniciales son compatibles con una solución;
- no existe una segunda solución.
Por qué 17 no era una respuesta evidente
Investigadores y coleccionistas de puzzles habían encontrado sudokus únicos válidos con 17 pistas.
Durante mucho tiempo nadie encontró un ejemplo de 16 pistas.
Pero:
«Nadie ha encontrado uno»
no es lo mismo que:
«No existe ninguno».
El reto consistía en demostrar que no podía ocultarse algún sudoku de 16 pistas todavía desconocido dentro del inmenso espacio de búsqueda.
El resultado que descarta las 16 pistas
McGuire, Tugemann y Civario transformaron el problema en una búsqueda computacional exhaustiva basada en conjuntos inevitables (unavoidable sets) y conjuntos de cobertura (hitting sets).
A grandes rasgos:
- partir de cuadrículas solución completas;
- identificar estructuras que un conjunto de pistas debe intersectar para que el puzzle resultante siga siendo único;
- formular las posiciones candidatas de las pistas como un problema de hitting set;
- enumerar eficientemente posibles conjuntos pequeños;
- comprobar exhaustivamente las posibilidades de 16 pistas;
- no encontrar ningún puzzle único de 16 pistas.
Así se establece el límite inferior:
Todo sudoku clásico 9×9 con solución única necesita al menos 17 pistas.
La demostración es computacional.
No es una pequeña prueba manual basada únicamente en contar celdas o unidades.
¿Qué es un conjunto inevitable?
Para una cuadrícula solución concreta, un conjunto inevitable es un grupo de celdas con la propiedad de que cualquier puzzle único basado en esa solución debe contener al menos una pista dentro de ese grupo.
¿Por qué?
Porque si todas las celdas del conjunto quedaran sin pista, podría sobrevivir una solución alternativa.
Por tanto, un conjunto válido de pistas debe «tocar» cada conjunto inevitable relevante.
Ahí aparece la formulación mediante hitting sets.
Para una página pública basta con esta intuición; el trabajo científico contiene los detalles computacionales.
Mínimo frente a minimal
Esta diferencia importa.
Puzzle con número mínimo de pistas
Utiliza el menor número global posible de pistas.
Para un sudoku clásico 9×9 único:
17 pistas.
Puzzle minimal
Cada una de sus pistas es necesaria para ese puzzle concreto.
Si eliminas cualquier pista, se pierde la unicidad.
Un puzzle minimal puede tener:
- 18 pistas;
- 24 pistas;
- más.
«Minimal» no significa «tiene 17».
Significa:
Ninguna de sus pistas es redundante para mantener la unicidad.
¿Todo puzzle de 17 pistas es automáticamente minimal?
Un puzzle único de 17 pistas no puede perder una pista y seguir siendo un sudoku clásico único, porque eso produciría uno de 16 pistas, algo que el resultado del mínimo descarta.
Por tanto, todo puzzle válido y único de 17 pistas es necesariamente minimal.
La afirmación inversa es falsa:
Un puzzle minimal no tiene por qué tener 17 pistas.
¿Puedo elegir 17 celdas cualesquiera de una cuadrícula solución?
No.
La mayoría de subconjuntos arbitrarios de 17 celdas no producirán un buen puzzle único.
Pueden:
- permitir múltiples soluciones;
- no tener solución si los números iniciales no se toman de forma coherente;
- no encajar con el modelo de resolución humana previsto;
- producir una dificultad no deseada o no compatible.
El límite global dice que existen algunos puzzles únicos de 17 pistas.
No dice que 17 pistas sean suficientes en posiciones arbitrarias.
¿17 pistas significa Experto?
No.
El número de pistas es una medida muy pobre de la dificultad humana por sí sola.
La dificultad también depende de:
- ubicación de las pistas;
- estructura de candidatos;
- técnicas necesarias;
- número de pasos;
- profundidad de dependencias;
- carga de reconocimiento.
Una cuadrícula muy vacía puede exponer lógica sencilla.
Una más llena puede esconder una cadena difícil.
Por eso Pistas mínimas y Valoración de dificultad son páginas Theory diferentes.
¿Puede un puzzle de 16 pistas tener varias soluciones?
Por supuesto.
El teorema descarta los sudokus clásicos únicos de 16 pistas.
Un estado inicial de 16 pistas puede:
- tener varias soluciones;
- no tener ninguna;
- parecer una cuadrícula parcial válida.
Simplemente no puede determinar exactamente una solución clásica.
Por qué esto importa a un generador
Sobre todo indica qué no debería optimizar un generador.
Un generador práctico debería buscar:
único
+ resoluble por humanos
+ dificultad calibrada
+ variado
+ reproducibleen lugar de:
el menor número posible de pistasUn generador obsesionado con reducir pistas al extremo puede consumir mucho cálculo para producir puzzles matemáticamente escasos pero no especialmente agradables.
El número de pistas sigue siendo un dato útil.
No es por sí solo el objetivo de diseño.
Investigación frente a juego
El resultado de las 17 pistas es fascinante porque describe un límite duro en la estructura combinatoria del sudoku.
Para jugar a diario, la pregunta más útil es:
¿Esta distribución concreta de pistas crea una ruta de resolución justa e interesante?
Son criterios de calidad diferentes.
Preguntas frecuentes
¿Cuál es el menor número de pistas de un sudoku clásico 9×9 único?
17.
¿Existen sudokus únicos de 16 pistas?
No. El caso de 16 pistas fue descartado mediante cálculo exhaustivo.
¿Todos los sudokus de 17 pistas son difíciles?
No.
¿Todo puzzle único de 17 pistas es minimal?
Sí, porque quitar una pista produciría un imposible puzzle único de 16 pistas.
¿Todo sudoku minimal tiene 17 pistas?
No.
¿Por qué el número de pistas no sirve para valorar la dificultad?
Porque la posición de las pistas y la estructura de deducciones resultante importan mucho más que el conteo bruto.
Qué aprender después
Lee Soluciones únicas de sudoku para entender la propiedad global de una sola solución.
Lee Cómo se generan los sudokus para ver el proceso práctico de retirada y validación de pistas.