Noções básicas sobre retrocesso em C ++

Eu tenho um bom entendimento básico dos fundamentos do C ++, também tenho um entendimento de como a recursão também funciona. Me deparei com certos problemas, como o clássico problema das oito rainhas e a solução de um Sudoku com Backtracking.

Percebo que estou bastante perdida no que diz respeito a isso, não consigo entender o conceito de voltar à pilha de recursão e começar de novo para resolver o problema. Parece fácil com caneta e papel, mas quando se trata de escrever código para isso, estou confuso sobre como começar a atacar esses problemas.

Seria útil se houvesse um tutorial voltado para iniciantes em retroceder ou se houvesse um bom livro onde isso fosse abordado. Se alguém puder esclarecer esse tópico ou me fornecer alguns links para referências decentes, ficaria muito grato.

E sim, eu sei que seria mais fácil em linguagens funcionais, mas eu gostaria de entender a implementação em linguagens imperativas também.

... Parece que não consigo entender o conceito de voltar à pilha de recursão e começar de novo para resolver o problema.

No retrocesso, você não está iniciando novamente. Em vez disso, você percorre todas as opções na situação atual.

Pense em encontrar solução para um labirinto. Em um ponto em que você tem dois caminhos diferentes, tente primeiro o esquerdo. Se o esquerdo não o levar à saída, você retornará ao ponto e tentará o outro caminho. É assim que o retrocesso funciona. Em 8 Q e outros problemas em que o backtracking pode ser usado, a parte confusa está no domínio do problema - como iterar suas opções em uma determinada situação de maneira determinística.

EDIT : o seguinte é um pseudo-código que ajuda a entender o retrocesso.

# depending on the problem, backtracking is not necessarily calling the
# method itself directly. for now, let's just stick with the simple case.

def backtracking(state)
  option_list = state.get_all_options
  option_list.each {|option|
    state.apply option
    return resolved if state.is_resolved
    return resolved if backtracking(state) == resolved
    state.undo option
  }
  return not_resolved
end

Para a pergunta 8Q:

• state.get_all_options retornaria uma lista das posições possíveis para a próxima rainha
• state.is_resolved testaria se todas as rainhas estão no quadro e se elas são boas uma com a outra.
• state.apply e state.undo modificarão o quadro para aplicar ou desfazer um posicionamento.

Você viu um programa para andar em uma árvore binária, certo? Se parece com isso:

void walk(node* p){
  if (p == NULL) return;  // this is backtracking
  else if (WeWin(p)){
    // print We Win !!
    // do a Throw, or otherwise quit
  }
  else {
    walk(p->left);   // first try moving to the left
    walk(p->right);  // if we didn't win, try moving to the right
                     // if we still didn't win, just return (i.e. backtrack)
  }
}

Aí está o seu retorno.

Você realmente não precisa de uma árvore física. Tudo o que você precisa é de uma maneira de fazer uma jogada e depois desfazê-la, ou dizer se você ganhou ou se não pode ir mais longe.