Retour sur trace

Levitin, dans son livre[2], donne une version récursive. On suppose ici qu'une solution candidate se représente avec des variables X[1..i] et que la i-ème variable X[i] est à valeurs dans S_i. L'algorithme générique du backtracking s'écrit comme suit :

entrée : X[1..i] les valeurs des i premières variables d'une potentielle solution
sortie : écrit toutes les solutions dont les premières variables valent X[1..i]
fonction backtrack(X[1..i])
    si X[1..i] est une solution
             écrire X[1..i]
    sinon
             pour tout élément x dans Si+1 consistant avec X[1..i] et les contraintes du problème
                      X[i+1] := x
                      backtrack(X[1..i+1])

L'algorithme débute avec backtrack(X[1..0]) où X[1..0] est le tuple vide (c'est la racine dans un arbre de recherche).

Dasgupta et al., dans leur livre, eux donne une version itérative[3] et reste plus abstrait quant aux contenus des nœuds de l'arbre de recherche, qu'ils appellent sous-problèmes :

commencer avec un problème P0 (c'est la racine de l'arbre)
S := {P0} l'ensemble des sous-problèmes actifs
tant que S est non vide
       choisir un sous-problème P de S
       retirer P de S
       développer P des sous-problèmes plus petits P1, ... Pk 
       pour chaque Pi    
               si Pi peut se voir comme une solution
                      s'arrêter et afficher la solution
               si Pi ne peut pas être étendue en une solution
                      oublier Pi   
               sinon
                      ajouter Pi à S
dire qu'il n'y a pas de solution

Les parties soulignées de l'algorithme ci-dessus dépendent du problème que l'on souhaite résoudre.

Les problèmes de satisfaction sont des problèmes ayant une solution complète, dans laquelle aucun ordre naturel des éléments n'existe. Ces problèmes se composent d'un ensemble de variables dont les valeurs sont assujetties à des contraintes spécifiques au problème. L'idée maîtresse consiste à essayer chaque possibilité (combinaison) jusqu'à trouver la bonne. Pour cela on examine les possibilités immédiates, puis si aucun blocage n'apparaît on continue sur les possibilités suivantes ; si un blocage apparaît, autrement dit s'il n'y a aucune possibilité, on revient au dernier cas examiné où une autre possibilité existait et on continue à partir de ce cas. Les langages de programmation déclaratifs, comme Prolog, permettent d'exprimer directement ces contraintes et effectuent cette recherche automatiquement.

On peut, dans un jeu que l'on programme, envisager un mouvement donné et ses suites. Il se peut que l'une des suites ne soit pas heureuse. On remonte alors à un point donné et on envisage un autre mouvement.

Couvrir une zone avec les pentominos peut se voir comme un problème de couverture exacte.

Le problème de la couverture exacte consiste à sélectionner des sous-ensembles de façon à obtenir une partition d'un ensemble d'éléments. Ce problème est intéressant car plusieurs autres problèmes, comme des pavages, ou résoudre un Sudoku peuvent se voir comme un problème de couverture exacte. Donald Knuth a inventé l'algorithme X[4], dédié à ce problème qui est un algorithme de retour sur trace, ainsi qu'une structure de données pour représenter une solution partielle : les liens dansants.