Implementación del problema de las N-Reinas en Prolog (programación lógica)

Una implementación sencilla del problema de las n-reinas en Prolog consiste en tres simples pasos:

1. Generar un tablero de dimensión n.
2. Generar una permutación sobre ese tablero.
3. Comprobar si ese tablero cumple la condición de que todas las reinas colocadas no se amenacen entre sí.

Gracias al backtracking de Prolog podemos volver a preguntar por un resultado cuando nos muestra una solución, y así poder generar todas las posibles soluciones.

Implementación

nreinas (+N,?Sol). El primer predicado y el cual llamamos desde el intérprete de Prolog . Se satisface si Sol es la solución al problema de las N-Reinas en un tablero de tamaño N.

nreinas(N,Sol):- generarTablero(N,Tablero),
permutar(Tablero,Sol),
buenTablero(Sol).

Este predicado generar un tablero de dimensión N, generar una permutación de ese tablero y por último comprueba si esa permutación contiene reinas es posiciones que no se amenacen unas a otras.

generarTablero(+X,?Y). se verifica si Y es una lista de X elementos que contiene los naturales comprendidos entre 1 y X, ambos inclusive. Nótese que:

• Como cada reina habrá de ocupar una columna distinta, el tablero (o tableros) solución será (serán) una permutación de un tablero así generado.

generarTablero(0,[]).
generarTablero(X,[X|R]):-
XMenos1 is X - 1,
XMenos1 >= 0,
generarTablero(XMenos1,R).

Este predicado genera un tablero de la forma [N,N-1,N-2,….,1].

permutar(?LX,?LY). se verifica si LY es una permutación de los elementos de LX, la única permutación de la lista vacía es la lista vacía.

permutar([],[]).
permutar(X,[C|Z]) :- seleccionar(X,C,R), permutar(R,Z).

Para realizar la permutación de la lista de entrada, se seleccióna el primer valore de la lista y se permuta con el resto de la lista.

seleccionar(L,X,R). se verifica si X es un elemento de L y R es la lista L sin el elemento X.

seleccionar([X|R],X,R).
seleccionar([C|R],X,[C|Y]) :- seleccionar(R,X,Y).

buenTablero(+X). se verifica si en el tablero X, ninguna reina amenaza a otra. Hay que tener en cuenta que:

• Amenazar es una relación simétrica, es decir, lo mismo da amenazar que ser amenazada.
• Lo que se ha llamado Tablero es una lista de n elementos con los naturales de 1 a n donde cada elemento especifica la columna que ocupa la reina en el tablero, y la fila se especifica por el orden del elemento en la lista. (En resumidas cuentas, acorde a las especificaciones de la práctica).

buenTablero([]).
buenTablero([C|R]):- not(amenaza(C,R)),
buenTablero(R).

Se comprueba que la reina C no amena a las del resto del tablero y despues se comprueba el resto del tablero.

amenaza(X,Y). se verifica si una reina colocada en la columna X de la fila n de un tablero amenaza a cualquiera de las demás reinas colocadas en las filas 0..n-1 del resto del tablero, y cuyas columnas vienen especificadas en la lista Y. Utiliza para comprobar todo esto el predicado análogo amenaza(X,Prof,L), que se cumple cuando X y otro elemento de la lista L se encuentran en la misma columna (mismo valor) o especifican reinas situadas en diagonal.

amenaza(X,Prof,[C|_]):- X is C+Prof;
X is C-Prof;
X = C.
amenaza(X,Prof,[_|R]):- ProfMas1 is Prof + 1,
amenaza(X,ProfMas1,R).


amenaza(_,[]):- fail.
amenaza(X,Y):- amenaza(X,1,Y).

Análisis de la solución propuesta

Etiquetas: lógica, n-reinas, programación, prolog