Lo quiero para ayer

octubre 2, 2008

Bueno, mañana tenemos demo del proyecto y venimos tocando los huevos y poniendonos nerviosos porque las cosas no están acabadas durante toda la semana.

Espero que se den cuenta, porque insinuaciones no me faltan, que me dan más ganas aún de tocarme los huevos con las dos manos a la vez cada vez que nos vienen con una tarea que les corre mucha prisa para la demo. A mí plin tío, te hubieras espabilado y me lo hubieras dado antes porque yo a las 7 como muy tarde estoy camino de casa para tomarme la cervecita de después del curro. Pero como soy bueno te dejo encendido mi equipo y curras tú en él si quieres.

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😉

Nota sobre el tipo de licencia de mis entradas

febrero 11, 2008

Para quedarlo claro y que no haya problemas, a no ser que diga lo contrario, sois libres de hacer todo lo que queraís con mis post siempre que me citeis.

Bueno si vais a hacer alguna práctica sobre algo que está aquí podéis obviar el citarme para que la nota no sea mala😉

En fin, que publico todo bajo licencia Creative Commons

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


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.