Backtracking ( Busqueda En Profundidad )

Backtracking es una tecnica para resolver problemas de diversos tipos, por ejemplo:
generación de numeros y encontrar salidas de laberintos.

La tecnica consiste en recorrer todas las soluciones posibles ordenadamente,
asi si estuviesemos hablando de generar todos los numeros posibles de 4 digitos
tendriamos:

1 1 1 1
2 1 1 1
3 1 1 1
...
9 1 1 1
1 2 1 1


Ahora si estuviesemos hablando de encontrar la salida en un laberinto, lo que tendriamos que hacer es recorrer todas las habitaciones del laberinto pero en profundidad esto quiere decir, que una vez que se entra en una pieza, se busca una nueva salida que no sea por donde tu entraste y no te devuelves hasta que llegues a una habitacion sin salida

imaginemosnos el siguiente mapa

......
....xf
sxx...

donde:

s es el punto de partida
f el punto de llegada
x un muro
. un camino accesible
* un camino ya transitado

ademas dijimos que backtracking funciona generando soluciones ordenadas, de ahora
en adelante le llamaremos a esto generar nuevos candidatos, los nuevos candidatos son aquellas
posiciones que no han sido transitadas previamente.

Para este ejemplo usaremos el siguiente criterio:
primero se recorre para arriba si es posible
sino a la derecha
sino abajo
sino la izquierda.


con este criterio la salida encontrada seria:

******
*...x*
*xx...

Es importante destacar que backtracking no se preocupa de encontrar la mejor solucion, le
basta con la primera.

Recapitulando, se necesita
1) un mapa
2) un orden de movimiento ( para la generación de nuevos candidatos )
3) un criterio de llegada, normalmente que la posicion de un personaje este en cierta posicion

el pseudocodigo es el siguiente

listo = falso
backtrack(mapa, camino_recorrido, posicion_nueva)
si llegaste al final:
agregas la posicion a recorrido
listo = verdadero
retornas el camino_recorrido

si no:
agregas el nuevo punto a camino_recorrido
por cada posicion adyacentes
  si es un movimiento legal y no esta en camino_recorrido
    backtrack(mapa, camino_recorrido, posicion adyacente)
    si esta listo retornas el camino_recorrido

Para empezar simplemte le pasas la posicion de origen.

Sabes que llegasta al final cuando tu posicion es la posicion de destino
el camino de recorrido puede ser una lista, pero cuidado tienes que copiar la lista
y no pasarlo por referencia.