Recursividad - Ejercicios resueltos 100

Si fuéramos menos impacientes no tendríamos problema con el backtracking.

Aquellos que son usuarios (y sólo usuarios), están tan acostumbrados a que sus amados computadores les resuelvan todo que no están ni cerca de experimentar un trabajo repetitivo de ensayo y error.

El problema de las ocho reinas es un clásico del ingenio y cual más cual menos, debe utilizar el backtracking para solucionarlo.

El algoritmo general del problema de las ocho reinas se resuelve así:

1. Se coloca una reina en alguna de las filas.
2. Se siguen intentando colocar la siguiente reina en la siguiente fila preguntando en cada posición si está amenazada por otra reina existente.
3. Si no quedan más posiciones, se vuelve a la pieza anterior y se sigue intentando por las siguientes columnas de su fila

¿Nada más?

Nada más. Eso es el algoritmo general. Cuanto más general mayores posibilidades de hacerlo recursivo.

5.- Confeccione una función recursiva que llene un tablero de ajedrez con 8 reinas sin que estas se amenacen entre sí:


La implementación en Java es la siguiente:

public void reinas(int i, int j, int dama)
{
 
 //  Mientras no haya recorrido todo el tablero...
 if ( estaDentro(i,j) )
 {
 
  //  ...y si la posición en la que voy a poner la 
  //  reina no está amenazada...                   
  if (noAmenazada(i,j))
  {
   //Ponemos la reina
   T[i][j]=dama;

   //BORDE: Si logramos colocar la última reina
   //Imprimimos el tablero con la solución
   if (dama == N) imprimir();

   //Y si no es la última recurrimos por la
   //siguiente fila
   reinas(i+1, 0, dama + 1);

   //Si lo anterior falla sacamos la reina
   T[i][j]=0;
  }
  // Si la posición está amenazada recurrimos por la
  // siguiente columna.
  reinas(i, j+1, dama);

  //Si lo anterior falló, quitamos la reina
  T[i][j]=0;
 }
}