Implementación del problema de las n-reinas en Haskell (programación funcional)

febrero 11, 2008

Continuamos con las n-reinas (la reina Sofía, la reina Isabel II, Juana la loca, Ana Bolena….).

En esta ocasión cambiamos de paradigma y nos pasamos a la programación funcional (con sus divertidos lambda-cálculos) . El código en Haskell tiene muchos adjetivos, pero bonito o legible no se encuentra entre esa lista.

Implementación

comprobar : Dos reinas se amenazan mutuamente si estan en la misma fila, en la misma columna o en la misma diagonal.

comprobar :: (Int,Int) -> (Int,Int) -> Bool
comprobar (c, l) (i, j) = (l==j) || (c+l == i+j)|| (c-l == i-j)

Esta función compurueba dadas dos reinas por sus posiciones enel tablero (fila,columna) que no se amenzan mutuamente. Ojo! no comprueba que estén en la misma fila porque el tipo tablero es un vector de enteros y las filas corresponden a la posición que ocupan las reinas en el vector, así que nunca puede ser el mismo valor.

segura: Comprueba si una reina en la posición p amenanza la posible posición n.

segura :: [Int] -> Int -> Bool
segura p n = and [not (comprobar (i, j) (m, n)) | (i, j) <- zip [1..(length p)] p]
where m = length p + 1

El cometido de esta función es comprobar que la reina n no amenza a ninguna otra reina del tablero p. La función zip en Haskell se utiliza para gererar un lista de tuplas utilizando dos listas como entradas.

Ejemplo de uso:

zip [1,2,3] [6,4,5]
salida-> [(1,6),(2,4),(3,5)]

generarTablero: genera todas las posibles posiciones que puede tomar una reina independientemente de si está amenazada o no.Esta función nos va a servir posteriormente para ir generando todos los posibles tableros de tamaño n en los cuales las reinas no están amenzadas.

generaPosiciones::Int->[Int]
generaPosiciones posiciones | posiciones > 0 = [posiciones] ++ generaPosiciones (posiciones-1)
| otherwise = []

colocaReina: Coloca una nueva reina en el tablero devuelve todos los tableros que tienen reinas bien colcadas.

colocaReina:: [Int]->[Int]->[[Int]]
colocaReina [] _ = []
colocaReina (x:xs) tablero | segura tablero x = [tablero ++ [x]] ++ (colocaReina xs tablero)
| otherwise = colocaReina xs tablero

La primera lista de entrada x:xs es originalmente un vector de n..1 generado con la función generarTablero del cual se descartan la posiciones que están amenazadas. esta función devuelve una lista con todos los tableros que no están amenzados.

nuevosTableros: Tomando como entrada una serie de tableros validos de tamaño n-1 – genera todos los tableros de tamaño n que son válidos.

nuevosTableros::[[Int]]->Int->[[Int]]
nuevosTableros [] _ = []
nuevosTableros (x:xs) n = (colocaReina (generaPosiciones n) x) ++ (nuevosTableros xs n)

generaSolucion: A partir de una lista de tableros vacia va generando todos los tableros validos desde el de tamaño 1 hasta el de tamaño n utilizando la función nuevosTableros.

generaSolucion::Int->Int->[[Int]]->[[Int]]
generaSolucion n actual tableros | actual < n = generaSolucion n (actual+1) (nuevosTableros tableros n)
| actual == n = nuevosTableros tableros n

Y por último :
nreinas n :

nreinas::Int->[[Int]]
nreinas n = generaSolucion n 1 [[]]

Espero que nadie me pida que explique su comportamiento 😉

Anuncios

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

febrero 7, 2008

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