Algorithmes de retour en arrière: récursif et recherche expliqués avec des exemples

Les exemples où le retour en arrière peut être utilisé pour résoudre des énigmes ou des problèmes incluent:

  1. Puzzles tels que huit reines puzzle, mots croisés, arithmétique verbale, Sudoku [nb 1] et Peg Solitaire.
  2. Problèmes d'optimisation combinatoire tels que l'analyse syntaxique et le problème du sac à dos.
  3. Langages de programmation logique tels que Icon, Planner et Prolog, qui utilisent le retour arrière en interne pour générer des réponses.

Exemple de problème (problème de la tournée du chevalier)

Le chevalier est placé sur le premier bloc d'un plateau vide et, se déplaçant selon les règles des échecs, doit visiter chaque case exactement une fois.

Chemin suivi par Knight pour couvrir toutes les cellules

Voici un échiquier avec 8 x 8 cellules. Les nombres dans les cellules indiquent le numéro de coup de Knight.

La solution du tour du chevalier - par Euler

Algorithme naïf pour la tournée de Knight

L'algorithme naïf consiste à générer toutes les visites une par une et à vérifier si la tournée générée satisfait les contraintes.

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } 

Algorithme de retour en arrière pour la tournée de Knight

Voici l'algorithme de Backtracking pour le problème de tournée de Knight.

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" ) 

Et voici une explication vidéo pour vous