Symmetric Sudoku-Type Games from Perfect Codes

Resumen Técnico: Juegos de Tipo Sudoku Simétricos a Partir de Códigos Perfectos

Enunciado del Problema
Mientras que el Sudoku estándar de $9 \times 9$ es un objeto combinatorio bien estudiado con rica simetría, muchas variantes (como el Sudoku de Piezas) alteran las particiones de la cuadrícula de maneras que destruyen las simetrías rotacionales y reflexivas. Esta pérdida de simetría hace que muchas estrategias de resolución estándar y herramientas teóricas sean inaplicables. El artículo aborda la necesidad de un marco generalizado para construir juegos de tipo Sudoku que preserven altos niveles de simetría análogos al juego clásico, mientras ofrecen nuevas variaciones estructurales.

Metodología
Los autores proponen un método de construcción basado en códigos perfectos de distancia Lee y códigos perfectos de diámetro sobre anillos de enteros módulo $n$ ($\mathbb{Z}_n$).

1. Fundamento Teórico: El método utiliza la "propiedad de teselado" de estos códigos. Un código perfecto $C$ particiona el espacio $\mathbb{Z}_n^2$ en bolas disjuntas de radio $t$. Un "código perfecto de diámetro" logra la igualdad en el Límite Código-Anticódigo, particionando el espacio utilizando anticódigos de un diámetro específico.
2. Construcción de la Cuadrícula:
   • Se construye una cuadrícula de paleta $I$ donde cada celda $(x, y)$ se asigna un símbolo basado en qué bola de palabra código (o traslación de anticódigo) contiene esa coordenada.
   • Una cuadrícula de Sudoku $S$ se define como un cuadrado latino de orden $n$ que es ortogonal a la cuadrícula de paleta $I$. Esta ortogonalidad asegura que cada símbolo aparezca exactamente una vez dentro de las regiones definidas por el teselado del código.
3. Relaciones de Equivalencia: Los autores definen clases de equivalencia para las cuadrículas resultantes bajo:
   • Reetiquetado: Permutación de símbolos.
   • Movimientos Rígidos: Un grupo específico $G_S$ generado por rotaciones, reflexiones y traslaciones que preservan la estructura subyacente del código.
4. Estudios de Caso: El marco se aplica a dos casos mínimos:
   • Sudoku de $5 \times 5$: Construido a partir de un código perfecto de corrección de 1 error en $\mathbb{Z}_5^2$ (donde $n=5$).
   • Sudoku de $8 \times 8$: Construido a partir de códigos perfectos de diámetro 3 en $\mathbb{Z}_8^2$ (donde $n=8$).
5. Evaluación de Dificultad: Se implementa un "resolutor similar a un humano" para evaluar la jugabilidad. Este resolutor utiliza únicamente deducciones lógicas elementales (Único Desnudo y Único Oculto) combinadas con una fase de prueba y error. La dificultad se cuantifica mediante el número de inserciones de prueba y error requeridas más allá de las pistas iniciales.

Contribuciones y Resultados Clave

• Enumeración de Soluciones:
  • Para el caso de $5 \times 5$, los autores identificaron 2,040 cuadrículas válidas. Hasta el reetiquetado y la acción del grupo de movimientos rígidos, estas se reducen a 17 soluciones no equivalentes.
  • Para el caso de $8 \times 8$, se analizaron dos tipos distintos de códigos perfectos de diámetro. El primer tipo produjo aproximadamente $2.80 \times 10^{11}$ cuadrículas válidas, reduciéndose a 232,735 soluciones no equivalentes. El segundo tipo produjo aproximadamente $1.95 \times 10^{11}$ cuadrículas válidas, reduciéndose a 304,014 soluciones no equivalentes.
• Análisis de Sudoku Mínimo:
  • Para el caso de $5 \times 5$, los autores enumeraron los puzzles de Sudoku mínimos (aquellos con el número mínimo de pistas requeridas para una solución única). Encontraron un total de 15,898,200 puzzles mínimos (35,759 hasta la equivalencia) con conteos de pistas que van de 4 a 7.
  • Para el caso de $8 \times 8$, se consideró que una enumeración completa de puzzles mínimos era computacionalmente inviable. En su lugar, los autores identificaron puzzles mínimos con conteos de pistas que van de 10 a 18.
• Cuadrículas Especiales: El estudio identificó "cuadrículas de Sudoku especiales" que satisfacen las restricciones de Sudoku para cualquier código perfecto de los parámetros dados, no solo para el específico utilizado en la construcción. Hay 240 de tales cuadrículas para $5 \times 5$ y $4 \times 8!$ para $8 \times 8$.
• Distribución de Dificultad: El análisis de los juegos de $5 \times 5$ utilizando el resolutor similar a un humano reveló una distribución equilibrada de niveles de dificultad. Los puzzles se clasificaron como Fáciles (puntuación 0), Medios (puntuación 1–10) y Difíciles (puntuación >10). Los resultados mostraron una mezcla viable de dificultades, con muchos puzzles resolubles por lógica básica y otros que requieren una prueba y error significativa.

Significado y Afirmaciones
El artículo afirma que los códigos perfectos proporcionan un marco sistemático y matemáticamente riguroso para generar juegos de tipo Sudoku simétricos. El significado principal radica en demostrar que:

1. Preservación de Simetría: A diferencia de las variantes irregulares, estas construcciones basadas en códigos preservan inherentemente las simetrías rotacionales y reflexivas encontradas en el Sudoku clásico, permitiendo la aplicación de análisis grupal estándar.
2. Diversidad Estructural: El marco genera cuadrículas válidas estructuralmente diversas, expandiendo el panorama del Sudoku más allá del formato estándar de $9 \times 9$.
3. Jugabilidad Práctica: El análisis de dificultad confirma que estos juegos no son meros constructos teóricos, sino que ofrecen "una distribución equilibrada de niveles de dificultad, que van desde Fácil hasta Difícil", haciéndolos alternativas viables al Sudoku tradicional para el juego recreativo.

Los autores concluyen que este enfoque une la teoría de códigos y las matemáticas recreativas, ofreciendo una nueva vía para generar puzzles lógicos con estructuras algebraicas ricas. Se sugiere trabajo futuro para extender estas construcciones a otros anillos y métricas de distancia (por ejemplo, métricas de Mannheim o de rango).