À 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, la question était toute simple : est-ce vraiment compliqué de créer un générateur de Sudoku ? La réponse est non… jusqu’à un certain point. Les premières étapes ont été relativement simples. Générer une grille complète, retirer des chiffres tout en conservant une solution unique, puis créer plusieurs niveaux de difficulté ne pose pas de problème insurmontable. Pour les niveaux Bébé, Très facile, Facile ou Moyen, le générateur arrive assez facilement à produire des grilles adaptées.
Les choses se sont sérieusement corsées lorsqu’il a fallu créer de véritables grilles Difficiles et Expertes.
Générer une grille difficile ne suffit pas
Un Sudoku avec peu de chiffres n’est pas forcément difficile. Une grille très dépouillée peut parfois se résoudre avec des techniques élémentaires, tandis qu’une autre, comportant davantage d’indices, demandera des raisonnements beaucoup plus poussés.
Il fallait donc que SudokuGrid ne se contente pas de compter les cases remplies. Un solveur logique analyse chaque grille et reproduit différentes techniques utilisées par un joueur : single nu, single caché, candidats verrouillés, paires et triplets, jusqu’au X-Wing pour les grilles Expertes. C’est ce moteur qui détermine réellement le niveau d’une grille.
Et c’est là que mon serveur a commencé à beaucoup moins apprécier l’expérience.
Pour trouver aléatoirement une grille nécessitant réellement certaines techniques avancées, il faut générer énormément de candidats, vérifier leur unicité puis tenter de les résoudre logiquement. La recherche d’une grille Expert pouvait nécessiter des centaines de tentatives et des milliers d’analyses. Résultat : le serveur finissait régulièrement par abandonner avec une erreur 503.
Il fallait donc changer complètement d’approche.
Des modèles plutôt que de la force brute
J’ai finalement créé une sorte de chercheur de modèles. Son rôle n’est pas de servir les visiteurs, mais de travailler ponctuellement en administration pour dénicher de véritables grilles de référence.
Chaque modèle trouvé passe plusieurs contrôles. La grille doit avoir une solution unique, être entièrement résoluble par le moteur logique et correspondre réellement au niveau recherché. Pour une grille Expert, par exemple, le solveur doit confirmer que les techniques des niveaux précédents ne suffisent pas et qu’un X-Wing est effectivement nécessaire.
La recherche peut être assez brutale. Une seule grille Expert peut demander plusieurs minutes, des centaines de solutions complètes générées et des dizaines de milliers de candidats examinés.
Heureusement, ce travail n’a besoin d’être effectué qu’une fois.
SudokuGrid dispose ensuite d’un transformer capable de partir de ces modèles certifiés et de les modifier : permutation des chiffres, échanges de lignes ou de colonnes compatibles, rotations, symétries… La grille obtenue semble différente, mais conserve les propriétés logiques du modèle original. Un dernier contrôle vérifie malgré tout le résultat avant de le proposer au joueur : solution unique, résolution complète et niveau de difficulté correct.
On obtient ainsi une grande variété de Sudokus sans demander au serveur de rechercher un X-Wing au moment où quelqu’un clique sur « Nouvelle grille ».
Un Sudoku volontairement simple à utiliser
Côté joueur, toute cette mécanique reste invisible. On choisit simplement son niveau et SudokuGrid génère une nouvelle partie.
Le jeu propose six difficultés, de Bébé à Expert. Il peut signaler immédiatement une mauvaise réponse, met en évidence la ligne, la colonne et le bloc de la case sélectionnée et permet de jouer à la souris, au clavier ou sur un écran tactile.
Pour les grilles qui demandent davantage de réflexion, une petite grille de brouillon peut être affichée sous la partie. Elle permet de noter librement des candidats sans modifier le Sudoku principal.
La partie est également sauvegardée directement dans le navigateur. On peut fermer la page et revenir plus tard sans perdre sa progression ni son brouillon. Et si l’on souhaite repartir de zéro, le bouton « Recommencer » efface les réponses sans changer de grille.
De la petite expérience au véritable plugin
Ce qui devait au départ être un petit exercice de programmation s’est donc transformé en un projet nettement plus intéressant que prévu. Le plus compliqué n’a finalement pas été de générer des Sudokus, mais de s’assurer qu’ils correspondent réellement au niveau annoncé sans mettre le serveur à genoux.
SudokuGrid dispose aujourd’hui de son générateur, de son solveur, de son analyseur logique, de sa bibliothèque de modèles certifiés et de son système de transformation. Une page de diagnostic permet même de contrôler toute la bibliothèque et de vérifier automatiquement que chaque modèle possède toujours les caractéristiques attendues après une modification du moteur.
Et maintenant que mon hébergeur n’a plus à subir des centaines de recherches de X-Wing à la chaîne, SudokuGrid est disponible sur webpratique.ch et pomey.com. Tout ça parce qu’un jour, je me suis demandé si c’était compliqué de programmer un Sudoku.
Une version expurgée du générateur de modèles est disponible à l’installation pour votre site sous WordPress en suivant ce lien. Il s’installe en deux clics et ensuite, vous ajoutez le shortcode sudokugrid entre les deux crochets habituels [] ou vous voulez dans un article !
Republier cet article
Si vous aimez cet article, vous pouvez le partager ou le republier librement, sur votre site ou dans un journal, grâce à notre licence Creative Commons.
Mentionnez simplement la source et ajoutez un lien vers l’article d’origine. La reproduction doit être fidèle au texte original : il n’est pas permis de le modifier ni de le tronquer.Le bouton ci-dessous vous permet d'accéder au code préformaté. Copiez-le simplement dans l’éditeur de votre site. Cet article est mis à disposition selon les termes de la licence Creative Commons CC BY-NC-ND 4.0.
[…] Pour l’installer sur votre site WordPress, suivez ce lien. […]