À mes heures perdues, je m’amuse à créer des plugins WordPress. Certains répondent à un besoin précis, d’autres naissent simplement d’une question. Pour SudokuGrid, elle était toute simple : est-ce vraiment compliqué de créer un générateur de Sudoku ?
Pour les premières grilles, la réponse était plutôt non.
Un programme peut fabriquer une grille complète, supprimer progressivement certaines valeurs et contrôler qu’il ne reste qu’une seule solution. Avec cette méthode, obtenir des Sudokus accessibles ne demande pas une puissance de calcul démesurée. Les niveaux Bébé, Très facile, Facile et Moyen ont donc assez rapidement commencé à fonctionner.
Mais je ne voulais pas que la difficulté soit déterminée uniquement par le nombre de cases laissées visibles. Et c’est à ce moment-là que SudokuGrid est devenu un projet beaucoup plus sérieux.
La difficulté d’un Sudoku ne se compte pas en cases vides
Deux grilles comportant exactement le même nombre d’indices peuvent offrir des expériences radicalement différentes. L’une peut s’effondrer en quelques minutes avec des déductions évidentes, alors que l’autre impose de suivre les candidats et de repérer des configurations beaucoup plus subtiles.
Il fallait donc apprendre à SudokuGrid à résoudre ses propres créations comme le ferait un joueur.
Un moteur logique a progressivement été ajouté. Il sait notamment travailler avec les singles nus et cachés, les candidats verrouillés, les paires, les triplets et, pour les grilles les plus exigeantes, le X-Wing.
Le niveau n’est donc pas simplement attribué parce qu’une grille contient beaucoup de cases vides. SudokuGrid essaie de la résoudre et observe les techniques dont il a réellement besoin pour arriver au bout.
Cette approche fonctionne très bien. Elle a simplement un petit défaut : elle demande beaucoup plus de travail au serveur.
Quand l’hébergeur commence à souffrir
Chercher une grille Expert au hasard s’est rapidement révélé assez violent.
Il fallait générer une solution, retirer des chiffres, contrôler régulièrement que le Sudoku restait unique, lancer le solveur logique, rejeter le candidat s’il était trop facile ou au contraire hors de portée du moteur, puis recommencer.
Encore et encore.
Une recherche pouvait ainsi produire des centaines de grilles complètes, rencontrer des dizaines de milliers de candidats et effectuer des milliers d’analyses logiques avant de tomber enfin sur la configuration recherchée.
Pour les niveaux avancés, et particulièrement Expert, les erreurs 503 ont rapidement rappelé qu’un hébergement web n’était pas une ferme de calcul. Demander ce genre de travail à chaque visiteur aurait évidemment été absurde.
Le fonctionnement du générateur a donc été repensé.
Trouver les bonnes grilles une fois, puis les transformer
SudokuGrid utilise désormais une bibliothèque de modèles préalablement certifiés.
Un outil d’administration spécifique recherche ces modèles en effectuant le travail lourd en amont. Lorsqu’il pense avoir trouvé une bonne grille, plusieurs vérifications sont effectuées : elle doit être valide, ne posséder qu’une seule solution, pouvoir être terminée par le solveur logique et surtout correspondre au niveau annoncé.
Le cas des grilles Expert est particulièrement parlant. Il ne suffit pas qu’une grille soit pénible à résoudre : elle doit résister aux techniques prévues pour les niveaux inférieurs, puis devenir solvable lorsque le moteur est autorisé à utiliser le X-Wing. Celui-ci doit réellement intervenir dans la résolution.
Une fois une telle grille trouvée, inutile de recommencer cette coûteuse recherche pour chaque partie.
C’est là qu’intervient le transformer de SudokuGrid. À partir d’un modèle validé, il peut modifier les chiffres, permuter certaines lignes ou colonnes, effectuer des rotations et appliquer différentes symétries. Le Sudoku prend une apparence différente tout en conservant sa structure logique.
Et par prudence, la grille transformée passe encore par les contrôles du moteur avant d’être envoyée au joueur.
Autrement dit, la partie compliquée est préparée en coulisses ; lorsqu’un visiteur demande une nouvelle grille, le serveur n’a plus besoin de partir à la chasse au X-Wing.
Six niveaux, mais aucune mécanique à comprendre
Toute cette machinerie est volontairement invisible pendant une partie.
SudokuGrid propose six niveaux : Bébé, Très facile, Facile, Moyen, Difficile et Expert. Une fois la difficulté choisie, il suffit de demander une nouvelle grille et de jouer.
L’interface apporte quelques aides sans transformer le Sudoku en sapin de Noël. La case active, sa ligne, sa colonne et son bloc sont distingués visuellement. Lorsqu’un chiffre est sélectionné, ses autres occurrences deviennent également plus faciles à repérer.
Un contrôle immédiat des erreurs peut être activé pour ceux qui le souhaitent. Les joueurs préférant chercher sans assistance peuvent simplement le laisser désactivé.
Pour les niveaux où garder les candidats en tête commence à devenir pénible, j’ai également ajouté une grille de brouillon. Il s’agit d’une petite copie indépendante du Sudoku dans laquelle on peut inscrire ses propres notes. Elle peut être affichée ou masquée selon les besoins et n’intervient jamais dans la résolution de la partie principale.
On peut même fermer la page
Un autre détail me paraissait indispensable : ne pas perdre une partie parce que l’on ferme son navigateur.
SudokuGrid conserve donc la progression localement. La grille en cours, les chiffres saisis et les annotations du brouillon peuvent être retrouvés après avoir quitté ou rechargé la page.
Le bouton Recommencer permet quant à lui de repartir du début sans demander un nouveau Sudoku. Comme il efface également la progression, une confirmation évite le clic malheureux.
Le résultat reste volontairement simple côté utilisateur, alors que derrière la grille travaillent un générateur, un solveur, un système d’évaluation de la difficulté, une bibliothèque de modèles et un moteur de transformation.
Beaucoup de code pour neuf chiffres
C’est probablement ce que je retiendrai de cette expérience : fabriquer un Sudoku est facile ; fabriquer le Sudoku que l’on prétend avoir fabriqué l’est beaucoup moins.
Le véritable défi a été de pouvoir annoncer « Difficile » ou « Expert » avec une justification logique derrière cette étiquette, tout en évitant de faire travailler le serveur pendant plusieurs minutes à chaque nouvelle partie.
SudokuGrid possède aussi ses propres outils de diagnostic. La bibliothèque entière peut être auditée afin de contrôler les modèles, leur unicité, leur résolution et le niveau détecté par le moteur. C’est particulièrement pratique lorsqu’une modification est apportée au solveur : je peux vérifier que les grilles précédemment validées se comportent toujours comme prévu.
Le projet était au départ une simple expérience destinée à satisfaire ma curiosité. Il est finalement devenu un véritable petit moteur de Sudoku.
SudokuGrid est aujourd’hui jouable directement sur pomey.com, ainsi que sur webpratique.ch.
SudokuGrid ne se contente pas de piocher toujours dans une petite collection de grilles figées. Le jeu s’appuie sur des modèles de Sudoku préalablement contrôlés, classés selon les techniques nécessaires à leur résolution : des simples naked singles des niveaux Bébé et Très facile jusqu’au X-Wing des grilles Expert.
Lorsqu’une nouvelle partie est demandée, SudokuGrid sélectionne un modèle correspondant au niveau choisi puis le transforme aléatoirement sans modifier sa logique ni sa difficulté. Les chiffres peuvent être entièrement permutés, tandis que lignes, colonnes, bandes et piles peuvent être réorganisées selon les transformations autorisées d’une grille de Sudoku. Des rotations et symétries peuvent également intervenir.
Une seule grille modèle peut ainsi donner naissance à un nombre considérable de variantes. En considérant l’ensemble des transformations mathématiquement possibles utilisées par le système, on atteint théoriquement plus de 1 000 milliards de présentations différentes pour un même modèle.
SudokuGrid dispose actuellement de 32 modèles validés, répartis sur six niveaux : 5 Bébé, 5 Très facile, 5 Facile, 7 Moyen, 7 Difficile et 3 Expert.
Le nombre théorique de variantes compte donc environ 39’000 milliards de variantes !
D’où vient ce nombre ?
Pour un seul modèle de Sudoku, le nombre théorique de transformations possibles peut s’écrire :
9! × (3!)8 × 2 × 4 = 1 218 998 108 160
Les différents éléments de cette formule correspondent aux transformations que SudokuGrid peut appliquer sans modifier la logique du Sudoku :
9! correspond à la permutation des chiffres de 1 à 9, soit 362’880 possibilités.
(3!)8 correspond aux permutations possibles des lignes et des colonnes : les trois lignes peuvent être permutées à l’intérieur de chacune des trois bandes, les bandes peuvent elles-mêmes être permutées, et le même principe s’applique aux colonnes et aux piles.
Autrement dit :
(3!)3 × 3! × (3!)3 × 3! = (3!)8
Enfin, 2 × 4 = 8 représente les huit symétries possibles du carré : quatre rotations (0°, 90°, 180° et 270°), avec ou sans réflexion.
On peut donc écrire la formule de manière plus parlante :
9! (chiffres)
× (3!)4 (lignes et bandes)
× (3!)4 (colonnes et piles)
× 8 (rotations et symétries)
Soit, en théorie, jusqu’à 1 218 998 108 160 transformations possibles pour un seul modèle.
Toutes ces variantes ne constituent pas de nouveaux problèmes mathématiques indépendants : elles sont des transformations de modèles existants et conservent leurs propriétés de résolution. Mais, pour le joueur, leur disposition et leurs chiffres changent, ce qui rend extrêmement improbable de retrouver exactement la même grille au fil des parties.
Cette méthode permet surtout à SudokuGrid de proposer une très grande variété de parties tout en conservant une difficulté contrôlée et vérifiée, plutôt que de générer au hasard des grilles dont le niveau serait imprévisible.
Et dire que tout ça est parti d’une question qui semblait anodine : « Ça doit être facile de programmer un générateur de Sudoku, non ? »
Pour l’installer sur votre site WordPress, suivez ce lien.
