#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