Un casse-tête, deux problèmes d'algorithmique
Le Sudoku est un prétexte idéal pour montrer deux compétences distinctes : savoir résoudre une grille, et savoir en générer une bonne. Résoudre relève de la recherche exhaustive ; générer relève de la garantie — produire une grille qui n'admet qu'une seule réponse. Le tout tient en quelques kilo-octets de JavaScript, sans moteur ni dépendance, dans un rendu Canvas 2D.
Le solveur : un backtracking discipliné
Je résous par backtracking : je prends la première case vide, j'essaie un chiffre autorisé, je passe à la case suivante et je recommence. Dès qu'une case n'a plus aucun chiffre valide, je reviens en arrière et je change le choix précédent. C'est une exploration en profondeur de l'arbre des possibilités, où chaque impasse est annulée proprement. Le même code sert de moteur à tout le reste : validation, génération et révélation de la solution reposent sur cette unique fonction récursive.
Propager les contraintes plutôt que deviner
À chaque case, je ne teste jamais un chiffre au hasard : je vérifie qu'il ne viole aucune des trois contraintes du Sudoku — unicité sur la ligne, la colonne et le bloc de 3×3. Ces trois unités sont précalculées une fois pour toutes, et le jeu s'en ressert en direct pour surligner en rouge tout conflit que vous introduisez. Réduire l'espace des chiffres possibles avant de choisir, c'est ce qui transforme une recherche potentiellement gigantesque en un calcul quasi instantané.
Générer une grille à solution unique
C'est le point délicat. Je pars d'une grille pleine et valide, obtenue en lançant le solveur avec un ordre de chiffres aléatoire — d'où une grille différente à chaque partie. Puis je retire des cases une à une. Mais retirer trop, ou au mauvais endroit, casse l'unicité : la grille se met alors à admettre plusieurs solutions et cesse d'être un vrai Sudoku. Après chaque retrait, je relance donc un solveur qui compte les solutions et s'arrête net à la deuxième : s'il en existe plus d'une, j'annule le retrait. Inutile de savoir s'il y a cinq ou cinquante solutions — seul « plus d'une » compte, et cet arrêt précoce garde la génération rapide.
La preuve avant la livraison
Un générateur qui produirait, même rarement, une grille à deux solutions serait un bug silencieux : invisible à l'œil, fatal à l'usage. Avant d'intégrer cette démo, j'ai vérifié la génération sur des centaines de grilles, en comptant cette fois toutes les solutions de façon exhaustive, pour confirmer qu'il n'y en avait jamais qu'une. C'est exactement ma façon de travailler sur les projets sérieux : sur une brique dont la correction n'est pas négociable — un calcul de prix, une règle métier, une contrainte de cohérence — je ne me contente pas que « ça a l'air de marcher », je le prouve, et je vous livre un code dont vous pouvez rejouer la démonstration.
