Comprensión de Backtracking en C ++

Tengo una buena comprensión básica de los fundamentos de C ++, también entiendo cómo funciona la recursividad. Encontré ciertos problemas como el clásico problema de las ocho reinas y resolver un Sudoku con Backtracking.

Me doy cuenta de que estoy bastante perdido cuando se trata de esto, parece que no puedo entender el concepto de volver a la pila de recursión y comenzar de nuevo para resolver el problema. Parece fácil con un lápiz y papel, pero cuando se trata de escribir código para esto, estoy confundido sobre cómo comenzar a atacar estos problemas.

Sería útil si hubiera un tutorial dirigido a los principiantes para dar marcha atrás o si hubiera un buen libro donde se cubriera esto. Si alguien puede arrojar luz sobre este tema o darme algunos enlaces a referencias decentes, estaría realmente agradecido.

Y sí, sé que sería más fácil en lenguajes funcionales, pero también me gustaría entender la implementación en lenguajes imperativos.

... Parece que no puedo entender el concepto de volver a la pila de recursión y comenzar de nuevo para resolver el problema.

Al retroceder, no está comenzando de nuevo. En cambio, recorre todas las opciones en la situación actual.

Piensa en encontrar una solución para un laberinto. En un punto donde tienes dos caminos diferentes, primero prueba el izquierdo. Si el izquierdo no te lleva a la salida, regresas al punto e intentas el otro camino. Así es como funciona el retroceso. En 8 Q y otros problemas en los que se puede utilizar el retroceso, la parte confusa está en el dominio del problema: cómo iterar a través de sus opciones en una situación dada de una manera determinista.

EDITAR : el siguiente es un pseudocódigo que ayuda a comprender el retroceso.

# 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 la pregunta 8Q:

• state.get_all_options devolvería una lista de las posibles posiciones para la próxima reina
• state.is_resolved probaría si todas las reinas están en el tablero y si son buenas entre sí.
• state.apply y state.undo modificarán el tablero para aplicar o deshacer un posicionamiento.

Has visto un programa para caminar por un árbol binario, ¿verdad? Se parece a esto:

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)
  }
}

Ahí está tu retroceso.

En realidad no necesitas un árbol físico. Todo lo que necesitas es una forma de hacer un movimiento y luego deshacerlo, o saber si has ganado, o saber si no puedes seguir adelante.