En esta página
¿Cuántas pistas necesita como mínimo un sudoku clásico 9×9 para tener exactamente una solución?
La respuesta demostrada es:
17 pistas.
Existen sudokus únicos de 17 pistas, y una búsqueda computacional exhaustiva descartó la existencia de cualquier sudoku clásico 9×9 único de 16 pistas.
Pero esta respuesta necesita varios matices. Diecisiete no es un objetivo normal de construcción, no garantiza dificultad alta y no significa que cualquier conjunto de 17 pistas produzca un puzzle válido.
¿Qué se considera una pista de sudoku?
Una pista es un dígito que ya está colocado cuando comienza el puzzle.
También puede llamarse given en literatura inglesa.
Las pistas determinan el estado inicial. El jugador no puede modificarlas durante una resolución normal.
Cuando hablamos del problema de las pistas mínimas no contamos las cifras que el jugador coloca después. La pregunta es cuántos valores iniciales hacen falta para determinar una única cuadrícula completa.
Por qué la unicidad forma parte del problema de las pistas mínimas
Si solo preguntáramos cuántas pistas hacen falta para permitir alguna solución, la pregunta sería mucho menos interesante.
El problema clásico exige que el conjunto de pistas determine exactamente una solución.
Por eso un puzzle candidato debe cumplir dos condiciones globales:
- existe al menos una cuadrícula completa compatible con las pistas;
- no existe una segunda cuadrícula completa distinta compatible con esas mismas pistas.
El mínimo de 17 pertenece a este problema de unicidad.
Por qué 17 no era una respuesta evidente
Durante años se conocían muchos sudokus únicos de 17 pistas y no se había encontrado ninguno de 16.
Pero:
No haber encontrado un ejemplo no demuestra que sea imposible.
Para establecer que 17 era el mínimo global había que descartar todos los posibles conjuntos relevantes de 16 pistas, no simplemente probar una colección grande de puzzles.
El espacio de búsqueda es enorme. Por eso el resultado exigió una combinación de teoría y computación exhaustiva.
Cómo funcionó la prueba que descartó las 16 pistas
Gary McGuire, Bastian Tugemann y Gilles Civario desarrollaron una búsqueda exhaustiva que utilizaba estructura combinatoria para reducir el problema a casos comprobables.
Una de las ideas clave era estudiar conjuntos inevitables (unavoidable sets).
En lugar de intentar probar ciegamente todos los subconjuntos de 16 celdas, el método identifica estructuras que todo conjunto de pistas capaz de garantizar unicidad debe intersectar.
Después busca posibles conjuntos de pistas que cubran esas estructuras y verifica computacionalmente si alguno puede producir un sudoku único de 16 pistas.
Ninguno lo hace.
Eso convierte la observación empírica «nadie ha encontrado uno de 16» en un resultado mucho más fuerte:
No existe ningún sudoku clásico 9×9 de 16 pistas con solución única.
¿Qué es un conjunto inevitable?
Un conjunto inevitable es un conjunto de celdas de una cuadrícula solución con la propiedad de que cualquier puzzle único basado en esa solución debe contener al menos una pista dentro de ese conjunto.
¿Por qué?
Porque si ninguna de esas celdas estuviera fijada, existiría una transformación local que produciría otra solución compatible con las mismas pistas.
Por tanto, un conjunto de pistas que aspire a garantizar unicidad debe «golpear» o intersectar todos los conjuntos inevitables relevantes.
Esto conecta el problema con ideas de hitting set y cobertura combinatoria.
No es una técnica de resolución humana. Es una herramienta de análisis y búsqueda del espacio de construcciones posibles.
Por qué elegir 17 pistas al azar no basta
El número 17 es un límite inferior global, no una receta.
Si tomas una cuadrícula solución válida y revelas 17 celdas al azar, el resultado normalmente no tendrá una única solución.
Puede tener:
- muchas soluciones;
- ninguna estructura de resolución interesante;
- o simplemente no ser un puzzle apropiado.
Las posiciones de las pistas importan tanto como su número.
Puzzles mínimos frente a puzzles minimal
Los dos conceptos responden preguntas diferentes.
Puzzle con número mínimo de pistas
Un puzzle mínimo en sentido global alcanza la menor cantidad posible de pistas entre todos los sudokus clásicos 9×9 únicos.
Ese número es:
17.
Puzzle minimal
Un puzzle concreto es minimal cuando cada una de sus pistas es necesaria para mantener la unicidad.
Si puedes quitar una sola pista y el puzzle sigue teniendo solución única, entonces ese puzzle no era minimal.
Un puzzle minimal puede tener 18, 24, 30 o más pistas.
¿Todo sudoku único de 17 pistas es minimal?
Sí.
Si un sudoku único de 17 pistas tuviera una pista redundante, podríamos retirarla y obtener un sudoku único de 16 pistas.
Como sabemos que no existen sudokus clásicos 9×9 únicos de 16 pistas, toda pista de un sudoku único de 17 es necesariamente esencial.
Por tanto:
Todo sudoku clásico único de 17 pistas es minimal.
Lo contrario no es cierto:
No todo sudoku minimal tiene 17 pistas.
¿Puede existir una cuadrícula de 16 pistas?
Sí, si utilizamos «cuadrícula de 16 pistas» para describir simplemente un estado parcialmente rellenado.
Lo que no puede existir es un sudoku clásico 9×9 de 16 pistas con exactamente una solución.
Un conjunto de 16 pistas puede ser:
- inconsistente y no tener solución;
- compatible con varias soluciones;
- o simplemente un estado parcial que no pretende ser un puzzle publicado.
La imposibilidad se refiere específicamente a la combinación:
9×9 clásico + 16 pistas + solución única.
¿Menos pistas significa un sudoku más difícil?
No.
El número de pistas influye en el estado inicial, pero la dificultad humana depende de la ruta lógica que queda después.
Dos puzzles con números de pistas similares pueden requerir técnicas muy distintas.
Y un puzzle muy escaso puede abrirse con deducciones relativamente sencillas mientras otro con más pistas contiene un cuello de botella avanzado.
Por eso el clue count no debería utilizarse como sustituto de un modelo de dificultad.
Por qué los constructores no suelen perseguir el límite de 17 pistas
Llegar a 17 es interesante desde el punto de vista matemático, pero un buen puzzle editorial tiene otros objetivos.
Un constructor puede valorar:
- una ruta lógica limpia;
- técnicas concretas;
- una dificultad determinada;
- una distribución estética de pistas;
- progresión y ritmo;
- ausencia de ambigüedades o pasos poco elegantes.
Reducir pistas por reducirlas puede empeorar varios de esos criterios.
El número mínimo global es una frontera matemática, no una medida universal de calidad.
Pistas mínimas en variantes y otros tamaños de cuadrícula
El resultado de 17 pertenece al sudoku clásico 9×9 con sus filas, columnas y nueve bloques 3×3 estándar.
No debe trasladarse automáticamente a:
- Sudoku X;
- Killer Sudoku;
- Jigsaw Sudoku;
- tamaños 4×4, 6×6 o 16×16;
- puzzles con restricciones adicionales.
Cambiar las reglas cambia el problema matemático y puede cambiar completamente los límites de pistas.
Por qué importa este resultado
El resultado de las 17 pistas conecta varias capas del sudoku:
- combinatoria;
- unicidad;
- generación;
- búsqueda exhaustiva;
- estructuras inevitables;
- diseño de puzzles.
También ofrece un ejemplo claro de algo que se repite en toda la teoría del sudoku:
Una afirmación sencilla sobre el tablero puede esconder un problema computacional enorme.
FAQ
¿Cuál es el menor número de pistas en un sudoku clásico 9×9 único?
Diecisiete.
¿Existen sudokus únicos de 16 pistas?
No para el sudoku clásico 9×9. Una búsqueda exhaustiva demostró que ningún conjunto de 16 pistas puede determinar una única solución.
¿Quién demostró que son necesarias 17 pistas?
Gary McGuire, Bastian Tugemann y Gilles Civario establecieron el resultado mediante una búsqueda computacional exhaustiva basada en estructura combinatoria.
¿Todo sudoku de 17 pistas es único?
No. Puedes elegir 17 pistas que admitan múltiples soluciones. El resultado dice que existen puzzles únicos de 17 y que ninguno de 16 puede ser único.
¿Todo sudoku único de 17 pistas es minimal?
Sí. Si una pista fuera redundante podrías eliminarla y producir un sudoku único de 16 pistas, lo cual es imposible.
¿Todo sudoku minimal tiene 17 pistas?
No. Minimal significa que ninguna pista concreta puede retirarse sin perder la unicidad; un puzzle minimal puede tener más de 17 pistas.
¿Todo sudoku de 17 pistas es difícil?
No. El número de pistas no determina por sí solo la dificultad humana.
¿El límite de 17 pistas se aplica a las variantes de sudoku?
No automáticamente. Es un resultado específico del sudoku clásico 9×9 con sus restricciones estándar.
Qué aprender después
Lee Soluciones únicas de sudoku para entender qué significa exactamente que un conjunto de pistas determine una única cuadrícula.
Después consulta Cómo se generan los sudokus y Cómo se valora la dificultad del sudoku para ver por qué un constructor necesita mucho más que minimizar el número de pistas.