Generación de Sudoku - Diseño del algoritmo de creación automática
Generar puzzles 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 puzzle 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 puzzle 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 puzzle, la solución debe ser única. Cada vez que se elimina una celda, hay que verificar que el puzzle 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 puzzle.
Control de la dificultad
La dificultad se define por la complejidad de las técnicas necesarias para resolver el puzzle. Se simula la resolución humana del puzzle 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 puzzle y se genera uno nuevo.
Reproducibilidad mediante semilla
Para implementar funciones como el desafío diario, donde todos los usuarios resuelven el mismo puzzle, 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 puzzle. Esto elimina la necesidad de almacenar puzzles en el servidor, ya que el cliente puede reproducir el mismo puzzle localmente.
Orden de eliminacion de celdas y simetria
Al eliminar celdas de una cuadricula completa, el orden de eliminacion y la simetria determinan tanto la calidad como el aspecto del rompecabezas generado. El enfoque mas simple elimina celdas una a una en orden aleatorio y restaura cualquier celda cuya eliminacion 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 simetria puntual, lo que da la elegante disposicion asociada al sudoku tradicional. Como las comprobaciones de unicidad se encarecen a medida que avanza la eliminacion, ordenar las celdas candidatas para provocar mas salidas tempranas acelera la generacion. El punto en que ya no se pueden eliminar mas celdas se acerca a la configuracion minima de pistas del rompecabezas.
Por que es dificil estimar la dificultad
La parte mas delicada de la generacion es estimar la dificultad. La dificultad suele definirse por la tecnica mas dificil requerida, pero la dificultad percibida del mismo rompecabezas cambia segun el camino del resolutor. Ademas, la escala no es lineal: subir un solo paso la tecnica requerida puede disparar la dificultad percibida. Las implementaciones usan un resolutor que imita los metodos 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 tecnicas que implemente el resolutor, asi que una tecnica ausente puede sobreestimar la dificultad. Un etiquetado de dificultad coherente exige que el resolutor cubra las tecnicas de forma exhaustiva.
Acelerar la verificacion de unicidad
La mayor parte del coste computacional de la generacion se dedica a verificar la unicidad. La fuerza bruta ingenua es lenta, asi que los generadores practicos usan varias optimizaciones. Incorporar propagacion de restricciones que pruebe primero la celda con menos candidatos reduce mucho la ramificacion inutil. Un resolutor que cuenta soluciones se configura para abortar en cuanto encuentra una segunda solucion, en lugar de enumerar todas. Usar un algoritmo para problemas de cobertura exacta como Dancing Links (DLX) agiliza aun mas el retroceso. La generacion es un proceso pesado, pero crear un solo rompecabezas para un reto diario se ejecuta con suficiente rapidez incluso en el lado del cliente.
Que hace bueno a un rompecabezas y la regeneracion
Lo que un generador debe buscar no es solo una solucion unica, sino un rompecabezas agradable de resolver. Las condiciones de un buen rompecabezas incluyen poder resolverse hasta el final solo con logica, no forzar un ensayo y error azaroso, y que la dificultad mostrada coincida con el reto real. Para cumplirlas, tras la generacion el resolutor reproduce el camino de resolucion para verificar que no hay ningun punto que exija adivinar y que puede resolverse con las tecnicas previstas. Los rompecabezas que fallan se descartan y se regeneran, asi que cuanto mayor es la dificultad objetivo, mas intentos de generacion hacen falta. Un diseno que prioriza la calidad de cada rompecabezas sobre la produccion en masa eleva, en ultima instancia, la satisfaccion de quienes juegan. Juzgar la dificultad solo por el numero de pistas es un error: algunos rompecabezas con pocas pistas se resuelven con fluidez, mientras que otros con muchas pistas aun exigen tecnicas avanzadas.