Algorithmes de résolution des sudokus

Un puzzle Sudoku typique

Un Sudoku standard contient 81 cellules, dans une grille 9×9, et comporte 9 régions, chaque région étant l'intersection de la première, du milieu ou des 3 dernières lignes et des 3 premières colonnes, du milieu ou des dernières. Chaque cellule peut contenir un nombre de un à neuf, et chaque nombre ne peut apparaître qu'une seule fois dans chaque ligne, colonne et région. Un Sudoku commence avec quelques cellules contenant des nombres (indices) et le but est de résoudre les cellules restantes. Les bons Sudokus ont une solution.^{[réf. nécessaire]} Les joueurs et les enquêteurs utilisent un large éventail d'algorithmes informatiques pour résoudre les Sudokus, étudier leurs propriétés et créer de nouveaux puzzles, y compris des Sudokus avec des symétries intéressantes et d'autres propriétés.

Il existe plusieurs algorithmes informatiques qui résoudront des puzzles 9 × 9 (n = 9) en une fractions de seconde, mais une explosion combinatoire se produit lorsque n augmente, créant des limites aux propriétés du Sudokus qui peuvent être construites, analysées et résolues lorsque n augmente.

Techniques

Retour sur trace (backtracking)

Un Sudoku (en haut) en cours de résolution par retour sur trace. Chaque cellule est testée pour un nombre valide, reculant en cas de violation et avançant à nouveau jusqu'à ce que l'énigme soit résolue.

Un Sudoku conçu pour fonctionner contre l'algorithme de force brute.

Certains amateurs ont développé des programmes informatiques qui résoudront les puzzles de Sudoku à l'aide d'un algorithme de retour sur trace, qui est un type de recherche par force brute. Le retour sur trace est une recherche en profondeur (contrairement à une recherche en largeur ), car il explorera complètement une branche vers une solution possible avant de passer à une autre branche. Bien qu'il ait été établi qu'il existe environ 5,96 x 11 ²⁶ grilles finales, un algorithme de force brute peut être une méthode pratique pour résoudre les puzzles de Sudoku.

Un algorithme de force brute visite les cellules vides dans un certain ordre, en remplissant les chiffres de manière séquentielle ou en revenant en arrière lorsque le numéro s'avère non valide. En bref, un programme résoudrait une énigme en plaçant le chiffre « 1 » dans la première cellule et en vérifiant s’il est autorisé à s’y trouver. S'il n'y a aucune violation (vérification des contraintes de ligne, de colonne et de région), l'algorithme passe à la cellule suivante et place un « 1 » dans cette cellule. Lors de la vérification des violations, s'il s'avère que le "1" n'est pas autorisé, la valeur passe à "2". Si une cellule est découverte dans laquelle aucun des 9 chiffres n'est autorisé, l'algorithme laisse cette cellule vide et revient à la cellule précédente. La valeur de cette cellule est ensuite incrémentée de un. Ceci est répété jusqu'à ce que la valeur autorisée dans la dernière (81^e) cellule soit découverte.

L'animation montre comment un Sudoku est résolu avec cette méthode. Les indices du puzzle (chiffres rouges) restent fixes tandis que l'algorithme teste chaque cellule non résolue avec une solution possible. L'algorithme peut ignorer toutes les valeurs testées précédemment s'il constate que l'ensemble existant ne remplit pas les contraintes du Sudoku.

Les avantages de cette méthode sont :

• Une solution est garantie (tant que le puzzle est valide).
• Le temps de résolution n'est généralement pas lié au degré de difficulté.^{[Information douteuse]}
• L'algorithme (et donc le code du programme) est plus simple que les autres algorithmes, notamment par rapport aux algorithmes puissants qui garantissent une solution aux énigmes les plus difficiles.

L’inconvénient de cette méthode est que le temps de résolution peut être lent par rapport aux algorithmes modélisés d’après les méthodes déductives. Un programmeur a rapporté qu'un tel algorithme peut généralement nécessiter aussi peu que 15 000 cycles, voire jusqu'à 900 000 cycles pour résoudre un Sudoku, chaque cycle étant le changement de position d'un « pointeur » lorsqu'il se déplace dans les cellules d'un Sudoku.

Une approche différente, qui utilise également le retour sur trace, s'appuie sur le fait que dans la solution d'un sudoku standard, la distribution de chaque symbole individuel (valeur) doit être seulement l'un des 46 656 modèles. Dans la résolution manuelle du sudoku, cette technique est appelée superposition de motifs ou utilisation de modèles et se limite à remplir uniquement les dernières valeurs. Une bibliothèque avec tous les modèles possibles peut être chargée ou créée au démarrage du programme. Ensuite, chaque symbole donné se voit attribuer un ensemble filtré avec ces modèles, qui sont conformes aux indices donnés. Dans la dernière étape, la partie de retour sur trace proprement dite, les modèles de ces ensembles sont tentés d'être combinés ou superposés de manière non conflictuelle jusqu'à ce que la seule combinaison autorisée soit trouvée. L'implémentation est exceptionnellement simple lors de l'utilisation de vecteurs de bits, car pour tous les tests, seules des opérations logiques au niveau du bit sont nécessaires, au lieu d'itérations imbriquées sur les lignes et les colonnes. Une optimisation significative peut être obtenue en réduisant encore davantage les ensembles de modèles pendant le filtrage. En testant chaque modèle douteux par rapport à tous les ensembles réduits déjà acceptés pour les autres symboles, le nombre total de modèles restant à revenir en arrière est considérablement réduit.

Et comme pour toutes les techniques de force brute du sudoku, le temps d'exécution peut être considérablement réduit en appliquant d'abord certaines des pratiques de résolution les plus simples qui peuvent remplir certaines valeurs « faciles ».

