Generación de Sudoku - Diseño del algoritmo de creación automática
Generar puzles de Sudoku de calidad no se logra simplemente colocando números al azar. Este artículo explica cómo garantizar la solución única, controlar la dificultad y conseguir una distribución estética de las pistas.
Los 3 pasos de la generación
La generación de un puzle de Sudoku se realiza en 3 pasos: (1) generar aleatoriamente un tablero completo válido, (2) eliminar celdas una a una verificando que se mantiene la solución única tras cada eliminación, (3) analizar la dificultad del puzle resultante y comprobar que coincide con la dificultad objetivo. Los pasos 2 y 3 son el núcleo que determina la calidad, y es donde se concentra la mayor parte del coste computacional.
Garantía de solución única
Para que funcione como puzle, la solución debe ser única. Cada vez que se elimina una celda, hay que verificar que el puzle resultante sigue teniendo una única solución. Esta verificación requiere usar un solver para contar el número de soluciones. En cuanto se encuentran 2 o más soluciones, se determina que no es única y se revierte la eliminación de esa celda. Esta verificación tiene un alto coste computacional, pero es imprescindible para garantizar la calidad del puzle.
Control de la dificultad
La dificultad se define por la complejidad de las técnicas necesarias para resolver el puzle. Se simula la resolución humana del puzle generado y se analiza qué técnicas son necesarias. Si se resuelve solo con Singles Desnudos es Fácil; si requiere Singles Ocultos es Medio; si necesita Pares Desnudos es Difícil; si requiere X-Wing es Maestro. Si no coincide con la dificultad objetivo, se descarta el puzle y se genera uno nuevo.
Reproducibilidad mediante semilla
Para implementar funciones como el desafío diario, donde todos los usuarios resuelven el mismo puzle, se asigna una semilla (seed) al generador de números aleatorios para garantizar la reproducibilidad. Se calcula la semilla a partir de la fecha, y la misma semilla siempre genera el mismo puzle. Esto elimina la necesidad de almacenar puzles en el servidor, ya que el cliente puede reproducir el mismo puzle localmente.
Orden de eliminación de celdas y simetría
Al eliminar celdas de una cuadrícula completa, el orden de eliminación y la simetría determinan tanto la calidad como el aspecto del rompecabezas generado. El enfoque más simple elimina celdas una a una en orden aleatorio y restaura cualquier celda cuya eliminación rompa la unicidad, pero esto tiende a producir disposiciones de pistas irregulares. Muchos rompecabezas eliminan dos celdas a la vez, reflejadas respecto al centro, para lograr simetría puntual, lo que da la elegante disposición asociada al sudoku tradicional. Como las comprobaciones de unicidad se encarecen a medida que avanza la eliminación, ordenar las celdas candidatas para provocar más salidas tempranas acelera la generación. El punto en que ya no se pueden eliminar más celdas se acerca a la configuración mínima de pistas del rompecabezas.
Por qué es difícil estimar la dificultad
La parte más delicada de la generación es estimar la dificultad. La dificultad suele definirse por la técnica más difícil requerida, pero la dificultad percibida del mismo rompecabezas cambia según el camino del resolutor. Además, la escala no es lineal: subir un solo paso la técnica requerida puede disparar la dificultad percibida. Las implementaciones usan un resolutor que imita los métodos humanos, comprobando en orden si el rompecabezas se resuelve solo con singles desnudos, si hacen falta singles ocultos, etc., y fijan la dificultad en el primer paso donde se atasca. Sin embargo, ese juicio depende del rango de técnicas que implemente el resolutor, así que una técnica ausente puede sobreestimar la dificultad. Un etiquetado de dificultad coherente exige que el resolutor cubra las técnicas de forma exhaustiva.
Acelerar la verificación de unicidad
La mayor parte del coste computacional de la generación se dedica a verificar la unicidad. La fuerza bruta ingenua es lenta, así que los generadores prácticos usan varias optimizaciones. Incorporar propagación de restricciones que pruebe primero la celda con menos candidatos reduce mucho la ramificación inútil. Un resolutor que cuenta soluciones se configura para abortar en cuanto encuentra una segunda solución, en lugar de enumerar todas. Usar un algoritmo para problemas de cobertura exacta como Dancing Links (DLX) agiliza aún más el retroceso. La generación es un proceso pesado, pero crear un solo rompecabezas para un reto diario se ejecuta con suficiente rapidez incluso en el lado del cliente.
Qué hace bueno a un rompecabezas y la regeneración
Lo que un generador debe buscar no es solo una solución única, sino un rompecabezas agradable de resolver. Las condiciones de un buen rompecabezas incluyen poder resolverse hasta el final solo con lógica, no forzar un ensayo y error azaroso, y que la dificultad mostrada coincida con el reto real. Para cumplirlas, tras la generación el resolutor reproduce el camino de resolución para verificar que no hay ningún punto que exija adivinar y que puede resolverse con las técnicas previstas. Los rompecabezas que fallan se descartan y se regeneran, así que cuanto mayor es la dificultad objetivo, más intentos de generación hacen falta. Un diseño que prioriza la calidad de cada rompecabezas sobre la producción en masa eleva, en última instancia, la satisfacción de quienes juegan. Juzgar la dificultad solo por el número de pistas es un error: algunos rompecabezas con pocas pistas se resuelven con fluidez, mientras que otros con muchas pistas aún exigen técnicas avanzadas.