Capitulo 4 (Ejercicios 4.3)

Ejercicio
El problema de las ocho reinas.
Se trata de colocar 8 reinas en un tablero de ajedrez vacío de tal manera que ninguna
reina pueda atacar directamente a otra reina. La solución será programada como un
predicado unario solucion(Pos) que será verdadero si y solamente si Pos representa una
posición de las ocho reinas sin que se ataque una a ninguna otra.
Primero tenemos que elegir una representación para las posiciones del tablero. Una
manera lógica sería representar las posiciones de las ocho reinas como una lista de ocho
ítems, cada ítem correspondiendo a la posición de cada reina. La posición de una reina
será especificada por un par de coordenadas (X,Y) sobre el tablero, donde cada
coordenada es un entero entre 1 y 8. En notación de Prolog lo podriamos manejar así:
X/Y donde el símbolo “/” en este caso no indica realizar una división, sino solamente es
un separador de ambos símbolos X y Y.

Colocar n-reinas en un tablero rectangular de dimensiones NxN, de forma que no se encuentren más de una en la misma línea horizontal, vertical o diagonal.

Solución:

La implementación del problema de las n-reinas en WSI-Prolog consiste en tres pasos:

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

Código fuente:

1.- La siguiente línea añade reglas de nivel superior, es muy importante para poner en ejecución sin el cual SWI-Prolog nos dará error.
[user].
2.- nreinas (+N,?Sol). Es el predicado principal que nos permite conocer el resultado de la operación.
nreinas(N,Sol) :- generarTablero(N,Tablero), permutar(Tablero,Sol), buenTablero(Sol).
3.- generarTablero(+X,?Y). Este predicado genera un tablero de dimensión variable (N).
generarTablero(0,[]).
generarTablero(X,[X|R]) :- XMenos1 is X - 1, XMenos1 >= 0, generarTablero(XMenos1,R).
4.- permutar(?LX,?LY). 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).
5.- seleccionar(L,X,R). 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).
6.- buenTablero(+X). Verifica si en el tablero X, ninguna reina amenaza a otra; considerando que amenazar también se entiende ser amenazado.
buenTablero([]).
buenTablero([C|R]) :- not(amenaza(C,R)), buenTablero(R).
7.- amenaza(X,Y). 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.
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).

Ejecución en SWI-Prolog:

La imagen está delimitada en tres secciones cuya descripción es:

a) Código.- Sección de código ingresado.
b) Ctrl+D.- Combinación de teclas para poder compilar el algoritmo..
c) Pruebas.- Resultado de la ejecución del algoritmo compilado nreinas (n,S), donde n es igual a la dimensión.

Gráficos de los resultados obtenidos

Representación gráfica del tablero de 4 dimensiones nreinas (4,S), donde S=(3,1,4,2) en el que se aprecia la ausencia de amenaza y amenazado.

Representación gráfica del tablero de 8 dimensiones nreinas (8,S), donde S=(8,4,1,3,6,2,7,5) en el que se aprecia la ausencia de amenaza y amenazado.