¿Cuál es el número mínimo de pistas que puede tener un Sudoku?
Última actualización
Un Sudoku válido - uno con exactamente una solución - requiere al menos 17 dígitos dados. Este es un resultado matemático probado. Cualquier rompecabezas con 16 o menos pistas tiene múltiples soluciones o ninguna.
La prueba de 2012
En 2012, Gary McGuire, Bastian Tugemann y Gilles Civario del University College Dublin publicaron una prueba de que no existe ningún Sudoku válido de 16 pistas. Su trabajo fue principalmente computacional: buscaron en el espacio completo de posibles cuadrículas de 16 pistas y verificaron que ninguna producía una solución única. La búsqueda requirió aproximadamente 7 millones de horas-núcleo de computación.
Antes de esto, se creía ampliamente que 17 era el mínimo y se habían encontrado experimentalmente miles de rompecabezas de 17 pistas. El equipo de McGuire proporcionó la primera prueba rigurosa de que 16 es imposible.
Cómo son los puzzles de 17 pistas
Los rompecabezas de 17 pistas son extremadamente escasos: 17 dígitos dados en 81 celdas, dejando 64 vacías. Se encuentran entre los rompecabezas más difíciles de resolver y generalmente requieren técnicas avanzadas. Encontrar rompecabezas válidos de 17 pistas en sí mismo requirió décadas de esfuerzo computacional. Hasta la fecha de redacción, se conocen más de 49,000 rompecabezas de Sudoku de 17 pistas esencialmente diferentes.
Qué significa esto para el diseño de puzzles
Los rompecabezas publicados dirigidos a solucionadores humanos rara vez bajan de 22 pistas. Los rompecabezas de dificultad Experto y Maestro típicamente usan 22-27 dígitos dados, mientras que los rompecabezas Fáciles usan 36-45. El mínimo de 17 pistas es un límite teórico: en la práctica, la resolubilidad con buena técnica y un camino de resolución agradable importan mucho más que el número de pistas por sí solo.