Les ordinateurs peuvent résoudre un Sudoku 9×9 ordinaire extrêmement vite, mais il n'existe pas un seul « algorithme Sudoku ». Les solveurs sont construits pour des objectifs différents.
Un solveur complet cherche à déterminer si un puzzle possède zéro, une ou plusieurs solutions.
Un solveur de style humain cherche à expliquer le puzzle en utilisant des techniques logiques nommées dans un ordre utile.
Un générateur, un validateur et un système d'évaluation de difficulté peuvent utiliser les deux.
Le Sudoku comme problème de contraintes
Pour chaque case, le programme suit un domaine de chiffres possibles.
Les contraintes imposent :
- un chiffre par case ;
- chaque chiffre une fois par ligne ;
- chaque chiffre une fois par colonne ;
- chaque chiffre une fois par bloc.
Lorsqu'une valeur est fixée, les valeurs incompatibles peuvent être retirées ailleurs. C'est la propagation de contraintes — l'équivalent informatique de la mise à jour des candidats après un placement humain.
Propagation des candidats
Un solveur simple peut répéter :
- calculer les candidats légaux ;
- placer les cases forcées ;
- retirer les candidats bloqués par les nouveaux placements ;
- recommencer jusqu'à ce qu'aucun progrès direct ne soit possible.
Cela suffit pour des puzzles faciles, mais pas pour tous les Sudoku valides.
Un solveur complet a besoin d'un moyen d'explorer des alternatives lorsque la propagation seule s'arrête.
Backtracking
Le backtracking est l'une des approches complètes les plus simples.
- choisissez une case non résolue ;
- essayez un candidat légal ;
- propagez les contraintes ;
- si une contradiction apparaît, annulez le choix ;
- essayez un autre candidat ;
- continuez jusqu'à trouver une grille complète ou jusqu'à l'échec de toutes les alternatives.
Les bonnes implémentations choisissent d'abord une case très contrainte afin de réduire le nombre de branches.
Le backtracking n'est pas la méthode que VeyraPlay enseigne à un humain. C'est une méthode de recherche efficace pour une machine.
Comptage des solutions
Pour valider l'unicité, un solveur ne doit pas s'arrêter simplement parce qu'il a trouvé une solution.
Il peut poursuivre jusqu'à ce que :
- aucune solution n'existe ;
- exactement une solution soit prouvée ;
- ou qu'une seconde solution soit trouvée, ce qui suffit à prouver la non-unicité.
C'est fondamental pour la génération et pour la sécurité des techniques d'unicité.
Le Sudoku comme exact cover
Le Sudoku classique 9×9 peut être encodé comme un problème d'exact cover.
Il existe quatre familles d'exigences :
- 81 contraintes de case : chaque case reçoit une valeur ;
- 81 contraintes ligne-chiffre ;
- 81 contraintes colonne-chiffre ;
- 81 contraintes bloc-chiffre.
Total :
81 × 4 = 324 contraintesIl existe 729 affectations ligne/colonne/chiffre possibles :
9 × 9 × 9 = 729 placements candidatsChaque placement satisfait exactement quatre contraintes pertinentes.
Le problème devient alors : sélectionner des lignes d'affectation qui couvrent chaque contrainte exactement une fois.
Algorithm X
L'Algorithm X de Donald Knuth est une méthode récursive pour résoudre les problèmes d'exact cover.
À chaque étape, il :
- choisit une contrainte non couverte ;
- sélectionne une ligne candidate qui la satisfait ;
- couvre les contraintes et lignes incompatibles ;
- appelle récursivement la même procédure ;
- effectue un backtracking si nécessaire.
La même méthode peut trouver une solution Sudoku ou énumérer suffisamment de solutions pour tester l'unicité.
Dancing Links (DLX)
Dancing Links est une structure de données et une technique d'implémentation efficace pour Algorithm X sur des matrices creuses.
La matrice d'exact cover 729×324 du Sudoku est creuse : chaque placement candidat ne touche que quatre contraintes.
DLX rend efficaces les opérations de couverture et de restauration de ces relations pendant la recherche récursive.
Algorithm X est l'idée de recherche ; Dancing Links est une technique d'implémentation célèbre de cette idée.
Programmation par contraintes et modèles de type SAT
Le Sudoku peut aussi être exprimé pour des systèmes de résolution généralistes :
- satisfaction de contraintes (CSP/CP) ;
- encodages SAT/booléens ;
- programmation entière ;
- représentations par graphes ou exact cover.
La meilleure représentation dépend de ce dont vous avez besoin : vitesse, explication, comptage, extensibilité aux variantes ou analyse de recherche.
Solveurs de style humain
Un solveur de style humain cherche des déductions nommées telles que :
- Singles ;
- Locked Candidates ;
- sous-ensembles ;
- Fish ;
- Wings ;
- Coloring ;
- Chains ;
- ALS.
Au lieu de demander seulement « puis-je trouver une solution ? », il enregistre un parcours de résolution.
Ce parcours peut servir à :
- fournir des indices ;
- créer des tutoriels ;
- évaluer la difficulté ;
- filtrer la qualité des puzzles générés ;
- identifier la technique qui débloque un puzzle.
Pourquoi séparer solveur complet et solveur de style humain
Un puzzle peut être facile pour le backtracking et difficile pour un humain.
Le coût d'une recherche machine ne correspond pas directement à la difficulté de reconnaissance humaine.
Une plateforme Sudoku robuste peut donc utiliser :
- solveur complet → validité et nombre de solutions ;
- solveur humain → explication et rating ;
- générateur → création de puzzles candidats ;
- analyseur → métadonnées et contrôles de qualité.
Comment un générateur utilise les solveurs
Lorsque des indices sont retirés d'une grille solution, un solveur complet teste si l'unicité est conservée.
Ensuite, un solveur de style humain peut demander :
- le puzzle est-il logiquement résoluble avec l'ensemble de techniques autorisé ?
- quelle est la technique la plus difficile réellement nécessaire ?
- combien d'étapes faut-il ?
- où se trouvent les goulots d'étranglement ?
- la technique souhaitée apparaît-elle réellement dans le parcours de résolution ?
C'est pourquoi « générer un Sudoku » signifie beaucoup plus que « supprimer des chiffres au hasard ».
Les ordinateurs devinent-ils ?
Les algorithmes de recherche explorent des alternatives, mais « deviner » n'est pas une description technique très utile.
Un solveur complet par backtracking énumère systématiquement un espace de recherche fini, élimine les branches impossibles grâce aux contraintes et fournit une preuve par exploration exhaustive.
Un Guide humain sur la devinette s'intéresse à autre chose : savoir si le joueur prend des engagements non justifiés pendant la résolution. Ce sont deux contextes différents.
FAQ
Quel est l'algorithme le plus rapide pour résoudre un Sudoku ?
Il n'existe pas de réponse universelle. Pour les grilles 9×9, le backtracking optimisé, exact cover/DLX et les solveurs de contraintes sont tous extrêmement rapides. Le choix dépend du besoin et de l'implémentation.
Quelles sont les 324 contraintes d'exact cover ?
81 contraintes de case, plus 81 ligne-chiffre, 81 colonne-chiffre et 81 bloc-chiffre.
Pourquoi existe-t-il 729 lignes candidates ?
Il y a 9 lignes × 9 colonnes × 9 chiffres possibles, soit une ligne d'exact cover pour chaque placement candidat potentiel.
Algorithm X est-il la même chose que Dancing Links ?
Non. Algorithm X est l'algorithme récursif d'exact cover ; Dancing Links est une technique de structure de données souvent utilisée pour implémenter efficacement les opérations de couverture/restauration.
Les solveurs Sudoku humains utilisent-ils le backtracking ?
Les solveurs logiques de style humain essaient généralement de l'éviter parce que l'objectif est d'obtenir un parcours de déductions explicable. Les validateurs complets utilisent couramment la recherche.
Que faut-il apprendre ensuite ?
Lisez le Guide Génération pour comprendre comment validateurs et solveurs humains s'intègrent dans le pipeline d'un puzzle, ou Comment créer un Sudoku pour le processus pratique de construction.