Matematica Discreta Programas En Haskell

1* Las torres de Hanói es un rompecabezas que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los

N discos en algunos de los otros dos postes.

Diseñar una estrategia recursiva para resolver el problema de las torres de Hanoi.

Solución: La estrategia recursiva es la siguiente:

Caso base (N=1): Se mueve el disco de A a C.

Caso inductivo (N=M+1): Se mueven M discos de A a C. Se mueve el disco de A a

B. Se mueven M discos de C a B

Programación en haskell:

2* El problema de las 8 reinas consiste en situar a las 8 reinas en un tablero de ajedrez de NxN sin que se amenacen entre ellas.

Para representar el problema, se podría plantear como una matriz de NxN

enteros, donde un 1 significa que la reina está en esa posición, y un 0 que la casilla está vacía.

Programación en haskell:

La lista [3,1,4,2] representa que las posiciones de las reinas son

[(4,3),(3,1),(2,4),(1,2)]; gráficamente,

import Data.List

-- La lista [3,1,4,2] representa que las posiciones de las reinas son

-- [(4,3),(3,1),(2,4),(1,2)]; gráficamente,

-- +---------+

-- | R |

-- | R |

-- | R |

-- | R |

-- +---------+

-- ---------------------------------------------------------------------

-- § 1ª solución (mediante permutaciones) --

-- ---------------------------------------------------------------------

-- (reinas1 n) es la lista de soluciones del problema de las N

-- reinas. Por ejemplo,

-- reinas1 4 == [[2,4,1,3],[3,1,4,2]]

reinas1 :: Int -> [[Int]]

reinas1 n = [rs | rs <- permutations [1..n], segura rs]

-- (segura rs) se verifica si rs es una lista de m números

-- [n_1,...,n_m] tal que las reinas colocadas en las posiciones (x,

-- n_1), ..., (x + m, n_m) no se atacan entre sí.

segura [] = True

segura (r:rs) = noAtaca r rs 1 && segura rs

-- (noAtaca r rs d) se verifica si la reina r no ataca a niguna de las

-- de la lista rs donde la primera de la lista está a una distancia

-- horizontal d.

noAtaca :: Int -> [Int] -> Int -> Bool

noAtaca _ [] _ = True

noAtaca r (a:rs) distH = abs(r-a) /= distH &&

noAtaca r rs (distH+1)

...