Sudoku FlowComment les ordinateurs résolvent le Sudoku
Mis à jour le 2026-10-05
Retour sur trace
Le solveur essaie un chiffre autorisé dans une cellule vide et poursuit. Si aucun chiffre ne mène à une solution, il annule un choix antérieur et en essaie un autre. Choisir d'abord la cellule ayant le moins de chiffres possibles raccourcit souvent considérablement la recherche.
Sources: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Couverture exacte et Dancing Links
Le Sudoku peut être reformulé comme un problème de couverture exacte : choisir des placements de sorte que chaque cellule et chaque chiffre dans chaque ligne, colonne et bloc soient couverts exactement une fois. Dans un article de novembre 2000, Donald Knuth a décrit Dancing Links, une méthode efficace pour exécuter son algorithme X de retour sur trace ; appliquée au modèle de couverture exacte du Sudoku, elle trouve rapidement toutes les solutions d'une grille.
Sources: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Recherche aléatoire
Certains programmes remplissent la grille au hasard, puis réorganisent les chiffres pour réduire le nombre de conflits, à l'aide de méthodes comme le recuit simulé ou les algorithmes génétiques. Ces méthodes ont été étudiées comme approches alternatives ; leur efficacité dépend du programme et de la grille.
Sources: Wikipedia: Sudoku solving algorithms
Des solveurs qui raisonnent comme des humains
Un moteur d'indices a une autre mission : trouver la réponse, mais aussi montrer la prochaine étape qu'une personne peut suivre. Le moteur de notre application essaie les techniques humaines dans un ordre fixe, des plus simples, comme le Singleton caché, aux plus difficiles, comme les chaînes et les ensembles presque verrouillés, et utilise la première qui permet de placer un chiffre ; les techniques plus difficiles commencent par éliminer des candidats. La technique la plus difficile qu'il utilise pour une grille détermine le niveau de cette grille dans l'application.
Sources: Ce que chaque niveau de Sudoku vous demande
Voir aussi
Related articles
- Les mathématiques du sudoku
- Comment la difficulté du Sudoku est évaluée
- Les règles du sudoku expliquées
