Symmetric Sudoku-Type Games from Perfect Codes

Résumé technique : Jeux de type Sudoku symétriques à partir de codes parfaits

Énoncé du problème
Alors que le Sudoku standard $9 \times 9$ est un objet combinatoire bien étudié possédant une riche symétrie, de nombreuses variantes (telles que le Jigsaw Sudoku) modifient les partitions de la grille de manière à détruire les symétries de rotation et de réflexion. Cette perte de symétrie rend inapplicables de nombreuses stratégies de résolution standard et outils théoriques. L'article répond au besoin d'un cadre généralisé pour construire des jeux de type Sudoku préservant des niveaux élevés de symétrie analogues à ceux du jeu classique, tout en offrant de nouvelles variations structurelles.

Méthodologie
Les auteurs proposent une méthode de construction basée sur les codes parfaits de distance de Lee et les codes parfaits de diamètre sur des anneaux d'entiers modulo $n$ ($\mathbb{Z}_n$).

1. Fondement théorique : La méthode exploite la « propriété de pavage » de ces codes. Un code parfait $C$ partitionne l'espace $\mathbb{Z}_n^2$ en boules disjointes de rayon $t$. Un « code parfait de diamètre » atteint l'égalité dans la borne Code-Anticode, partitionnant l'espace à l'aide d'anticodes d'un diamètre spécifique.
2. Construction de la grille :
   • Une grille palette $I$ est construite où chaque cellule $(x, y)$ se voit attribuer un symbole en fonction de la boule (ou de la translation d'anticode) du mot de code qui contient cette coordonnée.
   • Une grille Sudoku $S$ est définie comme un carré latin d'ordre $n$ qui est orthogonal à la grille palette $I$. Cette orthogonalité garantit que chaque symbole apparaît exactement une fois dans les régions définies par le pavage du code.
3. Relations d'équivalence : Les auteurs définissent des classes d'équivalence pour les grilles résultantes selon :
   • Étiquetage : Permutation des symboles.
   • Mouvements rigides : Un groupe spécifique $G_S$ généré par des rotations, des réflexions et des translations qui préservent la structure sous-jacente du code.
4. Études de cas : Le cadre est appliqué à deux cas minimaux :
   • Sudoku $5 \times 5$ : Construit à partir d'un code parfait de correction d'une erreur dans $\mathbb{Z}_5^2$ (où $n=5$).
   • Sudoku $8 \times 8$ : Construit à partir de codes parfaits de diamètre 3 dans $\mathbb{Z}_8^2$ (où $n=8$).
5. Évaluation de la difficulté : Un « résolveur de type humain » est implémenté pour évaluer la jouabilité. Ce résolveur n'utilise que des déductions logiques élémentaires (Unique nu et Unique caché) combinées à une phase d'essai et d'erreur. La difficulté est quantifiée par le nombre d'insertions par essais et erreurs requises au-delà des indices initiaux.

Contributions et résultats clés

• Énumération des solutions :
  • Pour le cas $5 \times 5$, les auteurs ont identifié 2 040 grilles valides. Jusqu'au relabeling et à l'action du groupe de mouvements rigides, celles-ci se réduisent à 17 solutions non équivalentes.
  • Pour le cas $8 \times 8$, deux types distincts de codes parfaits de diamètre ont été analysés. Le premier type a produit environ $2,80 \times 10^{11}$ grilles valides, se réduisant à 232 735 solutions non équivalentes. Le second type a produit environ $1,95 \times 10^{11}$ grilles valides, se réduisant à 304 014 solutions non équivalentes.
• Analyse des Sudokus minimaux :
  • Pour le cas $5 \times 5$, les auteurs ont énuméré les puzzles Sudoku minimaux (ceux avec le nombre minimum d'indices requis pour une solution unique). Ils ont trouvé un total de 15 898 200 puzzles minimaux (35 759 jusqu'à équivalence) avec des nombres d'indices allant de 4 à 7.
  • Pour le cas $8 \times 8$, une énumération complète des puzzles minimaux a été jugée irréalisable sur le plan computationnel. À la place, les auteurs ont identifié des puzzles minimaux avec des nombres d'indices allant de 10 à 18.
• Grilles spéciales : L'étude a identifié des « grilles Sudoku spéciales » qui satisfont les contraintes du Sudoku pour n'importe quel code parfait des paramètres donnés, et pas seulement celui spécifique utilisé pour la construction. Il existe 240 telles grilles pour $5 \times 5$ et $4 \times 8!$ pour $8 \times 8$.
• Distribution de la difficulté : L'analyse des jeux $5 \times 5$ à l'aide du résolveur de type humain a révélé une distribution équilibrée des niveaux de difficulté. Les puzzles ont été classés comme Faciles (score 0), Moyens (score 1–10) et Difficiles (score >10). Les résultats ont montré un mélange viable de difficultés, avec de nombreux puzzles résolubles par logique de base et d'autres nécessitant des essais et erreurs significatifs.

Signification et affirmations
L'article affirme que les codes parfaits fournissent un cadre systématique et mathématiquement rigoureux pour générer des jeux de type Sudoku symétriques. La signification principale réside dans la démonstration que :

1. Préservation de la symétrie : Contrairement aux variantes irrégulières, ces constructions basées sur les codes préservent intrinsèquement les symétries de rotation et de réflexion trouvées dans le Sudoku classique, permettant l'application d'une analyse de groupe standard.
2. Diversité structurelle : Le cadre génère des grilles valides structurellement diverses, élargissant le paysage du Sudoku au-delà du format standard $9 \times 9$.
3. Jouabilité pratique : L'analyse de la difficulté confirme que ces jeux ne sont pas de simples constructions théoriques mais offrent une « distribution équilibrée des niveaux de difficulté, allant du Facile au Difficile », les rendant des alternatives viables au Sudoku traditionnel pour le jeu récréatif.

Les auteurs concluent que cette approche fait le pont entre la théorie des codes et les mathématiques récréatives, offrant une nouvelle voie pour générer des puzzles logiques dotés de structures algébriques riches. Des travaux futurs sont suggérés pour étendre ces constructions à d'autres anneaux et métriques de distance (par exemple, les métriques de Mannheim ou de rang).