#code #algorithme
Le backtracking est un algorithme permettant de trouver un ensemble de solutions parmi un “state-solution tree” et avec un contrainte donnée.
L’algorithme permet de construire incrémentalement une solution en faisant des “choix” puis en dé-faisant ces “choix” (e.g backtrack) plus tard pour trouver d’autres solutions. D’une certaine façon, le backtracking est un Depth First Search (DFS) du solution tree.
L’algorithme a toujours cette forme:
void backtrack()
if (solution is complete)
add solution to result
return
for choice in possible solutions
if choice is valid
make choice
backtrack()
undo choice