VISI201 Backtracking (PICHENOT Simon)
Aller à la navigation
Aller à la recherche
Principe du backtracking
Le backtracking est une catégorie d’algorithme qui permet de résoudre des problèmes en explorant toutes les possibilités. Pour cela le principe est de choisir une variable du problème, et pour chaque affectation possible de cette variable tester si il y a une solution possible. Si aucune solution n'est trouvée, l'algorithme abandonne et revient sur l'affectation précédente.
Résolution de sudoku
Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.
Algorithme basique
Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide.