Las ocho reinas y la fuerza bruta

El problema de las ocho reinas es muy fácil de describir, sólo hay que colocar ocho reinas del juego del ajedrez en un tablero estándar de 8x8 de tal manera que no se ataquen entre ellas. Recordemos que las reinas pueden desplazarse cualquier número de casillas en horizontal, vertical, o diagonal. Por tanto, para que que el problema esté resuelto, las reinas no pueden compartir ni filas, ni columnas, ni diagonales. A modo de ejemplo, y para asegurarnos de que todos estamos hablando de lo mismo, la siguiente figura muestra la solución al problema para un caso más simple, el de 4 reinas en un minitablero de 4x4 casillas.

Una técnica de resolución de problemas para la que los ordenadores están especialmente bien dotados es la conocida como fuerza bruta. Básicamente la idea cosiste en dado un problema, intentar de manera sistemática todas las soluciones candidatas hasta dar con la solución buscada. El método de la fuerza bruta aplicado al problema de las reinas consistiría en calcular todas las formas posibles de colocar las ocho piezas en el tablero, y para cada una de ellas comprobar si se trata de una posición legal, es decir, no hemos colocado más de una reina en la misma casilla, y que las reinas no se atacan entre sí (no hay dos reinas situadas en la misma fila, columna, o diagonal). De esta manera, la primera pieza la podríamos colocar en cualquiera de las 64 casillas; la segunda, también se podría colocar en cualquiera de las 64 casillas (y después ya comprobaremos si las hemos colocado en la misma), con lo que tendríamos 64x64 posibilidades; con la tercera pieza tendríamos 64x64x64 posibilidades; y cuando coloquemos la última, tendríamos 64x64x64x64x64x64x64x64 posibilidades, que nos da el astronómico número de 281.474.976.710.656 posiciones a examinar, algo que está fuera del alcance de la mayoría de los ordenadores de hoy en día.

Llegados a este punto, lo que tenemos que hacer es aplicar algunas técnicas heurísticas, para ver hasta dónde podemos reducir el número de soluciones candidatas a calcular. La primera mejora, y la más evidente, es evitar colocar dos piezas en la misma casilla. La primera reina la podemos poner en cualquiera de las 64 casillas, la segunda en cualquiera de las 63 restantes, y así sucesivamente, por lo que tendríamos un total de 64x63x62x61x60x59x58x57 posiciones, que nos da el número 178.462.987.637.760.

A continuación vamos a añadir la restricción de que sólo puede haber una reina en cada columna, ya que de lo contrario se atacarían. En este caso, la primera reina podría ir a cualquiera de las 8 casillas de la primera columna, la segunda reina a cualquiera de las 8 casillas de la segunda, y así sucesivamente. Para este caso lo que tenemos son 8x8x8x8x8x8x8x8 combinaciones, que hace un total de 16.777.216 posibilidades, un número bastante más asequible para un ordenador.

La siguiente mejora que podemos añadir es la de no permitir que dos reinas estén en la misma fila. En este caso, la primera reina puede ocupar cualquiera de las 8 casillas de la primera columna como estudiamos en el caso anterior, pero ahora la segunda reina sólo puede ocupar una de las 7 casillas libres, es decir, puede estar en cualquier lugar de la segunda columna excepto en la fila que ya está ocupada por la primera reina. De igual manera, a la tercera reina le quedarían 6 casillas libres para ocupar, y así sucesivamente. Es decir, tendríamos que evaluar 8x7x6x5x4x3x2x1 u 8! combinaciones, lo que nos da 40.320 posibles posiciones.

Veamos, por tanto, el algoritmo que soluciona el problema de las ocho reinas mediante la fuerza bruta, al que le añadiremos las mejoras de evitar colocar dos reinas en la misma columna y en la misma fila.

En primer lugar vamos a implementar una función que dada una posición determinada (una configuración concreta de reinas) determine si es una solución válida o no al problema. Dado que nuestro algoritmo de búsqueda se encarga de eliminar todas aquellas posiciones en las que dos o más reinas ocupan la misma casilla, la misma columna, y la misma fila, a la función de validación sólo le quedaría por comprobar que no ocupen la misma diagonal.

Para poder trabajar, nuestra función de validación necesita conocer en qué posición se encuentra cada reina, es decir, necesitamos algún mecanismo que nos permita codificar los tableros. Para ello enumeraremos por orden a las reinas, de tal manera que la reina número 1 es la que ocupa la primera columna, la reina 2 la segunda, etc. Y a continuación creamos un array con las filas que ocupan cada una de las reinas dentro del tablero. De esta manera, si la primera reina está en la fila 4, tendremos que el array en su posición 1 contendrá el valor 4, es decir, x[1]:=4. Así por ejemplo el siguiente array:

[5, 7, 8, 4, 2, 7, 3, 1]

se correspondería con el siguiente tablero:

Para que dos reinas, i y j, ocupen la misma diagonal se debe cumplir que la distancia (número de casillas) que hay entre sus respectivas columnas (valores de i y de j) sea igual a la distancia que hay entre sus respectivas filas (valores x[i] y x[j]). Y dado que la distancia entre dos números cualesquiera es el valor absoluto de la diferencia entre ambos, tenemos que para que dos reinas ocupen la misma diagonal se debe cumplir que |i-j| = |x[i]-x[j]|.

Por tanto, nuestra función para el cálculo de posiciones válidas sería:

función posición_válida(x)
    para i desde 1 hasta 7
        para j desde i+1 hasta 8
            si |i-j| = |x[i]-x[j]| entonces
                retorna falso
            fin si
        fin para
    fin para
    retorna cierto
fin función

Finalmente, lo que necesitamos es otra función que genere los distintos tableros a examinar. Dicho de otra manera, que genere todas las combinaciones posibles de reinas. Dados los números del 1 al 8, queremos calcular todas las formas posibles que existen de ordenarlos, sin que se repitan. A esto en matemáticas se le conoce con el nombre de permutaciones. Supondremos la existencia de una función llamada permutaciones() que nos devuelve un array con todas las permutaciones posibles.

Una vez tenemos disponible la función que comprueba la validez de un tablero, y una función para la generación de permutaciones, podemos implementar el algoritmo que soluciona el problema de las ocho reinas:

p := permutaciones(8)
para i desde 1 hasta longitud(p) hacer
    k := perm[i]
    si posición_valida(k) entonces
        escribir(k)
    fin si
fin para

Se trata de un algoritmo muy sencillito, que simplemente genera la totalidad de las permultaciones, y después va comprobando una a una si se trata de una solución válida.