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.