Backtracking es una serie de ideas para resolver problemas de búsqueda completa con recursión. El pricipal motivo de backtracking es minimizar el tener que revisar todos los estados para armar una solución. Además, usar recursión tiene dos grandes sabores:
Recursión te permite resolver un problema grande de forma local.
Abandonar una solución mala cuando haces recursión es solo hacer "return".
Backtracking es recursión, pero no solamente intenta ser recursión. Backtrack es retractarse en español, por eso mismo los problemas que se pueden hacer con backtracking deben tener una solución que se puede armar parcialmente, entonces, en backtrack por lo general vas a armar una solución, luego retractarte, luego armar otra, luego retractarte y así. Armar un rompecabezas es hacer backtracking.
La experiencia me dice que por lo general es sencillo, pero también puede ser difícil, esto es el menor de los casos.
void backtrack(parametros independientes, parametros dependientes) {
if (estado final) {
procesar estado final
return;
}
//hay que apreciar que si no hay estado siguiente, no va a ninguno.
for (estado siguiente desde actual estado) {
backtrack(estado siguiente);
}
}Otra forma de hacer el for interno sería la siguiente:
while (hay estado siguiente) {
modificar estado actual
bactrack(estado actual modificado);
quitar los cambios al estado actual
}