Algo que cabe destacar dentro de esta estrategia es que hay que tener en cuenta la mayor cantidad de restricciones posibles al generar cada combinación para disminuir el tiempo de ejecución y evitar cálculos redundantes.

Para que se entienda mejor, veamos un primer ejemplo:

El problema de las 8 reinas

Este problema consiste en determinar si se pueden colocar 8 damas en un tablero de ajedrez de 64 casillas, de tal manera que no queden amenazadas.

Si fuéramos a resolver este problema con fuerza bruta, tendríamos que analizar todas las ubicaciones posibles de 8 reinas en el tablero hasta que nos encontremos con una combinación en la que ninguna reina esté amenazada o hayamos realizado todas las ubicaciones posibles.

Para la colocación de la primera dama hay 64 casillas disponibles. Cuando colocamos ésta, quedarían 63 casillas posibles para la segunda dama. Y así sucesiva y recursivamente hasta que llegaríamos a un total de “combinaciones” posibles de 64 * 63 * 62 * 61* 60 * 59 * 58 * 57, para un total de 200 000 millones de combinaciones.

Una computadora muy rápida trabajando día y noche demoraría más de medio año solamente para obtener todas las combinaciones, eso sin analizarlas. Por lo que evidentemente esta es una solución muy costosa y puede mejorarse como se verá a continuación.

Sabemos que si podemos ubicar 8 reinas sin que se amenacen, entonces solo puede haber una reina por columna, ya que dos reinas en una misma columna estarían amenazándose. Por tanto el algoritmo de este problema consiste en:

1 – Si n es cero, entonces ya no quedan reinas por poner y el problema tiene solución.

2 – Se intenta ubicar una reina en cada columna de izquierda a derecha.

3 – Se intenta colocar la reina en cada celda de la columna y se verifica si desde esta posición se amenaza a las reinas ubicadas en las columnas a la izquierda. Si no se amenazan las reinas anteriores, entonces trataremos de colocar las reinas restantes en las columnas de la derecha (aproximación recursiva al caso base).

4 – Si ninguna celda de la columna satisface el paso 3, no se puede ubicar una reina en la columna y se vuelve atrás para intentar ubicar en otra posición a la reina ubicada en la columna anterior. Si estamos en la primera columna, entonces el problema no tiene solución.

Este método lo único que hace es verificar si se ha recibido un tablero correcto (es cuadrado y tiene todas las celdas en false). Luego llama al método privado UbicaReinas que es el que intenta ubicar k reinas a partir del ancho del tablero.

El método Amenaza sería el encargado de verificar si se amenaza alguna otra dama, recorriendo el array de forma vertical, horizontal y diagonal, a partir de la posición
[i , j]. Además de implementar este método como ejercicio, puede mejorar un poco más el algoritmo. Fíjese que dos reinas no pueden ubicarse en la misma fila.

Buscar la salida en un laberinto

Al menos para mi este problema es el ideal para demostrar el poder del backtracking. Se trata de encontrar la salida dentro de un laberinto. La estrategia a seguir para salir de un laberinto es primeramente, explorar hacia delante un posible camino y ver si conduce a una solución. Si no conduce a una solución, hay que desandar el camino y volver atrás para intentar con otro.

Considere un laberinto representado por un array rectangular (bidimensional) de bool, en el que una celda con valor false significa que hay un obstáculo por el que no se puede atravesar. Y una celda con valor true es una celda por la que se puede pasar.

El problema consiste por ejemplo en suponer que entramos por la celda en la posición 0,0 y se quiere encontrar en camino hasta la posición m,n donde m es la cantidad de filas del array y n la cantidad de columnas. Puede resolverse de igual forma si se empieza y se termina por otras celdas.

El método C# HaySalida es el siguiente:

Como se ha visto en los ejemplos anteriores, este primer método es el que se encarga de llamar al otro método privado y recursivo de igual nombre. Veamos ahora el código y luego lo comentamos.

Empezamos desde la línea 2 donde se indica el caso base de la recursividad. O sea, si se ha llegado a la celda de salida y esta es true. Después comprobamos si estamos en una celda por la cual no se puede pasar, en caso de que no se pueda pasar retornamos false. Si se puede pasar por esa casilla, la ponemos en false para garantizar que no pasaremos de nuevo por ella en caso que el camino no conduzca a una salida.

Luego, en las próximas llamadas recursivas se intenta averiguar si hay salida desde las casillas vecinas y se retorna true en caso de encontrar la salida. Si se llega a la última línea es porque desde ninguna de las celdas vecinas hay salida, y por tanto no hay salida desde la celda actual, por lo que se retorna false.

El método HaySalida solamente nos dice si existe o no salida del laberinto, pero no nos da la respuesta de cual es la salida, o sea, el camino a seguir para llegar a la salida. Intenta hacer un método SalidaLaberinto que devuelva un array con los puntos por los que se debe pasar para llegar a la salida mas corta.

En este caso para estar seguros de encontrar el camino más corto, habría que explorar todos los caminos posibles y compararlos. Note que en el método HaySalida, primero se explora el camino que va en dirección diagonal y luego los caminos más cercanos a esta, lo cual no quiere decir que se encuentre el camino más corto. Esto es lo que se conoce como heurística, que consiste en mejorar los algoritmos basados en la experiencia, el conocimiento y el sentido común.

Solo agregar que esta técnica de backtracking o Vuelta Atrás, es muy utilizada en juegos, ya que ante una determinada situación del juego se exploran los diferentes caminos a seguir según las posibles jugadas del contrario y así sucesivamente, decidiendo las jugadas, hasta que se conduce a la victoria.

Bueno, hasta aquí este pequeño tutorial de recursividad en C#. Seguro faltaron muchas cosas por tratar en este tema, ya que no soy un experto ni mucho menos.

Para aprender recursividad lo más importante es practicar, leer y copiar código. Aquí dejo algunos ejercicios. Si quieres luego debatimos las soluciones.

1- Escriba un método recursivo string Invierte (string s) que devuelva el reverso de la cadena s.

2- Implemente un método que demuestre que con un caballo se pueden recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por una misma casilla.

3- Escriba el método static long Factorial(int n) que devuelva el factorial del número n.

0! = 1, y para n ≥ 1, n! = n * (n – 1)!

4- Escriba el método static bool EsPalíndromo(string s) que diga si el string s es palíndromo. Un string es palíndromo si se lee de la misma forma de izquierda a derecha que de derecha a izquierda.

5- Implemente el método static void DescomposicionSumandos(int n) que muestre en la pantalla todas las formas posibles de descomponer el número n en sumandos. Por ejemplo, para n=5, en la pantalla se muestra:

1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
1 4
2 3
5

6- El Taxista: Un taxista se desplaza en su taxi por una ciudad en la cual sólo está permitido conducir hacia el ESTE y hacia el SUR.
Implemente el método static int CantidadCaminos(int xOrig, int yOrig, int xDest, int yDest) que devuelva la cantidad de caminos diferentes por los que se puede llegar desde el punto (xOrig, yOrig) hasta el punto (xDest, yDest). Asuma que xDest ≥ xOrig y que yDest ≥ yOrig.