lunes, 21 de octubre de 2013

Las ocho reinas y la vuelta atrás

En una entrada anterior vimos cómo solucionar el problema de las ocho reinas utilizando la fuerza bruta. En esta ocasión vamos a ver cómo se solucionaría el mismo problema utilizando una técnica diferente: la vuelta atrás.
El método de resolución de problemas de vuelta atrás (del inglés backtracking) se basa en la idea de que no siempre es necesario terminar de construir completamente una solución candidata para determinar que ésta no es válida. Para ciertos problemas es posible que con soluciones parcialmente construidas ya sea posible determinar que estas son incorrectas. En el caso concreto del problema de las ocho reinas, si por ejemplo colocamos la primera reina en la primera columna y primera fila, y la segunda reina en la segunda columna y la segunda fila, no es necesario colocar ninguna de las otras 6 reinas restantes (en cualquiera de sus combinaciones posibles), porque ya sabemos que esta solución no es válida, porque las dos reinas ya colocadas se atacan mutuamente. Si en este momento abortamos la búsqueda en esta línea, nos ahorraríamos de examinar 6! ó 720 soluciones candidatas. Una vez que hemos encontrado que una combinación es incorrecta, y hemos determinado que vamos a abortarla, lo que hacemos es volver un paso hacia atrás, hasta la última reina que colocamos, y continuamos la búsqueda por donde la dejamos.
A continuación vamos a estudiar el algoritmo que resuelve el problema de las ocho reinas utilizando la técnica de la vuelta atrás. Primero, y al igual que en el caso del algoritmo de la fuerza bruta, necesitamos una función que dada una posición nos indique si esta es válida o no.
función posición_válida(x, k)
    para i desde 1 hasta k-1
        si x[i]=x[k] ó |i-k|=|x[i]-x[k]| entonces
            retorna falso
        fin si
    fin para
    retorna cierto
fin función
La primera diferencia que observamos con respecto a la función de validación del apartado anterior es que ésta recibe dos argumentos, a saber, el tablero (x) y el número de reinas colocadas en el mismo (k). Esto es así porque las posiciones que les pasamos a la función son posiciones parcialmente construidas, es decir, que no todas las piezas están colocadas en el tablero, y por tanto, tenemos que decirle cuantas piezas hay. Otra gran diferencia es que la función sólo cuenta con un único bucle, en lugar de los dos bucles anidados del caso anterior. Esto es así porque no es necesario comprobar si cada reina ataca a todas las demás, ya que el algoritmo va construyendo progresivamente la solución, y por tanto, cuando es invocada la función con, por ejemplo, 4 reinas, sabemos que las tres primeras no se atacan entre sí: la función ya fue invocada anteriormente para el caso k:=3, y si alguna de las tres reinas se hubiese atacado, no habríamos llegado a este punto. Por tanto, nos bastaría con comprobar que esta nueva y última reina no ataca a las demás. Finalmente, y para no complicarnos la vida con las temidas permutaciones, nuestro algoritmo de búsqueda sólo nos garantizará que las reinas no comparten columna, y por tanto, la función de validación ha de comprobar explícitamente que las reinas no comparten filas (x[i]=x[k]).
Una vez que tenemos la función posición_válida(), podemos abordar el algoritmo:
x   := [0, 0, 0, 0, 0, 0, 0, 0]
k   := 1
fin := falso
mientras (fin = falso) hacer
    mientras no posición_válida(k, x) hacer
        x[k] := x[k] + 1
        si x[k] > 8 entonces
           k := k – 1
           si k = 0 entonces
               fin := cierto
               salir
           si no
               x[k] := x[k] + 1
           fin si
    fin mientras
    si k = 8 entonces
        escribir(x)
    si no
        k := k + 1
        x[k] := 1
    fin si
fin mientras
Aunque el algoritmo parezca muy complejo, la idea subyacente al mismo es muy sencilla. Básicamente lo que tenemos que hacer para calcular todas las combinaciones posibles de reinas, con una reina por columna, es contar desde la posición [1,1,1,1,1,1,1,1] hasta la posición [8,8,8,8,8,8,8,8], de la misma forma que hacemos cuando contamos números naturales (la única diferencia es que en lugar de contar desde 0 hasta 9 como hacemos habitualmente, contamos desde 1 hasta 8).
Sin embargo, hay que tener en cuenta que con el algoritmo de vuelta atrás, la cuenta se ve interrumpida cada vez que encontramos una posición que no es válida con las reinas que llevamos hasta el momento colocadas. Por ejemplo, de la posición [1,1,1,1,1,1,1,1] nos saltaríamos a la posición [1,2,1,1,1,1,1,1] sin necesidad de pasar por todas las posiciones intermedias [1,1,X,X,X,X,X,X] ya que sabemos que son todas inválidas independientemente de los valores que adopten las X, porque las dos primeras reinas se atacan (comparten la primera fila).
Es sorprendente que algo tan sencillo como contar requiera de un algoritmo tan complejo. Pero esto es una situación muy habitual en informática.

No hay comentarios:

Publicar un comentario