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 ->

...