Le générateur de grilles de sudoku de Foxy Sudoku a été spécialement développé pour notre site. Nous ne dépendons pas d'un logiciel tiers pour créer nos grilles, et nous pouvons donc le faire évoluer à notre guise.
Grands joueurs de sudoku nous-mêmes, nous avons été quelque peu déçus par les logiciels et les magazines grand public, où souvent les sudokus dits experts ou diaboliques peuvent être résolus en dix minutes avec des techniques de base. Il existe néanmoins quelques excellents générateurs, mais en général c'est l'ergonomie de jeu qui ne suit pas.
Sur Foxy Sudoku, nous tentons de réunir le meilleur des deux mondes. D'un côté un générateur capable de créer des grilles de qualité, intéressantes à jouer quelque soit votre niveau. De l'autre, une ergonomie de jeu équivalente aux meilleurs logiciels de sudoku.
La première étape consiste à générer la solution du sudoku, à savoir une grille carrée de 9 x 9 cellules respectant les règles du sudoku, où chaque chiffre n'est présent qu'une fois par ligne, par colonne et par région.
Nous prenons ensuite une cellule au hasard dans la grille, nous effaçons sa valeur, et nous faisons passer la grille ainsi modifiée à notre solveur pas à pas pour voir s'il arrive à la résoudre. S'il y parvient, nous recommençons avec une autre cellule. Dans le cas contraire, nous remettons la valeur effacée dans sa cellule et nous tentons d'en effacer une autre. Quand il n'est plus possible d'effacer aucune cellule, la génération est terminée et nous enregistrons la grille.
Vous l'aurez compris, le solveur joue un rôle central dans la génération des grilles. C'est lui qui nous assure que le contenu d'une cellule peut être effacé tout en conservant un sudoku résolvable de façon logique par un être humain. Il est donc également le principal vecteur d'amélioration du générateur. En effet plus nous lui « apprenons » de techniques de résolution, plus les sudokus générés auront une difficulté élevée.
Pour résoudre une grille de sudoku, le solveur a à sa disposition une liste de techniques de résolution aux difficultés croissantes. Cet ordre est forcément subjectif, chacun étant plus à l'aise avec certaines techniques que d'autres. En commençant par la technique la plus facile, il scanne la grille pour voir si celle-ci est utilisable. Si la grille ne présente aucune opportunité d'utilisation, il recommence avec la technique de niveau supérieur, et ainsi de suite jusqu'à trouver une technique utilisable. La technique est alors utilisée et ce processus recommence jusqu'à résolution complète de la grille ou qu'il s'arrête faute de technique pour continuer.
L'ordre d'utilisation des techniques par le solveur est le suivant :
Il n'est pas possible de prédire le niveau de difficulté des sudokus générés. Celui-ci est évalué à postériori suivant la méthode décrite ci-dessous. Les grilles à la difficulté élevée sont les plus rares.
Nos sudokus sont classés en six niveau de difficulté : débutant, facile, moyen, difficile, expert et diabolique.
Pour déterminer le niveau de difficulté d'une grille, nous lui attribuons quatre notes.
La première note, sur six points, est déterminée par le niveau de la technique la plus difficile nécessaire à la résolution de la grille :
| Note | Techniques |
|---|---|
| 1 pt | Candidat unique, candidat unique caché |
| 2 pts | Paire nue, triplet nu, intersection ligne-région types 1 & 2 |
| 3 pts | Paire cachée, triplet caché, quadruplet nu, quadruplet caché |
| 4 pts | X-Wing, XY-Wing, chaîne simple, Swordfish, XYZ-Wing |
| 5 pts | Jellyfish, rectangle interdit |
| 6 pts | - |
La seconde note, sur deux points, est déterminée par le nombre de techniques d'élimination de candidats (les techniques ne permettant pas de placer directement un chiffre dans une cellule) utilisées pour résoudre la grille. Huit techniques d'élimination ou plus rapportent deux points. Entre quatre et huit, un point. Zéro sinon.
A noter que ce nombre d'utilisation est pondéré par un coefficient inversement proportionnel au nombre d'opportunité d'utilisation de la technique. Par exemple, si la grille requiert d'utiliser un X-Wing, et que plusieurs X-Wings différents permettent de poursuivre la résolution, alors l'utilisation de ce X-Wing rapporte moins d'un point. Ceci est également valable pour la note suivante.
La troisième note, sur un point, est déterminée par le nombre d'utilisation de techniques de niveau quatre ou plus (en référence au tableau de la première note) nécessaires à la résolution de la grille. Si ce nombre d'utilisations est supérieur ou égal à trois, cela rapporte un point. Zéro sinon.
La quatrième et dernière note, sur un point également, est déterminée par le nombre de techniques distinctes de niveau quatre ou plus nécessaires à la résolution de la grille. Si ce nombre est supérieur ou égal à trois, cela rapporte un point. Zéro sinon.
Mises bout à bout, ces quatre notes nous permettent de déterminer le niveau de difficulté de la grille suivant ce tableau :
| Difficulté | Notes |
|---|---|
| Débutant | 1000 |
| Facile | 2000 |
| Moyen | 2100, 2200, 3000, 3100, 3200 |
| Difficile | 4*** où la somme *** est inférieure ou égale à 2/4 |
| Expert |
4*** où la somme *** est supérieure où égale à 3/4 5*** où la somme *** est inférieure ou égale à 2/4 |
| Diabolique |
5*** où la somme *** est supérieure où égale à 3/4 6*** |