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.