Un Sudoku peut être construit pour lutter contre le retour sur trace. En supposant que le solveur fonctionne de haut en bas (comme dans l'animation), un puzzle avec peu d'indices (17), aucun indice dans la rangée du haut et une solution "987654321" pour la première rangée fonctionnerait à l'opposé de l'algorithme. Ainsi, le programme passerait beaucoup de temps à « compter » vers le haut avant d’arriver à la grille qui répond au puzzle. Dans un cas, un programmeur a découvert qu'un programme en force brute nécessitait six heures pour parvenir à la solution d'un tel Sudoku (bien qu'en utilisant un ordinateur datant de 2008). Un tel Sudoku peut aujourd’hui être résolu en moins d’une seconde grâce à une routine de recherche exhaustive et à des processeurs plus rapides.^{[réf. nécessaire]}

Recherche stochastique / méthodes d'optimisation

Le Sudoku peut être résolu en utilisant des algorithmes stochastiques (aléatoires). Un exemple de cette méthode consiste à :

1. Attribuer au hasard des numéros aux cellules vides de la grille.
2. Calculer le nombre d'erreurs.
3. "Mélanger" les nombres insérés jusqu'à ce que le nombre d'erreurs soit réduit à zéro.

On trouve alors une solution à l'énigme. Les approches pour mélanger les nombres incluent le recuit simulé, l'algorithme génétique et la recherche taboue. Les algorithmes stochastiques sont connus pour leur rapidité, bien que peut-être pas aussi rapides que les techniques déductives. Contrairement à ces dernières, cependant, les algorithmes d'optimisation ne nécessitent pas nécessairement que les problèmes soient résolubles logiquement, leur donnant ainsi le potentiel de résoudre un éventail plus large de problèmes. Les algorithmes conçus pour la coloration des graphiques sont aussi connus pour fonctionner bien avec le Sudokus. Il est également possible d'exprimer un Sudoku sous la forme d'un problème de programmation linéaire en nombres entiers. De telles approches se rapprochent rapidement d’une solution et peuvent ensuite utiliser des branchements vers la fin. L'algorithme du simplexe est capable de résoudre les Sudokus appropriés, indiquant si le Sudoku n'est pas valide (il n'a pas de solution). S'il existe plus d'une solution (Sudokus non approprié), l'algorithme du simplexe donnera généralement une solution avec des quantités fractionnaires de plus d'un chiffre dans certains carrés. Cependant, pour les Sudokus corrects, les techniques de pré-résolution de la programmation linéaire déduiront la solution sans avoir besoin d'itérations simplexes. Les techniques de pré-résolution pour la réduction des problèmes de programmation linéaire (LP) emploient les mêmes règles logiques que celles utilisées par les humains pour résoudre des Sudokus.

Programmation par contraintes

Un Sudoku peut aussi être représenté comme un problème de satisfaction de contraintes. Dans son article intitulé Sudoku as a Constraint Problem, Helmut Simonis expose divers algorithmes de raisonnement basés sur des contraintes qui peuvent être utilisés pour modéliser et résoudre ces problèmes. Certains solveurs de contraintes intègrent des méthodes spécifiques pour la modélisation et la résolution de Sudokus, et il est possible d'écrire un programme de moins de 100 lignes de code pour résoudre un Sudoku simple. Si le code fait usage d'un algorithme de raisonnement robuste, le recours à un mécanisme de retour en arrière ne serait nécessaire que pour les Sudokus les plus difficiles. Un algorithme combinant une approche basée sur un modèle de contraintes avec une stratégie de retour en arrière présenterait l'avantage d'un temps de résolution rapide, de l'ordre de quelques millisecondes, tout en conservant la capacité de résoudre tous les Sudokus.

Couverture exacte

Les énigmes de Sudoku peuvent être caractérisées comme un problème de couverture exacte, plus précisément, un problème d'ensemble de frappe exacte. Cette approche offre une description élégante du problème et permet une solution efficace. Modéliser le Sudoku comme un problème de couverture exacte et appliquer un algorithme tel que l'algorithme X de Knuth avec sa technique Dancing Links "constitue la méthode privilégiée pour trouver rapidement [mesurée en microsecondes] toutes les solutions possibles aux énigmes de Sudoku". Une alternative consiste à utiliser l'élimination de Gauss en conjonction avec la suppression de colonnes et de lignes.

Soit Q la matrice Sudoku 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9} et X représente une ligne, une colonne ou un bloc générique. N fournit des symboles pour remplir Q ainsi que l' index défini pour les 9 éléments de tout X . Les éléments donnés q dans Q représentent une fonction partielle de Q à N . La solution R est une relation totale et donc une fonction. Les règles du Sudoku exigent que la restriction de R à X soit une bijection, donc toute solution partielle C, restreinte à un X, est une permutation partielle de N.

Soit T={X:X est une ligne, une colonne ou un bloc de Q}, donc T a 27 éléments. Un arrangement est soit une permutation partielle, soit une permutation sur N. Soit Z l'ensemble de tous les arrangements sur N. Une solution partielle C peut être reformulée pour inclure les règles sous la forme d'une composition de relations A(un à trois) et B nécessitant des arrangements compatibles.

$Q\xrightarrow {A} T\xrightarrow {B} Z\quad {\text{with}}\quad A;B\subseteq C.$

a solution du puzzle implique des suggestions pour que le nouveau "q" entre dans "Q", résultant d'arrangements interdits C, le complément de Cdans Q×Z. Les outils pertinents dans le calcul des relations sont les résidus.

$A\backslash C={\overline {A^{T};{\bar {C}}}}$ mappe T à Z, et

$C/B={\overline {{\bar {C}};B^{T}}}$ mappe Q à T.

Voir également

• Sudoku
• Mathématiques du Sudoku
  • § Sudokus avec quelques indices (nombre minimum de données)
  • § Sudokus automorphes
• Explosion combinatoire (avec résumé du nombre de grilles du Sudoku par rapport aux carrés latins)
• Glossaire du Sudoku

Liens externes

• http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html Sudoku Explainer par Nicolas Juillerat (Populaire pour évaluer les Sudokus en général)
• http://gsf.cococlyde.org/download/sudoku sudoku par Glenn Fowler (populaire pour évaluer les Sudokus les plus difficiles, entre autres)
• Un algorithme crayon et papier pour résoudre des énigmes de Sudoku