Propagation de contraintes
Chaque case a un ensemble de candidats {1..9}. Placer un chiffre l'enlève de la ligne, colonne et bloc 3×3. S'il ne reste qu'un candidat, la case est résolue. Répéter jusqu'à stabilité.
Quand la propagation ne suffit pas
Certains puzzles exigent de deviner. Backtracking : choisir la case avec le moins de candidats, en essayer un, propager. Échec ? Revenir et essayer le suivant.
Dancing Links (DLX)
L'Algorithm X de Knuth modélise le sudoku comme un Exact Cover : 729 tuples (case, valeur), 324 contraintes. DLX trouve la sélection qui satisfait chaque contrainte exactement une fois. Résout les pires puzzles en microsecondes.
Leçons pour le game design
Les puzzles résolubles par seule propagation sont plaisants. Ceux qui forcent à deviner frustrent. Les bons concepteurs vérifient la résolubilité sans devinette — la même discipline rend les niveaux Signal//Lock équitables.
La limite des 17 indices
En 2012, des chercheurs ont prouvé qu'un Sudoku valide nécessite au moins 17 indices pour garantir une solution unique. Avec seulement 16 chiffres, l'ambiguïté logique est inévitable. Ce seuil mathématique montre que la difficulté d'une grille dépend de la structure des contraintes plutôt que du nombre de cases remplies.
L'origine architecturale du jeu
Inventé en 1979 par l'architecte américain Howard Garns sous le nom 'Number Place', le jeu s'inspire des Carrés Latins d'Euler. C'est ensuite au Japon, via la société Nikoli, qu'il a acquis ses lettres de noblesse et son nom actuel, en imposant une esthétique de symétrie et une résolution purement logique.
L'approche de satisfaisabilité
Les solveurs modernes traitent souvent le Sudoku comme un problème SAT. En traduisant la grille en logique propositionnelle (CNF), des algorithmes sophistiqués apprennent des conflits pour déduire la solution. Cette méthode est bien plus rapide que le simple backtracking pour résoudre des variantes complexes ou des grilles de grande taille.
Le seuil des 17 indices
En 2012, Gary McGuire a prouvé qu'un Sudoku nécessite au minimum 17 indices pour avoir une solution unique. Grâce à 7 millions d'heures de calcul, son équipe a démontré qu'une configuration à 16 indices est mathématiquement ambiguë, mettant fin à un vieux débat dans la théorie des graphes.