{"id":7954,"date":"2023-07-01T17:27:02","date_gmt":"2023-07-01T15:27:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7954"},"modified":"2023-07-01T17:27:02","modified_gmt":"2023-07-01T15:27:02","slug":"01-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/01-jul-23\/","title":{"rendered":"La semana en Exercitium (1 de julio de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Algoritmo divide y vencer\u00e1s<\/a><\/li>\n<li><a href=\"#ej2\">2. Rompecabeza del triomin\u00f3 mediante divide y vencer\u00e1s<\/a><\/li>\n<li><a href=\"#ej3\">3. B\u00fasqueda en espacios de estados por profundidad<\/a><\/li>\n<li><a href=\"#ej4\">4. El problema de las n reinas (mediante b\u00fasqueda por profundidad en espacios de estados)<\/a><\/li>\n<li><a href=\"#ej5\">5. B\u00fasqueda en espacios de estados por anchura<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Algoritmo divide y vencer\u00e1s<\/h3>\n<p>La t\u00e9cnica <a href=\"https:\/\/bit.ly\/46afaca\">divide y vencer\u00e1s<\/a> consta de los siguientes pasos:<\/p>\n<ul>\n<li>Dividir el problema en subproblemas menores.<\/li>\n<li>Resolver por separado cada uno de los subproblemas:\n<ul>\n<li>si los subproblemas son complejos, usar la misma t\u00e9cnica recursivamente;<\/li>\n<li>si son simples, resolverlos directamente.<\/li>\n<\/ul>\n<\/li>\n<li>Combinar todas las soluciones de los subproblemas en una soluci\u00f3n simple.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   divideVenceras :: (p -> Bool)\n                  -> (p -> s)\n                  -> (p -> [p])\n                  -> (p -> [s] -> s)\n                  -> p\n                  -> s\n<\/pre>\n<p>tal que <code>divideVenceras ind resuelve divide combina pbInicial<\/code> resuelve el problema <code>pbInicial<\/code> mediante la t\u00e9cnica de divide y vencer\u00e1s, donde<\/p>\n<ul>\n<li><code>ind pb<\/code> se verifica si el problema <code>pb<\/code> es indivisible<\/li>\n<li><code>resuelve pb<\/code> es la soluci\u00f3n del problema indivisible <code>pb<\/code><\/li>\n<li><code>divide pb<\/code> es la lista de subproblemas de <code>pb<\/code><\/li>\n<li><code>combina pb ss<\/code> es la combinaci\u00f3n de las soluciones <code>ss<\/code> de los subproblemas del problema <code>pb<\/code>.<\/li>\n<li><code>pbInicial<\/code> es el problema inicial<\/li>\n<\/ul>\n<p>Usando la funci\u00f3n DivideVenceras, definir las funciones<\/p>\n<pre lang=\"text\">\n   ordenaPorMezcla :: Ord a => [a] -> [a]\n   ordenaRapida    :: Ord a => [a] -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>ordenaPorMezcla xs<\/code> es la lista obtenida ordenando <code>xs<\/code> por el procedimiento de ordenaci\u00f3n por mezcla. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ordenaPorMezcla [3,1,4,1,5,9,2,8]\n     [1,1,2,3,4,5,8,9]\n<\/pre>\n<ul>\n<li><code>ordenaRapida xs<\/code> es la lista obtenida ordenando <code>xs<\/code> por el procedimiento de ordenaci\u00f3n r\u00e1pida. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ordenaRapida [3,1,4,1,5,9,2,8]\n     [1,1,2,3,4,5,8,9]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule DivideVenceras (divideVenceras) where\n\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ndivideVenceras :: (p -> Bool)\n               -> (p -> s)\n               -> (p -> [p])\n               -> (p -> [s] -> s)\n               -> p\n               -> s\ndivideVenceras ind resuelve divide combina = dv'\n  where\n    dv' pb\n      | ind pb    = resuelve pb\n      | otherwise = combina pb [dv' sp | sp <- divide pb]\n\nordenaPorMezcla :: Ord a => [a] -> [a]\nordenaPorMezcla =\n    divideVenceras ind id divide combina\n    where\n      ind xs            = length xs <= 1\n      divide xs         = [take n xs, drop n xs]\n                          where n = length xs `div` 2\n      combina _ [l1,l2] = mezcla l1 l2\n\n-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,\n--    mezcla [1,3] [2,4,6]  ==  [1,2,3,4,6]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla [] b = b\nmezcla a [] = a\nmezcla a@(x:xs) b@(y:ys) | x <= y    = x : mezcla xs b\n                         | otherwise = y : mezcla a ys\n\nordenaRapida :: Ord a => [a] -> [a]\nordenaRapida =\n    divideVenceras ind id divide combina\n    where\n      ind xs                = length xs <= 1\n      divide (x:xs)         = [[ y | y <- xs, y <= x],\n                               [ y | y <- xs, y > x]]\n      combina (x:_) [l1,l2] = l1 ++ [x] ++ l2\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]\n  it \"e2\" $\n    ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0004 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Callable, TypeVar\n\nP = TypeVar('P')\nS = TypeVar('S')\n\ndef divideVenceras(ind: Callable[[P], bool],\n                   resuelve: Callable[[P], S],\n                   divide: Callable[[P], list[P]],\n                   combina: Callable[[P, list[S]], S],\n                   p: P) -> S:\n    def dv(pb: P) -> S:\n        if ind(pb):\n            return resuelve(pb)\n        return combina(pb, [dv(sp) for sp in divide(pb)])\n    return dv(p)\n\ndef ordenaPorMezcla(xs: list[int]) -> list[int]:\n    def ind(xs: list[int]) -> bool:\n        return len(xs) <= 1\n\n    def divide(xs: list[int]) -> list[list[int]]:\n        n = len(xs) \/\/ 2\n        return [xs[:n], xs[n:]]\n\n    def combina(_: list[int], xs: list[list[int]]) -> list[int]:\n        return mezcla(xs[0], xs[1])\n\n    return divideVenceras(ind, lambda x: x, divide, combina, xs)\n\n# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,\n#    mezcla([1,3], [2,4,6]) == [1,2,3,4,6]\ndef mezcla(a: list[int], b: list[int]) -> list[int]:\n    if not a:\n        return b\n    if not b:\n        return a\n    if a[0] <= b[0]:\n        return [a[0]] + mezcla(a[1:], b)\n    return [b[0]] + mezcla(a, b[1:])\n\ndef ordenaRapida(xs: list[int]) -> list[int]:\n    def ind(xs: list[int]) -> bool:\n        return len(xs) <= 1\n\n    def divide(xs: list[int]) -> list[list[int]]:\n        x, *xs = xs\n        return [[y for y in xs if y <= x],\n                [y for y in xs if y > x]]\n\n    def combina(xs: list[int], ys: list[list[int]]) -> list[int]:\n        x = xs[0]\n        return ys[0] + [x] + ys[1]\n\n    return divideVenceras(ind, lambda x: x, divide, combina, xs)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_divideVenceras() -> None:\n    assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]\n    assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_divideVenceras()\n#    Verificado\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Rompecabeza del triomin\u00f3 mediante divide y vencer\u00e1s<\/h3>\n<p>Un poliomin\u00f3 es una figura geom\u00e9trica plana formada conectando dos o m\u00e1s cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus v\u00e9rtices, ni juntando solo parte de un lado de un cuadrado con parte de un lado de otro. Si unimos dos cuadrados se obtiene un domin\u00f3, si se juntan tres cuadrados se construye un triomin\u00f3.<\/p>\n<p>S\u00f3lo existen dos triomin\u00f3s, el I-triomino (por tener forma de I) y el L-triomin\u00f3 (por su forma de L) como se observa en las siguientes figuras<\/p>\n<pre lang=\"text\">\n   X\n   X     X\n   X     XX\n<\/pre>\n<p>El rompecabeza del triomin\u00f3 consiste en cubrir un tablero cuadrado con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla, con L-triomin\u00f3s de formas que cubran todas las casillas excepto la eliminada y los triomin\u00f3s no se solapen.<\/p>\n<p>La casilla eliminada se representar\u00e1 con -1 y los L-triomin\u00f3s  sucesiones de tres n\u00fameros consecutivos en forma de L. Con esta representaci\u00f3n una soluci\u00f3n del rompecabeza del triomin\u00f3 con 4 filas y la fila eliminada en la posici\u00f3n (4,4) es<\/p>\n<pre lang=\"text\">\n   (  3  3  2  2 )\n   (  3  1  1  2 )\n   (  4  1  5  5 )\n   (  4  4  5 -1 )\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   triomino :: Int -> Posicion -> Tablero\n<\/pre>\n<p>tal que (triomino n p) es la soluci\u00f3n, mediante divide y vencer\u00e1s,  del rompecabeza del triomin\u00f3 en un cuadrado nxn en el que se ha eliminado la casilla de la posici\u00f3n p. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> triomino 4 (4,4)\n   (  3  3  2  2 )\n   (  3  1  1  2 )\n   (  4  1  5  5 )\n   (  4  4  5 -1 )\n\n   \u03bb> triomino 4 (2,3)\n   (  3  3  2  2 )\n   (  3  1 -1  2 )\n   (  4  1  1  5 )\n   (  4  4  5  5 )\n\n   \u03bb> triomino 16 (5,6)\n   (  7  7  6  6  6  6  5  5  6  6  5  5  5  5  4  4 )\n   (  7  5  5  6  6  4  4  5  6  4  4  5  5  3  3  4 )\n   (  8  5  9  9  7  7  4  8  7  4  8  8  6  6  3  7 )\n   (  8  8  9  3  3  7  8  8  7  7  8  2  2  6  7  7 )\n   (  8  8  7  3  9 -1  8  8  7  7  6  6  2  8  7  7 )\n   (  8  6  7  7  9  9  7  8  7  5  5  6  8  8  6  7 )\n   (  9  6  6 10 10  7  7 11  8  8  5  9  9  6  6 10 )\n   (  9  9 10 10 10 10 11 11  1  8  9  9  9  9 10 10 )\n   (  8  8  7  7  7  7  6  1  1  9  8  8  8  8  7  7 )\n   (  8  6  6  7  7  5  6  6  9  9  7  8  8  6  6  7 )\n   (  9  6 10 10  8  5  5  9 10  7  7 11  9  9  6 10 )\n   (  9  9 10  4  8  8  9  9 10 10 11 11  5  9 10 10 )\n   (  9  9  8  4  4 10  9  9 10 10  9  5  5 11 10 10 )\n   (  9  7  8  8 10 10  8  9 10  8  9  9 11 11  9 10 )\n   ( 10  7  7 11 11  8  8 12 11  8  8 12 12  9  9 13 )\n   ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Rompecabeza_del_triomino_mediante_divide_y_venceras where\n\nimport DivideVenceras (divideVenceras)\nimport Data.Matrix\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Los tableros son matrices de n\u00fameros enteros donde -1 representa el\n-- hueco, 0 las posiciones sin rellenar y los n\u00fameros mayores que 0\n-- representan los triomin\u00f3s.\ntype Tablero = Matrix Int\n\n-- Los problemas se representar\u00e1n mediante pares formados por un n\u00famero\n-- natural mayor que 0 (que indica el n\u00famero con el que se formar\u00e1 el\n-- siguiente triomin\u00f3 que se coloque) y un tablero.\ntype Problema = (Int,Tablero)\n\n-- Las posiciones son pares de n\u00fameros enteros\ntype Posicion = (Int,Int)\n\ntriomino :: Int -> Posicion -> Tablero\ntriomino n p =\n  divideVenceras ind resuelve divide combina (pbInicial n p)\n\n-- (tablero n p) es el tablero inicial del problema del triomin\u00f3\n-- en un cuadrado nxn en el que se ha eliminado la casilla de la\n-- posici\u00f3n (i,j). Por ejemplo,\n--    \u03bb> tablero 4 (3,4)\n--    (  0  0  0  0 )\n--    (  0  0  0  0 )\n--    (  0  0  0 -1 )\n--    (  0  0  0  0 )\ntablero :: Int -> Posicion -> Tablero\ntablero n (i,j) =\n  setElem (-1) (i,j) (zero n n)\n\n-- (pbInicial n p) es el problema inicial del rompecabeza del triomin\u00f3\n-- en un cuadrado nxn en el que se ha eliminado la casilla de la\n-- posici\u00f3n p. Por ejemplo,\n--    \u03bb> pbInicial 4 (4,4)\n--    (1,(  0  0  0  0 )\n--       (  0  0  0  0 )\n--       (  0  0  0  0 )\n--       (  0  0  0 -1 ))\npbInicial :: Int -> Posicion -> Problema\npbInicial n p = (1,tablero n p)\n\n-- (ind pb) se verifica si el problema pb es indivisible. Por ejemplo,\n--    ind (pbInicial 2 (1,2))  ==  True\n--    ind (pbInicial 4 (1,2))  ==  False\nind :: Problema -> Bool\nind (_,p) = ncols p == 2\n\n-- (posicionHueco t) es la posici\u00f3n del hueco en el tablero t. Por\n-- ejemplo,\n--    posicionHueco (tablero 8 (5,2))  ==  (5,2)\nposicionHueco :: Tablero -> Posicion\nposicionHueco p =\n  head [(i,j) | i <- [1..nrows p],\n                j <- [1..ncols p],\n                p!(i,j) \/= 0]\n\n-- (cuadranteHueco p) es el cuadrante donde se encuentra el hueco del\n-- tablero t (donde la numeraci\u00f3n de los cuadrantes es 1 el superior\n-- izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el\n-- inferior derecho). Por ejemplo,\n--    cuadranteHueco (tablero 8 (4,4))  ==  1\n--    cuadranteHueco (tablero 8 (5,2))  ==  2\n--    cuadranteHueco (tablero 8 (3,6))  ==  3\n--    cuadranteHueco (tablero 8 (6,6))  ==  4\ncuadranteHueco :: Tablero -> Int\ncuadranteHueco t\n  | i <= x &#038;&#038; j <= x = 1\n  | i >  x && j <= x = 2\n  | i <= x &#038;&#038; j >  x = 3\n  | otherwise        = 4\n  where (i,j) = posicionHueco t\n        x     = nrows t `div` 2\n\n-- (centralHueco t) es la casilla central del cuadrante del tablero t\n-- donde se encuentra el hueco. Por ejemplo,\n--    centralHueco (tablero 8 (5,2))  ==  (5,4)\n--    centralHueco (tablero 8 (4,4))  ==  (4,4)\n--    centralHueco (tablero 8 (3,6))  ==  (4,5)\n--    centralHueco (tablero 8 (6,6))  ==  (5,5)\ncentralHueco :: Tablero -> Posicion\ncentralHueco t =\n  case cuadranteHueco t of\n    1 -> (x,x)\n    2 -> (x+1,x)\n    3 -> (x,x+1)\n    _ -> (x+1,x+1)\n  where x = nrows t `div` 2\n\n-- (centralesSinHueco t) son las posiciones centrales del tablero t de\n-- los cuadrantes sin hueco. Por ejemplo,\n--    centralesSinHueco (tablero 8 (5,2))  ==  [(4,4),(4,5),(5,5)]\ncentralesSinHueco :: Tablero -> [Posicion]\ncentralesSinHueco t =\n  delete (i,j) [(x,x),(x+1,x),(x,x+1),(x+1,x+1)]\n  where x     = nrows t `div` 2\n        (i,j) = centralHueco t\n\n-- (actualiza t ps) es la matriz obtenida cambiando en t los valores del\n-- las posiciones indicadas en ps por sus correspondientes valores. Por\n-- ejemplo,\n--    \u03bb> actualiza (identity 3) [((1,2),4),((3,1),5)]\n--    ( 1 4 0 )\n--    ( 0 1 0 )\n--    ( 5 0 1 )\nactualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a\nactualiza p []             = p\nactualiza p (((i,j),x):zs) = setElem x (i,j) (actualiza p zs)\n\n-- (triominoCentral (n,t) es el tablero obtenido colocando el triomin\u00f3\n-- formado por el n\u00famero n en las posiciones centrales de los 3\n-- cuadrantes que no contienen el hueco. Por ejemplo,\n--    \u03bb> triominoCentral (7,tablero 4 (4,4))\n--    (  0  0  0  0 )\n--    (  0  7  7  0 )\n--    (  0  7  0  0 )\n--    (  0  0  0 -1 )\ntriominoCentral :: Problema -> Tablero\ntriominoCentral (n,t) =\n  actualiza t [((i,j),n) | (i,j) <- centralesSinHueco t]\n\n-- (resuelve p) es la soluci\u00f3n del problema indivisible p. Por ejemplo,\n--    \u03bb> tablero 2 (2,2)\n--    (  0  0 )\n--    (  0 -1 )\n--\n--    \u03bb> resuelve (5,tablero 2 (2,2))\n--    (  5  5 )\n--    (  5 -1 )\nresuelve :: Problema -> Tablero\nresuelve = triominoCentral\n\n-- (divide (n,t)) es la lista de de los problemas obtenidos colocando el\n-- triomin\u00f3 n en las casillas centrales de t que no contienen el hueco y\n-- dividir el tablero en sus cuatros cuadrantes y aumentar en uno el\n-- n\u00famero del correspondiente triomin\u00f3. Por ejemplo,\n--    \u03bb> divide (3,tablero 4 (4,4))\n--    [(4,(  0  0 )\n--        (  3  0 )),\n--     (5,(  0  0 )\n--        (  0  3 )),\n--     (6,(  0  3 )\n--        (  0  0 )),\n--     (7,(  0  0 )\n--        (  0 -1 ))]\ndivide :: Problema -> [Problema]\ndivide (n,t) =\n  [(n+1, submatrix 1     x (x+1) m q),\n   (n+2, submatrix 1     x 1     x q),\n   (n+3, submatrix (x+1) m 1     x q),\n   (n+4, submatrix (x+1) m (x+1) m q)]\n  where q = triominoCentral (n,t)\n        m = nrows t\n        x = m `div` 2\n\n-- (combina p ts) es la combinaci\u00f3n de las soluciones ts de los\n-- subproblemas del problema p. Por ejemplo,\n--    \u03bb> let inicial = (1,tablero 4 (4,4)) :: (Int,Matrix Int)\n--    \u03bb> let [p1,p2,p3,p4] = divide inicial\n--    \u03bb> let [s1,s2,s3,s4] = map resuelve [p1,p2,p3,p4]\n--    \u03bb> combina inicial [s1,s2,s3,s4]\n--    (  3  3  2  2 )\n--    (  3  1  1  2 )\n--    (  4  1  5  5 )\n--    (  4  4  5 -1 )\ncombina :: Problema -> [Tablero] -> Tablero\ncombina _ [s1,s2,s3,s4] = joinBlocks (s2,s1,s3,s4)\ncombina _ _             = error \"Imposible\"\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    toLists (triomino 4 (4,4)) `shouldBe`\n    [[3,3,2,2],\n     [3,1,1,2],\n     [4,1,5,5],\n     [4,4,5,-1]]\n  it \"e2\" $\n    toLists (triomino 4 (2,3)) `shouldBe`\n    [[3,3,2,2],\n     [3,1,-1,2],\n     [4,1,1,5],\n     [4,4,5,5]]\n  it \"e3\" $\n    toLists (triomino 16 (5,6)) `shouldBe`\n    [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],\n     [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],\n     [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7],\n     [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],\n     [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],\n     [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],\n     [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],\n     [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],\n     [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],\n     [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],\n     [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],\n     [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],\n     [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],\n     [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],\n     [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],\n     [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0018 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nimport numpy as np\nimport numpy.typing as npt\n\nfrom src.DivideVenceras import divideVenceras\n\n# Los tableros son matrices de n\u00fameros enteros donde -1 representa el\n# hueco, 0 las posiciones sin rellenar y los n\u00fameros mayores que 0\n# representan los triomin\u00f3s.\nTablero = npt.NDArray[np.complex64]\n\n# Los problemas se representar\u00e1n mediante pares formados por un n\u00famero\n# natural mayor que 0 (que indica el n\u00famero con el que se formar\u00e1 el\n# siguiente triomin\u00f3 que se coloque) y un tablero.\nProblema = tuple[int, Tablero]\n\n# Las posiciones son pares de n\u00fameros enteros\nPosicion = tuple[int, int]\n\n# tablero(n p) es el tablero inicial del problema del triomin\u00f3\n# en un cuadrado nxn en el que se ha eliminado la casilla de la\n# posici\u00f3n p. Por ejemplo,\n#    >>> tablero(4, (3,4))\n#    array([[ 0,  0,  0,  0],\n#           [ 0,  0,  0,  0],\n#           [ 0,  0,  0, -1],\n#           [ 0,  0,  0,  0]])\ndef tablero(n: int, p: Posicion) -> Tablero:\n    (i, j) = p\n    q = np.zeros((n, n), dtype=int)\n    q[i - 1, j - 1] = -1\n    return q\n\n# pbInicial(n, p) es el problema inicial del rompecabeza del triomin\u00f3\n# en un cuadrado nxn en el que se ha eliminado la casilla de la\n# posici\u00f3n p. Por ejemplo,\n#    >>> pbInicial(4, (4,4))\n#    (1, array([[ 0,  0,  0,  0],\n#           [ 0,  0,  0,  0],\n#           [ 0,  0,  0,  0],\n#           [ 0,  0,  0, -1]]))\ndef pbInicial(n: int, p: Posicion) -> Problema:\n    return 1, tablero(n, p)\n\n# ind(pb) se verifica si el problema pb es indivisible. Por ejemplo,\n#    ind(pbInicial(2, (1,2)))  ==  True\n#    ind(pbInicial(4, (1,2)))  ==  False\ndef ind(pb: Problema) -> bool:\n    _, p = pb\n    return p.shape[1] == 2\n\n# posicionHueco(t) es la posici\u00f3n del hueco en el tablero t. Por\n# ejemplo,\n#    posicionHueco(tablero(8, (5,2)))  ==  (5,2)\ndef posicionHueco(t: Tablero) -> Posicion:\n    indices = np.argwhere(t != 0)\n    (i, j) =  tuple(indices[0])\n    return (i + 1, j + 1)\n\n# cuadranteHueco(p) es el cuadrante donde se encuentra el hueco del\n# tablero t (donde la numeraci\u00f3n de los cuadrantes es 1 el superior\n# izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el\n# inferior derecho). Por ejemplo,\n#    cuadranteHueco(tablero(8, (4,4)))  ==  1\n#    cuadranteHueco(tablero(8, (5,2)))  ==  2\n#    cuadranteHueco(tablero(8, (3,6)))  ==  3\n#    cuadranteHueco(tablero(8, (6,6)))  ==  4\ndef cuadranteHueco(t: Tablero) -> int:\n    i, j = posicionHueco(t)\n    x = t.shape[0] \/\/ 2\n    if j <= x:\n        if i <= x:\n            return 1\n        return 2\n    if i <= x:\n        return 3\n    return 4\n\n# centralHueco(t) es la casilla central del cuadrante del tablero t\n# donde se encuentra el hueco. Por ejemplo,\n#    centralHueco(tablero(8, (5,2)))  ==  (5,4)\n#    centralHueco(tablero(8, (4,4)))  ==  (4,4)\n#    centralHueco(tablero(8, (3,6)))  ==  (4,5)\n#    centralHueco(tablero(8, (6,6)))  ==  (5,5)\ndef centralHueco(t: Tablero) -> Posicion:\n    x = t.shape[0] \/\/ 2\n    cuadrante = cuadranteHueco(t)\n    if cuadrante == 1:\n        return (x, x)\n    if cuadrante == 2:\n        return (x+1, x)\n    if cuadrante == 3:\n        return (x, x+1)\n    return (x+1, x+1)\n\n# centralesSinHueco(t) son las posiciones centrales del tablero t de\n# los cuadrantes sin hueco. Por ejemplo,\n#    centralesSinHueco(tablero(8, (5,2)))  ==  [(4,4),(4,5),(5,5)]\ndef centralesSinHueco(t: Tablero) -> list[Posicion]:\n    x = t.shape[0] \/\/ 2\n    i, j = centralHueco(t)\n    ps = [(x, x), (x+1, x), (x, x+1), (x+1, x+1)]\n    return [p for p in ps if p != (i, j)]\n\n# actualiza(t, ps) es la matriz obtenida cambiando en t los valores del\n# las posiciones indicadas en ps por sus correspondientes valores. Por\n# ejemplo,\n#    >>> actualiza(np.identity(3, dtype=int), [((1,2),4),((3,1),5)])\n#    array([[1, 4, 0],\n#           [0, 1, 0],\n#           [5, 0, 1]])\ndef actualiza(p: Tablero, ps: list[tuple[Posicion, int]]) -> Tablero:\n    for (i, j), x in ps:\n        p[i - 1, j - 1] = x\n    return p\n\n# triominoCentral(n,t) es el tablero obtenido colocando el triomin\u00f3\n# formado por el n\u00famero n en las posiciones centrales de los 3\n# cuadrantes que no contienen el hueco. Por ejemplo,\n#    >>> triominoCentral((7, tablero(4, (4,4))))\n#    array([[ 0,  0,  0,  0],\n#           [ 0,  7,  7,  0],\n#           [ 0,  7,  0,  0],\n#           [ 0,  0,  0, -1]])\ndef triominoCentral(p: Problema) -> Tablero:\n    n, t = p\n    return actualiza(t, [((i,j),n) for (i,j) in centralesSinHueco(t)])\n\n# resuelve(p) es la soluci\u00f3n del problema indivisible p. Por ejemplo,\n#    >>> tablero(2, (2,2))\n#    array([[ 0,  0],\n#           [ 0, -1]])\n#    >>> resuelve((5,tablero(2, (2,2))))\n#    array([[ 5,  5],\n#           [ 5, -1]])\ndef resuelve(p: Problema) -> Tablero:\n    return triominoCentral(p)\n\n# divide(n,t) es la lista de de los problemas obtenidos colocando el\n# triomin\u00f3 n en las casillas centrales de t que no contienen el hueco y\n# dividir el tablero en sus cuatros cuadrantes y aumentar en uno el\n# n\u00famero del correspondiente triomin\u00f3. Por ejemplo,\n#    >>> divide((3,tablero(4, (4,4))))\n#    [(4, array([[0, 0],\n#                [3, 0]])),\n#     (5, array([[0, 0],\n#                [0, 3]])),\n#     (6, array([[0, 3],\n#                [0, 0]])),\n#     (7, array([[ 0,  0],\n#                [ 0, -1]]))]\ndef divide(p: Problema) -> list[Problema]:\n    q = triominoCentral(p)\n    n, t = p\n    m = t.shape[0]\n    x = m \/\/ 2\n    subproblemas = [\n        (n+1, q[0:x, x:m]),\n        (n+2, q[0:x, 0:x]),\n        (n+3, q[x:m, 0:x]),\n        (n+4, q[x:m, x:m])\n    ]\n    return subproblemas\n\n# combina(p, ts) es la combinaci\u00f3n de las soluciones ts de los\n# subproblemas del problema p. Por ejemplo,\n#    >>> inicial = (1, tablero(4, (4, 4)))\n#    >>> p1, p2, p3, p4 = divide(inicial)\n#    >>> s1, s2, s3, s4 = map(resuelve, [p1, p2, p3, p4])\n#    >>> combina(inicial, [s1, s2, s3, s4])\n#    array([[ 3,  3,  2,  2],\n#           [ 3,  1,  1,  2],\n#           [ 4,  1,  5,  5],\n#           [ 4,  4,  5, -1]])\ndef combina(_: Problema, ts: list[Tablero]) -> Tablero:\n    s1, s2, s3, s4 = ts\n    combined = np.block([[s2, s1], [s3, s4]])\n    return combined\n\ndef triomino(n: int, p: Posicion) -> Tablero:\n    return divideVenceras(ind, resuelve, divide, combina, pbInicial(n, p))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_triomino() -> None:\n    def filas(p: Tablero) -> list[list[int]]:\n        return p.tolist()\n\n    assert filas(triomino(4, (4,4))) == \\\n        [[3,3,2,2],[3,1,1,2],[4,1,5,5],[4,4,5,-1]]\n    assert filas(triomino(4, (2,3))) == \\\n        [[3,3,2,2],[3,1,-1,2],[4,1,1,5],[4,4,5,5]]\n    assert filas(triomino(16, (5,6))) == \\\n        [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],\n         [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],\n         [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7],\n         [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],\n         [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],\n         [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],\n         [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],\n         [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],\n         [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],\n         [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],\n         [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],\n         [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],\n         [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],\n         [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],\n         [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],\n         [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_triomino()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. B\u00fasqueda en espacios de estados por profundidad<\/h3>\n<p>Las caracter\u00edsticas de los problemas de espacios de estados son:<\/p>\n<ul>\n<li>un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),<\/li>\n<li>un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,<\/li>\n<li>un nodo inicial y<\/li>\n<li>un nodo objetivo que es la soluci\u00f3n.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)\n                                  -> nodo -> [nodo]\n<\/pre>\n<p>tal que <code>buscaProfundidad s o e<\/code> es  la lista de soluciones del problema de espacio de estado definido por la funci\u00f3n sucesores <code>s<\/code>, el objetivo <code>o<\/code> y estado inicial <code>e<\/code> obtenidas mediante b\u00fasqueda en profundidad.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule BusquedaEnProfundidad (buscaProfundidad) where\n\nimport TAD.Pila (apila, cima, desapila, esVacia, vacia)\n\nbuscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)\n                               -> nodo -> [nodo]\nbuscaProfundidad sucesores esFinal inicial =\n  aux (apila inicial vacia)\n  where\n    aux p\n      | esVacia p        = []\n      | esFinal (cima p) = cima p : aux (desapila p)\n      | otherwise        = aux (foldr\n                                apila\n                                (desapila p)\n                                (sucesores (cima p)))\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom sys import setrecursionlimit\nfrom typing import Callable, TypeVar\n\nfrom src.TAD.pila import Pila, apila, cima, desapila, esVacia, vacia\n\nA = TypeVar('A')\n\nsetrecursionlimit(10**6)\n\ndef buscaProfundidad1(sucesores: Callable[[A], list[A]],\n                      esFinal: Callable[[A], bool],\n                      inicial: A) -> list[A]:\n    def aux(p: Pila[A]) -> list[A]:\n        if esVacia(p):\n            return []\n        if esFinal(cima(p)):\n            return [cima(p)] + aux(desapila(p))\n        return aux(reduce(lambda x, y: apila(y, x),\n                          sucesores(cima(p)),\n                          desapila(p)))\n\n    return aux(apila(inicial, vacia()))\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. El problema de las n reinas (mediante b\u00fasqueda por profundidad en espacios de estados)<\/h3>\n<p>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\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal.<\/p>\n<p>Las posiciones de las reinas en el tablero se representan por su columna y su fila.<\/p>\n<pre lang=\"text\">\n   type Columna = Int\n   type Fila    = Int\n<\/pre>\n<p>Una soluci\u00f3n del problema de las n reinas es una lista de posiciones.<\/p>\n<pre lang=\"text\">\n   type SolNR = [(Columna,Fila)]\n<\/pre>\n<p>Usando el procedimiento de <a href=\"\">b\u00fasqueda en profundidad<\/a>, definir las funciones<\/p>\n<pre lang=\"text\">\n   solucionesNR      :: Columna -> [SolNR]\n   primeraSolucionNR :: Columna -> SolNR\n   nSolucionesNR     :: Columna -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>solucionesNR n<\/code> es la lista de las soluciones del problema de las n reinas, por b\u00fasqueda de espacio de estados en profundidad. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     take 3 (solucionesNR 8)\n     [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],\n      [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],\n      [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]\n<\/pre>\n<ul>\n<li><code>primeraSolucionNR n<\/code> es la primera soluci\u00f3n del problema de las n reinas, por b\u00fasqueda en espacio de estados por profundidad. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> primeraSolucionNR 8\n     [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)]\n<\/pre>\n<ul>\n<li><code>nSolucionesNR n<\/code> es el n\u00famero de soluciones del problema de las n reinas, por b\u00fasqueda en espacio de estados. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nSolucionesNR 8  ==  92\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule BEE_Reinas_Profundidad where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Columna = Int\ntype Fila    = Int\ntype SolNR = [(Columna,Fila)]\n\n-- Los nodos del problema de las n reinas son ternas formadas por la\n-- columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n-- tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\ntype NodoNR = (Columna,Columna,SolNR)\n\nsolucionesNR :: Columna -> [SolNR]\nsolucionesNR n =\n  map estado (buscaProfundidad sucesoresNR esFinalNR (1,n,[]))\n  where\n    estado (_,_,e) = e\n\nprimeraSolucionNR :: Columna -> SolNR\nprimeraSolucionNR =\n  head . solucionesNR\n\nnSolucionesNR :: Columna -> Int\nnSolucionesNR =\n  length . solucionesNR\n\n-- (valida sp p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n-- soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n-- ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n-- columnas). Por ejemplo,\n--    valida [(1,1)] (2,2)  ==  False\n--    valida [(1,1)] (2,3)  ==  True\nvalida :: SolNR -> (Columna,Fila) -> Bool\nvalida solp (c,r) = and [test s | s <- solp]\n  where test (c',r') = c'+r'\/=c+r &#038;&#038; c'-r'\/=c-r &#038;&#038; r'\/=r\n\n-- (sucesoresNR e) es la lista de los sucesores del estado e en el\n-- problema de las n reinas. Por ejemplo,\n--    \u03bb> sucesoresNR (1,4,[])\n--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\nsucesoresNR :: NodoNR -> [NodoNR]\nsucesoresNR (c,n,solp) =\n  [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]\n\n-- (esFinalNR e) se verifica si e es un estado final del problema de las\n-- n reinas.\nesFinalNR :: NodoNR -> Bool\nesFinalNR (c,n,_) = c > n\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 3 (solucionesNR 8) `shouldBe`\n    [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],\n     [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],\n     [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]\n  it \"e2\" $\n    nSolucionesNR 8 `shouldBe` 92\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.1173 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\nColumna = int\nFila = int\nSolNR = list[tuple[Columna, Fila]]\n\n# Los nodos del problema de las n reinas son ternas formadas por la\n# columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n# tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\nNodoNR = tuple[Columna, Columna, SolNR]\n\n# valida(sp, p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n# soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n# ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n# columnas). Por ejemplo,\n#    valida([(1,1)], (2,2))  ==  False\n#    valida([(1,1)], (2,3))  ==  True\ndef valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:\n    c, r = p\n    def test(s: tuple[Columna, Fila]) -> bool:\n        c1, r1 = s\n        return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r\n\n    return all(test(s) for s in sp)\n\n# sucesoresNR(e) es la lista de los sucesores del estado e en el\n# problema de las n reinas. Por ejemplo,\n#    >>> sucesoresNR((1,4,[]))\n#    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\ndef sucesoresNR (nd: NodoNR) -> list[NodoNR]:\n    c,n,solp = nd\n    return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]\n\n# esFinalNR(e) se verifica si e es un estado final del problema de las\n# n reinas.\ndef esFinalNR(nd: NodoNR) -> bool:\n    c, n, _ = nd\n    return c > n\n\ndef solucionesNR(n: int) -> list[SolNR]:\n    nInicial: NodoNR = (1,n,[])\n    return [e for (_, _, e) in buscaProfundidad(sucesoresNR,\n                                                esFinalNR,\n                                                nInicial)]\n\ndef primeraSolucionNR(n: int) -> SolNR:\n    return solucionesNR(n)[0]\n\ndef nSolucionesNR(n: int) -> int:\n    return len(solucionesNR(n))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_nReinas() -> None:\n    assert solucionesNR(8)[:3] == \\\n        [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],\n         [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],\n         [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]\n    assert nSolucionesNR(8) == 92\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_nReinas()\n#    Verificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. B\u00fasqueda en espacios de estados por anchura<\/h3>\n<p>Las caracter\u00edsticas de los problemas de espacios de estados son:<\/p>\n<ul>\n<li>un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),<\/li>\n<li>un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,<\/li>\n<li>un nodo inicial y<\/li>\n<li>un nodo objetivo que es la soluci\u00f3n.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)\n                              -> nodo -> [nodo]\n<\/pre>\n<p>tal que <code>buscaAnchura s o e<\/code> es  la lista de soluciones del problema de espacio de estado definido por la funci\u00f3n sucesores <code>s<\/code>, el objetivo <code>o<\/code> y estado inicial <code>e<\/code> obtenidas mediante b\u00fasqueda en anchura.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule BusquedaEnAnchura (buscaAnchura) where\n\nimport TAD.Cola (esVacia, inserta, primero, resto, vacia)\n\nbuscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)\n                               -> nodo -> [nodo]\nbuscaAnchura sucesores esFinal inicial =\n  aux (inserta inicial vacia)\n  where\n    aux p\n      | esVacia p        = []\n      | esFinal (primero p) = primero p : aux (resto p)\n      | otherwise        = aux (foldr\n                                inserta\n                                (resto p)\n                                (sucesores (primero p)))\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom sys import setrecursionlimit\nfrom typing import Callable, TypeVar\n\nfrom src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia\n\nA = TypeVar('A')\n\nsetrecursionlimit(10**6)\n\ndef buscaAnchura(sucesores: Callable[[A], list[A]],\n                  esFinal: Callable[[A], bool],\n                  inicial: A) -> list[A]:\n    def aux(p: Cola[A]) -> list[A]:\n        if esVacia(p):\n            return []\n        if esFinal(primero(p)):\n            return [primero(p)] + aux(resto(p))\n        return aux(reduce(lambda x, y: inserta(y, x),\n                          sucesores(primero(p)),\n                          resto(p)))\n\n    return aux (inserta(inicial, vacia()))\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Algoritmo divide y vencer\u00e1s 2. Rompecabeza del triomin\u00f3 mediante divide y vencer\u00e1s 3. B\u00fasqueda en espacios de estados por profundidad 4. El problema de las n reinas (mediante b\u00fasqueda por profundidad en espacios de estados) 5. B\u00fasqueda en espacios de estados por&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[1],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7954"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7954"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7954\/revisions"}],"predecessor-version":[{"id":7955,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7954\/revisions\/7955"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7954"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7954"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7954"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}