El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)

El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

Una solución del problema de las n reinas es una lista de posiciones.

Usando el procedimiento de búsqueda en profundidad, definir las funciones

tales que

  • solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en profundidad. Por ejemplo,

  • primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,

  • nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Búsqueda en espacios de estados por profundidad

Las características de los problemas de espacios de estados son:

  • un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
  • un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
  • un nodo inicial y
  • un nodo objetivo que es la solución.

Definir la función

tal que buscaProfundidad s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en profundidad.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Caminos en un grafo

Definir las funciones

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

Soluciones

Sucesiones de listas de números

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

tales que

  • (soluciones xs) es la lista de pares (n,ys) tales que ys es una lista final obtenida aplicándole n transformaciones a xs. Por ejemplo,

  • (finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,

  • (finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,

Soluciones

[schedule expon=’2019-06-07′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 07 de junio.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

Siempre que nos vemos
es cita para mañana.
Nunca nos encontraremos.

Antonio Machado

[/schedule]

[schedule on=’2019-06-07′ at=»06:00″]

[/schedule]

Descomposiciones de N como sumas de 1, 3 ó 4.

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

Definir las funciones

tales que

  • (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

  • (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

Nota: Se puede usar programación dinámica.

Soluciones