Problèmes de satisfaction de contraintes (CSP)

Le retour en arrière est l'action de retourner vers une variable précédant la variable courante dans la sous-séquence d'instanciation, de modifier la valeur affectée à celle-ci et de poursuivre la résolution par la suite.

L'algorithme de BT est donc un algorithme à deux phases.

1. Premièrement, une phase permettant d'avancer vers une prochaine variable à instancier et permettant d'étendre la sous-séquence et,
2. Deuxièmement, une phase de retour en arrière consistant à choisir la variable vers laquelle sera fait le retour en arrière dans la sous-séquence.

• Pas d’identification des causes de conflit
• Redondance
• Détection tardive des conflits