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

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

Etiquetas: , , ,

4 comentarios to “Implementación del problema de las n-reinas en Haskell (programación funcional)”

  1. Miguel Says:

    Hola! me pareció muy interesante. Me podrías enviar el código fuente?
    Desde ya muchas gracias!!!

    PD: Disculpá que puse equivocadamente este comentario en otro artículo que no correspondía!!

  2. sandy Says:

    hola podrias enviarme tu codigo porfa, gracias

  3. erick Says:

    hola oie es interesante me podrias ayudar enviandome tu codigo fuente oie y no tendras un ejemplo de el problema del granjero gracias espero y me lo puedas enviar la verdad es muy urgente

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s


A %d blogueros les gusta esto: