Em sistemas especialistas, Backtracking designa um modo de resolução de problemas no qual o programa busca soluções alternativas para tentar encontrar o motivo do problema. O cenário habitual é que nos deparamos com uma série de opções, e devemos escolher uma delas. Depois de ser feita uma escolha irá ter um novo conjunto de opções. O conjunto de opções depende da que escolha que foi feita. Este procedimento é repetido várias vezes até chegar a um estado final. Se for feita uma boa sequência de escolhas, o seu estado final é um estado “meta”. Nós começamos na raiz de uma árvore em que essa árvore provavelmente tem algumas boas folhas e algumas folhas ruins. Podemos chegar a uma boa folha. Supondo que cheguemos a uma folha má, podemos recuar para continuar a busca de uma boa folha, revogando sua escolha mais recente, e experimentar a próxima opção noutro conjunto de opções. Se ficarmos sem opções, revogamos a escolha e tentamos outra escolha naquele nó.
Recursão é a chave na programação backtracking. Como o nome sugere, requer recuar para encontrar a solução. Começamos com uma possível solução dentro de várias outras disponíveis e tentaremos resolver o problema. Se formos capazes de resolver o problema com o movimento selecionado, então vamos imprimir a solução senão vamos voltar atrás e seleccionar outro movimento e tentar resolvê-lo. Se nenhum desses movimentos resultarem chegamos à conclusão que não há solução para o problema.
Abaixo temos uma imagem de um sudoku que é resolvida com programação backtracking (tentativa e erro):
