Backtracking

Le backtracking est un algorithme informatique de recherche d'une solution optimale en étudiant un arbre de décision. Afin d'optimiser les recherches, les branches d'exploration jugées improductives sont coupées au plus tôt.

Le problème des 8 reines consiste à placer huit reines sur un échiquier de 8x8 cases sans qu'elles ne puissent s'attaquer entre elles :

Quant au problème des cavaliers, il s'agit de trouver un parcours qui couvre toutes les cases de l'échiquier sans répéter de case :