retour sur trace

Dans un sudoku, on peut inscrire un nombre autorisé dans une case vide, puis passer à la suivante. Si une case finit sans aucun nombre possible, le choix précédent était mauvais : on l’efface et on en essaie un autre.

Ce mouvement d’essai, de détection d’un blocage et de recul est le retour sur trace. L’ordinateur ne recommence pas nécessairement depuis le début : il reprend au dernier choix encore modifiable.

Le retour sur trace, aussi nommé algorithme de retour arrière ou backtracking, est une méthode générale de recherche pour les problèmes combinatoires, notamment les problèmes de satisfaction de contraintes. Elle construit une solution candidate par décisions successives. Chaque nœud de l’arbre de recherche représente une solution partielle, et chaque branche ajoute un choix.

Après chaque ajout, l’algorithme vérifie si la solution partielle peut encore être prolongée sans violer les contraintes. Si aucun prolongement valide n’existe, la branche est une impasse : l’algorithme remonte au dernier nœud où un autre choix reste disponible. Une solution complète est obtenue lorsque toutes les décisions demandées satisfont les contraintes ; selon l’objectif, la recherche peut alors s’arrêter ou continuer pour énumérer d’autres solutions.

L’abandon précoce d’une solution partielle invalide élague tout le sous-arbre qui en dépend. Ce gain n’est toutefois pas garanti sur chaque problème : si les contraintes détectent peu d’impasses avant les derniers niveaux, une grande partie des combinaisons peut encore être visitée. L’ordre des choix et la rapidité des tests influencent donc fortement le temps de recherche.

Considérons un mini-sudoku 4 × 4, découpé en blocs 2 × 2. Chaque ligne, colonne et bloc doit contenir une fois les nombres 1, 2, 3 et 4. Les lignes initiales sont :
· · 3 4
3 4 1 2
· 1 4 ·
· · · ·

1. Dans la case de la première ligne et de la première colonne, les contraintes autorisent 1 ou 2. Essayons d’abord 2.

2. La case suivante de la première ligne n’accepte alors aucun nombre : 1 figure déjà dans sa colonne, 2 est déjà dans la ligne, et 3 comme 4 sont aussi présents dans cette ligne. La branche est donc impossible. Cette bifurcation montre l’essai, l’impasse et le retour.

3. Revenons à la première case et choisissons 1. La case suivante est alors forcée à 2. En poursuivant les mêmes contrôles, on obtient les lignes 1 2 3 4 ; 3 4 1 2 ; 2 1 4 3 ; 4 3 2 1.

4. Le contrôle est refaisable : chacune des quatre lignes, des quatre colonnes et des quatre blocs 2 × 2 contient exactement 1, 2, 3 et 4. La grille complète satisfait donc toutes les contraintes annoncées.

Pour résoudre un sudoku, le retour sur trace choisit une case vide, teste une valeur compatible et annule ce choix si une case devient impossible. Une déduction directe reste préférable lorsqu’une seule valeur est autorisée ; l’essai intervient quand plusieurs choix subsistent.

Dans un problème d’emploi du temps, chaque décision peut affecter un horaire à une activité, sous réserve de disponibilités et d’absence de conflit. Si une affectation partielle empêche de placer une activité restante, l’algorithme revient sur une affectation antérieure.

Pour énumérer des configurations combinatoires, la méthode convient lorsque la validité d’une solution partielle se teste tôt. Une exploration exhaustive sans retour anticipé reste possible, mais elle examine aussi les prolongements de choix déjà incompatibles.

Retour sur trace et recherche exhaustive. Une recherche exhaustive énumère toutes les solutions complètes envisagées ; le retour sur trace peut abandonner une solution partielle dès qu’elle ne possède plus de prolongement valide. Dans le mini-sudoku, il rejette la branche commençant par 2 sans compléter le reste de la grille.

Retour sur trace et algorithme glouton. Un algorithme glouton conserve à chaque étape un choix jugé localement préférable, sans revenir normalement sur les décisions passées. Le retour sur trace, lui, mémorise des choix alternatifs : l’apparition d’une impasse déclenche précisément leur réexamen.

Un test trop faible élague peu. Si une contradiction n’est visible qu’au dernier choix, presque tout le sous-arbre est parcouru. Il faut tester les contraintes dès qu’elles deviennent décidables, sans rejeter une branche encore prolongeable.

Un rejet injustifié supprime des solutions. L’élagage est correct seulement si l’impasse prouve qu’aucune extension valide n’existe. Un simple choix peu prometteur ne suffit pas ; il faut alors ordonner les essais, pas déclarer la branche impossible.

Trouver une solution ne prouve pas son unicité. L’arrêt à la première grille complète établit seulement l’existence d’une solution. Pour tester l’unicité, la recherche doit continuer jusqu’à trouver une deuxième solution ou épuiser toutes les autres branches.

La terminaison dépend de l’espace exploré. Sur un arbre fini, l’examen systématique des choix finit par réussir ou épuiser les branches. Avec une profondeur non bornée, une branche infinie peut monopoliser la recherche ; une limite de profondeur ou une autre stratégie devient alors nécessaire.

algorithme — Situer le retour sur trace parmi les procédures finies, ordonnées et exécutables qui transforment des données en résultat.

analyse combinatoire — Replacer l’arbre de choix dans l’étude du dénombrement et des configurations discrètes.