La semana en Exercitium (1 de julio de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Algoritmo divide y vencerás
- 2. Rompecabeza del triominó mediante divide y vencerás
- 3. Búsqueda en espacios de estados por profundidad
- 4. El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)
- 5. Búsqueda en espacios de estados por anchura
A continuación se muestran las soluciones.
1. Algoritmo divide y vencerás
La técnica divide y vencerás consta de los siguientes pasos:
- Dividir el problema en subproblemas menores.
- Resolver por separado cada uno de los subproblemas:
- si los subproblemas son complejos, usar la misma técnica recursivamente;
- si son simples, resolverlos directamente.
- Combinar todas las soluciones de los subproblemas en una solución simple.
Definir la función
1 2 3 4 5 6 |
divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s |
tal que divideVenceras ind resuelve divide combina pbInicial
resuelve el problema pbInicial
mediante la técnica de divide y vencerás, donde
ind pb
se verifica si el problemapb
es indivisibleresuelve pb
es la solución del problema indivisiblepb
divide pb
es la lista de subproblemas depb
combina pb ss
es la combinación de las solucionesss
de los subproblemas del problemapb
.pbInicial
es el problema inicial
Usando la función DivideVenceras, definir las funciones
1 2 |
ordenaPorMezcla :: Ord a => [a] -> [a] ordenaRapida :: Ord a => [a] -> [a] |
tales que
ordenaPorMezcla xs
es la lista obtenida ordenandoxs
por el procedimiento de ordenación por mezcla. Por ejemplo,
1 2 |
λ> ordenaPorMezcla [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9] |
ordenaRapida xs
es la lista obtenida ordenandoxs
por el procedimiento de ordenación rápida. Por ejemplo,
1 2 |
λ> ordenaRapida [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
module DivideVenceras (divideVenceras) where import Test.Hspec (Spec, hspec, it, shouldBe) divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideVenceras ind resuelve divide combina = dv' where dv' pb | ind pb = resuelve pb | otherwise = combina pb [dv' sp | sp <- divide pb] ordenaPorMezcla :: Ord a => [a] -> [a] ordenaPorMezcla = divideVenceras ind id divide combina where ind xs = length xs <= 1 divide xs = [take n xs, drop n xs] where n = length xs `div` 2 combina _ [l1,l2] = mezcla l1 l2 -- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo, -- mezcla [1,3] [2,4,6] == [1,2,3,4,6] mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] b = b mezcla a [] = a mezcla a@(x:xs) b@(y:ys) | x <= y = x : mezcla xs b | otherwise = y : mezcla a ys ordenaRapida :: Ord a => [a] -> [a] ordenaRapida = divideVenceras ind id divide combina where ind xs = length xs <= 1 divide (x:xs) = [[ y | y <- xs, y <= x], [ y | y <- xs, y > x]] combina (x:_) [l1,l2] = l1 ++ [x] ++ l2 -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9] it "e2" $ ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0004 seconds -- 2 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
from typing import Callable, TypeVar P = TypeVar('P') S = TypeVar('S') def divideVenceras(ind: Callable[[P], bool], resuelve: Callable[[P], S], divide: Callable[[P], list[P]], combina: Callable[[P, list[S]], S], p: P) -> S: def dv(pb: P) -> S: if ind(pb): return resuelve(pb) return combina(pb, [dv(sp) for sp in divide(pb)]) return dv(p) def ordenaPorMezcla(xs: list[int]) -> list[int]: def ind(xs: list[int]) -> bool: return len(xs) <= 1 def divide(xs: list[int]) -> list[list[int]]: n = len(xs) // 2 return [xs[:n], xs[n:]] def combina(_: list[int], xs: list[list[int]]) -> list[int]: return mezcla(xs[0], xs[1]) return divideVenceras(ind, lambda x: x, divide, combina, xs) # (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo, # mezcla([1,3], [2,4,6]) == [1,2,3,4,6] def mezcla(a: list[int], b: list[int]) -> list[int]: if not a: return b if not b: return a if a[0] <= b[0]: return [a[0]] + mezcla(a[1:], b) return [b[0]] + mezcla(a, b[1:]) def ordenaRapida(xs: list[int]) -> list[int]: def ind(xs: list[int]) -> bool: return len(xs) <= 1 def divide(xs: list[int]) -> list[list[int]]: x, *xs = xs return [[y for y in xs if y <= x], [y for y in xs if y > x]] def combina(xs: list[int], ys: list[list[int]]) -> list[int]: x = xs[0] return ys[0] + [x] + ys[1] return divideVenceras(ind, lambda x: x, divide, combina, xs) # Verificación # ============ def test_divideVenceras() -> None: assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9] assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9] print("Verificado") # La verificación es # >>> test_divideVenceras() # Verificado |
2. Rompecabeza del triominó mediante divide y vencerás
Un poliominó es una figura geométrica plana formada conectando dos o más cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus vértices, 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ó, si se juntan tres cuadrados se construye un triominó.
Sólo existen dos triominós, el I-triomino (por tener forma de I) y el L-triominó (por su forma de L) como se observa en las siguientes figuras
1 2 3 |
X X X X XX |
El rompecabeza del triominó 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ós de formas que cubran todas las casillas excepto la eliminada y los triominós no se solapen.
La casilla eliminada se representará con -1 y los L-triominós sucesiones de tres números consecutivos en forma de L. Con esta representación una solución del rompecabeza del triominó con 4 filas y la fila eliminada en la posición (4,4) es
1 2 3 4 |
( 3 3 2 2 ) ( 3 1 1 2 ) ( 4 1 5 5 ) ( 4 4 5 -1 ) |
Definir la función
1 |
triomino :: Int -> Posicion -> Tablero |
tal que (triomino n p) es la solución, mediante divide y vencerás, del rompecabeza del triominó en un cuadrado nxn en el que se ha eliminado la casilla de la posición p. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
λ> triomino 4 (4,4) ( 3 3 2 2 ) ( 3 1 1 2 ) ( 4 1 5 5 ) ( 4 4 5 -1 ) λ> triomino 4 (2,3) ( 3 3 2 2 ) ( 3 1 -1 2 ) ( 4 1 1 5 ) ( 4 4 5 5 ) λ> triomino 16 (5,6) ( 7 7 6 6 6 6 5 5 6 6 5 5 5 5 4 4 ) ( 7 5 5 6 6 4 4 5 6 4 4 5 5 3 3 4 ) ( 8 5 9 9 7 7 4 8 7 4 8 8 6 6 3 7 ) ( 8 8 9 3 3 7 8 8 7 7 8 2 2 6 7 7 ) ( 8 8 7 3 9 -1 8 8 7 7 6 6 2 8 7 7 ) ( 8 6 7 7 9 9 7 8 7 5 5 6 8 8 6 7 ) ( 9 6 6 10 10 7 7 11 8 8 5 9 9 6 6 10 ) ( 9 9 10 10 10 10 11 11 1 8 9 9 9 9 10 10 ) ( 8 8 7 7 7 7 6 1 1 9 8 8 8 8 7 7 ) ( 8 6 6 7 7 5 6 6 9 9 7 8 8 6 6 7 ) ( 9 6 10 10 8 5 5 9 10 7 7 11 9 9 6 10 ) ( 9 9 10 4 8 8 9 9 10 10 11 11 5 9 10 10 ) ( 9 9 8 4 4 10 9 9 10 10 9 5 5 11 10 10 ) ( 9 7 8 8 10 10 8 9 10 8 9 9 11 11 9 10 ) ( 10 7 7 11 11 8 8 12 11 8 8 12 12 9 9 13 ) ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 ) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
module Rompecabeza_del_triomino_mediante_divide_y_venceras where import DivideVenceras (divideVenceras) import Data.Matrix import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) -- Los tableros son matrices de números enteros donde -1 representa el -- hueco, 0 las posiciones sin rellenar y los números mayores que 0 -- representan los triominós. type Tablero = Matrix Int -- Los problemas se representarán mediante pares formados por un número -- natural mayor que 0 (que indica el número con el que se formará el -- siguiente triominó que se coloque) y un tablero. type Problema = (Int,Tablero) -- Las posiciones son pares de números enteros type Posicion = (Int,Int) triomino :: Int -> Posicion -> Tablero triomino n p = divideVenceras ind resuelve divide combina (pbInicial n p) -- (tablero n p) es el tablero inicial del problema del triominó -- en un cuadrado nxn en el que se ha eliminado la casilla de la -- posición (i,j). Por ejemplo, -- λ> tablero 4 (3,4) -- ( 0 0 0 0 ) -- ( 0 0 0 0 ) -- ( 0 0 0 -1 ) -- ( 0 0 0 0 ) tablero :: Int -> Posicion -> Tablero tablero n (i,j) = setElem (-1) (i,j) (zero n n) -- (pbInicial n p) es el problema inicial del rompecabeza del triominó -- en un cuadrado nxn en el que se ha eliminado la casilla de la -- posición p. Por ejemplo, -- λ> pbInicial 4 (4,4) -- (1,( 0 0 0 0 ) -- ( 0 0 0 0 ) -- ( 0 0 0 0 ) -- ( 0 0 0 -1 )) pbInicial :: Int -> Posicion -> Problema pbInicial n p = (1,tablero n p) -- (ind pb) se verifica si el problema pb es indivisible. Por ejemplo, -- ind (pbInicial 2 (1,2)) == True -- ind (pbInicial 4 (1,2)) == False ind :: Problema -> Bool ind (_,p) = ncols p == 2 -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- posicionHueco (tablero 8 (5,2)) == (5,2) posicionHueco :: Tablero -> Posicion posicionHueco p = head [(i,j) | i <- [1..nrows p], j <- [1..ncols p], p!(i,j) /= 0] -- (cuadranteHueco p) es el cuadrante donde se encuentra el hueco del -- tablero t (donde la numeración de los cuadrantes es 1 el superior -- izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el -- inferior derecho). Por ejemplo, -- cuadranteHueco (tablero 8 (4,4)) == 1 -- cuadranteHueco (tablero 8 (5,2)) == 2 -- cuadranteHueco (tablero 8 (3,6)) == 3 -- cuadranteHueco (tablero 8 (6,6)) == 4 cuadranteHueco :: Tablero -> Int cuadranteHueco t | i <= x && j <= x = 1 | i > x && j <= x = 2 | i <= x && j > x = 3 | otherwise = 4 where (i,j) = posicionHueco t x = nrows t `div` 2 -- (centralHueco t) es la casilla central del cuadrante del tablero t -- donde se encuentra el hueco. Por ejemplo, -- centralHueco (tablero 8 (5,2)) == (5,4) -- centralHueco (tablero 8 (4,4)) == (4,4) -- centralHueco (tablero 8 (3,6)) == (4,5) -- centralHueco (tablero 8 (6,6)) == (5,5) centralHueco :: Tablero -> Posicion centralHueco t = case cuadranteHueco t of 1 -> (x,x) 2 -> (x+1,x) 3 -> (x,x+1) _ -> (x+1,x+1) where x = nrows t `div` 2 -- (centralesSinHueco t) son las posiciones centrales del tablero t de -- los cuadrantes sin hueco. Por ejemplo, -- centralesSinHueco (tablero 8 (5,2)) == [(4,4),(4,5),(5,5)] centralesSinHueco :: Tablero -> [Posicion] centralesSinHueco t = delete (i,j) [(x,x),(x+1,x),(x,x+1),(x+1,x+1)] where x = nrows t `div` 2 (i,j) = centralHueco t -- (actualiza t ps) es la matriz obtenida cambiando en t los valores del -- las posiciones indicadas en ps por sus correspondientes valores. Por -- ejemplo, -- λ> actualiza (identity 3) [((1,2),4),((3,1),5)] -- ( 1 4 0 ) -- ( 0 1 0 ) -- ( 5 0 1 ) actualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a actualiza p [] = p actualiza p (((i,j),x):zs) = setElem x (i,j) (actualiza p zs) -- (triominoCentral (n,t) es el tablero obtenido colocando el triominó -- formado por el número n en las posiciones centrales de los 3 -- cuadrantes que no contienen el hueco. Por ejemplo, -- λ> triominoCentral (7,tablero 4 (4,4)) -- ( 0 0 0 0 ) -- ( 0 7 7 0 ) -- ( 0 7 0 0 ) -- ( 0 0 0 -1 ) triominoCentral :: Problema -> Tablero triominoCentral (n,t) = actualiza t [((i,j),n) | (i,j) <- centralesSinHueco t] -- (resuelve p) es la solución del problema indivisible p. Por ejemplo, -- λ> tablero 2 (2,2) -- ( 0 0 ) -- ( 0 -1 ) -- -- λ> resuelve (5,tablero 2 (2,2)) -- ( 5 5 ) -- ( 5 -1 ) resuelve :: Problema -> Tablero resuelve = triominoCentral -- (divide (n,t)) es la lista de de los problemas obtenidos colocando el -- triominó n en las casillas centrales de t que no contienen el hueco y -- dividir el tablero en sus cuatros cuadrantes y aumentar en uno el -- número del correspondiente triominó. Por ejemplo, -- λ> divide (3,tablero 4 (4,4)) -- [(4,( 0 0 ) -- ( 3 0 )), -- (5,( 0 0 ) -- ( 0 3 )), -- (6,( 0 3 ) -- ( 0 0 )), -- (7,( 0 0 ) -- ( 0 -1 ))] divide :: Problema -> [Problema] divide (n,t) = [(n+1, submatrix 1 x (x+1) m q), (n+2, submatrix 1 x 1 x q), (n+3, submatrix (x+1) m 1 x q), (n+4, submatrix (x+1) m (x+1) m q)] where q = triominoCentral (n,t) m = nrows t x = m `div` 2 -- (combina p ts) es la combinación de las soluciones ts de los -- subproblemas del problema p. Por ejemplo, -- λ> let inicial = (1,tablero 4 (4,4)) :: (Int,Matrix Int) -- λ> let [p1,p2,p3,p4] = divide inicial -- λ> let [s1,s2,s3,s4] = map resuelve [p1,p2,p3,p4] -- λ> combina inicial [s1,s2,s3,s4] -- ( 3 3 2 2 ) -- ( 3 1 1 2 ) -- ( 4 1 5 5 ) -- ( 4 4 5 -1 ) combina :: Problema -> [Tablero] -> Tablero combina _ [s1,s2,s3,s4] = joinBlocks (s2,s1,s3,s4) combina _ _ = error "Imposible" -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ toLists (triomino 4 (4,4)) `shouldBe` [[3,3,2,2], [3,1,1,2], [4,1,5,5], [4,4,5,-1]] it "e2" $ toLists (triomino 4 (2,3)) `shouldBe` [[3,3,2,2], [3,1,-1,2], [4,1,1,5], [4,4,5,5]] it "e3" $ toLists (triomino 16 (5,6)) `shouldBe` [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4], [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4], [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7], [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7], [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7], [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7], [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10], [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10], [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7], [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7], [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10], [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10], [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10], [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10], [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13], [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0018 seconds -- 3 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
import numpy as np import numpy.typing as npt from src.DivideVenceras import divideVenceras # Los tableros son matrices de números enteros donde -1 representa el # hueco, 0 las posiciones sin rellenar y los números mayores que 0 # representan los triominós. Tablero = npt.NDArray[np.complex64] # Los problemas se representarán mediante pares formados por un número # natural mayor que 0 (que indica el número con el que se formará el # siguiente triominó que se coloque) y un tablero. Problema = tuple[int, Tablero] # Las posiciones son pares de números enteros Posicion = tuple[int, int] # tablero(n p) es el tablero inicial del problema del triominó # en un cuadrado nxn en el que se ha eliminado la casilla de la # posición p. Por ejemplo, # >>> tablero(4, (3,4)) # array([[ 0, 0, 0, 0], # [ 0, 0, 0, 0], # [ 0, 0, 0, -1], # [ 0, 0, 0, 0]]) def tablero(n: int, p: Posicion) -> Tablero: (i, j) = p q = np.zeros((n, n), dtype=int) q[i - 1, j - 1] = -1 return q # pbInicial(n, p) es el problema inicial del rompecabeza del triominó # en un cuadrado nxn en el que se ha eliminado la casilla de la # posición p. Por ejemplo, # >>> pbInicial(4, (4,4)) # (1, array([[ 0, 0, 0, 0], # [ 0, 0, 0, 0], # [ 0, 0, 0, 0], # [ 0, 0, 0, -1]])) def pbInicial(n: int, p: Posicion) -> Problema: return 1, tablero(n, p) # ind(pb) se verifica si el problema pb es indivisible. Por ejemplo, # ind(pbInicial(2, (1,2))) == True # ind(pbInicial(4, (1,2))) == False def ind(pb: Problema) -> bool: _, p = pb return p.shape[1] == 2 # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # posicionHueco(tablero(8, (5,2))) == (5,2) def posicionHueco(t: Tablero) -> Posicion: indices = np.argwhere(t != 0) (i, j) = tuple(indices[0]) return (i + 1, j + 1) # cuadranteHueco(p) es el cuadrante donde se encuentra el hueco del # tablero t (donde la numeración de los cuadrantes es 1 el superior # izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el # inferior derecho). Por ejemplo, # cuadranteHueco(tablero(8, (4,4))) == 1 # cuadranteHueco(tablero(8, (5,2))) == 2 # cuadranteHueco(tablero(8, (3,6))) == 3 # cuadranteHueco(tablero(8, (6,6))) == 4 def cuadranteHueco(t: Tablero) -> int: i, j = posicionHueco(t) x = t.shape[0] // 2 if j <= x: if i <= x: return 1 return 2 if i <= x: return 3 return 4 # centralHueco(t) es la casilla central del cuadrante del tablero t # donde se encuentra el hueco. Por ejemplo, # centralHueco(tablero(8, (5,2))) == (5,4) # centralHueco(tablero(8, (4,4))) == (4,4) # centralHueco(tablero(8, (3,6))) == (4,5) # centralHueco(tablero(8, (6,6))) == (5,5) def centralHueco(t: Tablero) -> Posicion: x = t.shape[0] // 2 cuadrante = cuadranteHueco(t) if cuadrante == 1: return (x, x) if cuadrante == 2: return (x+1, x) if cuadrante == 3: return (x, x+1) return (x+1, x+1) # centralesSinHueco(t) son las posiciones centrales del tablero t de # los cuadrantes sin hueco. Por ejemplo, # centralesSinHueco(tablero(8, (5,2))) == [(4,4),(4,5),(5,5)] def centralesSinHueco(t: Tablero) -> list[Posicion]: x = t.shape[0] // 2 i, j = centralHueco(t) ps = [(x, x), (x+1, x), (x, x+1), (x+1, x+1)] return [p for p in ps if p != (i, j)] # actualiza(t, ps) es la matriz obtenida cambiando en t los valores del # las posiciones indicadas en ps por sus correspondientes valores. Por # ejemplo, # >>> actualiza(np.identity(3, dtype=int), [((1,2),4),((3,1),5)]) # array([[1, 4, 0], # [0, 1, 0], # [5, 0, 1]]) def actualiza(p: Tablero, ps: list[tuple[Posicion, int]]) -> Tablero: for (i, j), x in ps: p[i - 1, j - 1] = x return p # triominoCentral(n,t) es el tablero obtenido colocando el triominó # formado por el número n en las posiciones centrales de los 3 # cuadrantes que no contienen el hueco. Por ejemplo, # >>> triominoCentral((7, tablero(4, (4,4)))) # array([[ 0, 0, 0, 0], # [ 0, 7, 7, 0], # [ 0, 7, 0, 0], # [ 0, 0, 0, -1]]) def triominoCentral(p: Problema) -> Tablero: n, t = p return actualiza(t, [((i,j),n) for (i,j) in centralesSinHueco(t)]) # resuelve(p) es la solución del problema indivisible p. Por ejemplo, # >>> tablero(2, (2,2)) # array([[ 0, 0], # [ 0, -1]]) # >>> resuelve((5,tablero(2, (2,2)))) # array([[ 5, 5], # [ 5, -1]]) def resuelve(p: Problema) -> Tablero: return triominoCentral(p) # divide(n,t) es la lista de de los problemas obtenidos colocando el # triominó n en las casillas centrales de t que no contienen el hueco y # dividir el tablero en sus cuatros cuadrantes y aumentar en uno el # número del correspondiente triominó. Por ejemplo, # >>> divide((3,tablero(4, (4,4)))) # [(4, array([[0, 0], # [3, 0]])), # (5, array([[0, 0], # [0, 3]])), # (6, array([[0, 3], # [0, 0]])), # (7, array([[ 0, 0], # [ 0, -1]]))] def divide(p: Problema) -> list[Problema]: q = triominoCentral(p) n, t = p m = t.shape[0] x = m // 2 subproblemas = [ (n+1, q[0:x, x:m]), (n+2, q[0:x, 0:x]), (n+3, q[x:m, 0:x]), (n+4, q[x:m, x:m]) ] return subproblemas # combina(p, ts) es la combinación de las soluciones ts de los # subproblemas del problema p. Por ejemplo, # >>> inicial = (1, tablero(4, (4, 4))) # >>> p1, p2, p3, p4 = divide(inicial) # >>> s1, s2, s3, s4 = map(resuelve, [p1, p2, p3, p4]) # >>> combina(inicial, [s1, s2, s3, s4]) # array([[ 3, 3, 2, 2], # [ 3, 1, 1, 2], # [ 4, 1, 5, 5], # [ 4, 4, 5, -1]]) def combina(_: Problema, ts: list[Tablero]) -> Tablero: s1, s2, s3, s4 = ts combined = np.block([[s2, s1], [s3, s4]]) return combined def triomino(n: int, p: Posicion) -> Tablero: return divideVenceras(ind, resuelve, divide, combina, pbInicial(n, p)) # Verificación # ============ def test_triomino() -> None: def filas(p: Tablero) -> list[list[int]]: return p.tolist() assert filas(triomino(4, (4,4))) == \ [[3,3,2,2],[3,1,1,2],[4,1,5,5],[4,4,5,-1]] assert filas(triomino(4, (2,3))) == \ [[3,3,2,2],[3,1,-1,2],[4,1,1,5],[4,4,5,5]] assert filas(triomino(16, (5,6))) == \ [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4], [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4], [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7], [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7], [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7], [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7], [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10], [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10], [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7], [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7], [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10], [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10], [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10], [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10], [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13], [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]] print("Verificado") # La verificación es # >>> test_triomino() # Verificado |
3. 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
1 2 |
buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
module BusquedaEnProfundidad (buscaProfundidad) where import TAD.Pila (apila, cima, desapila, esVacia, vacia) buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] buscaProfundidad sucesores esFinal inicial = aux (apila inicial vacia) where aux p | esVacia p = [] | esFinal (cima p) = cima p : aux (desapila p) | otherwise = aux (foldr apila (desapila p) (sucesores (cima p))) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from functools import reduce from sys import setrecursionlimit from typing import Callable, TypeVar from src.TAD.pila import Pila, apila, cima, desapila, esVacia, vacia A = TypeVar('A') setrecursionlimit(10**6) def buscaProfundidad1(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> list[A]: def aux(p: Pila[A]) -> list[A]: if esVacia(p): return [] if esFinal(cima(p)): return [cima(p)] + aux(desapila(p)) return aux(reduce(lambda x, y: apila(y, x), sucesores(cima(p)), desapila(p))) return aux(apila(inicial, vacia())) |
4. 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.
1 2 |
type Columna = Int type Fila = Int |
Una solución del problema de las n reinas es una lista de posiciones.
1 |
type SolNR = [(Columna,Fila)] |
Usando el procedimiento de búsqueda en profundidad, definir las funciones
1 2 3 |
solucionesNR :: Columna -> [SolNR] primeraSolucionNR :: Columna -> SolNR nSolucionesNR :: Columna -> Int |
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,
1 2 3 4 |
take 3 (solucionesNR 8) [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)], [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)], [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]] |
primeraSolucionNR n
es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,
1 2 |
λ> primeraSolucionNR 8 [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)] |
nSolucionesNR n
es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,
1 |
nSolucionesNR 8 == 92 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
module BEE_Reinas_Profundidad where import BusquedaEnProfundidad (buscaProfundidad) import Test.Hspec (Spec, hspec, it, shouldBe) type Columna = Int type Fila = Int type SolNR = [(Columna,Fila)] -- Los nodos del problema de las n reinas son ternas formadas por la -- columna de la última reina colocada, el número de columnas del -- tablero y la solución parcial de las reinas colocadas anteriormente. type NodoNR = (Columna,Columna,SolNR) solucionesNR :: Columna -> [SolNR] solucionesNR n = map estado (buscaProfundidad sucesoresNR esFinalNR (1,n,[])) where estado (_,_,e) = e primeraSolucionNR :: Columna -> SolNR primeraSolucionNR = head . solucionesNR nSolucionesNR :: Columna -> Int nSolucionesNR = length . solucionesNR -- (valida sp p) se verifica si la posición p es válida respecto de la -- solución parcial sp; es decir, la reina en la posición p no amenaza a -- ninguna de las reinas de la sp (se supone que están en distintas -- columnas). Por ejemplo, -- valida [(1,1)] (2,2) == False -- valida [(1,1)] (2,3) == True valida :: SolNR -> (Columna,Fila) -> Bool valida solp (c,r) = and [test s | s <- solp] where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r -- (sucesoresNR e) es la lista de los sucesores del estado e en el -- problema de las n reinas. Por ejemplo, -- λ> sucesoresNR (1,4,[]) -- [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] sucesoresNR :: NodoNR -> [NodoNR] sucesoresNR (c,n,solp) = [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)] -- (esFinalNR e) se verifica si e es un estado final del problema de las -- n reinas. esFinalNR :: NodoNR -> Bool esFinalNR (c,n,_) = c > n -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ take 3 (solucionesNR 8) `shouldBe` [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)], [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)], [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]] it "e2" $ nSolucionesNR 8 `shouldBe` 92 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.1173 seconds -- 2 examples, 0 failures |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from src.BusquedaEnProfundidad import buscaProfundidad Columna = int Fila = int SolNR = list[tuple[Columna, Fila]] # Los nodos del problema de las n reinas son ternas formadas por la # columna de la última reina colocada, el número de columnas del # tablero y la solución parcial de las reinas colocadas anteriormente. NodoNR = tuple[Columna, Columna, SolNR] # valida(sp, p) se verifica si la posición p es válida respecto de la # solución parcial sp; es decir, la reina en la posición p no amenaza a # ninguna de las reinas de la sp (se supone que están en distintas # columnas). Por ejemplo, # valida([(1,1)], (2,2)) == False # valida([(1,1)], (2,3)) == True def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool: c, r = p def test(s: tuple[Columna, Fila]) -> bool: c1, r1 = s return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r return all(test(s) for s in sp) # sucesoresNR(e) es la lista de los sucesores del estado e en el # problema de las n reinas. Por ejemplo, # >>> sucesoresNR((1,4,[])) # [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] def sucesoresNR (nd: NodoNR) -> list[NodoNR]: c,n,solp = nd return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))] # esFinalNR(e) se verifica si e es un estado final del problema de las # n reinas. def esFinalNR(nd: NodoNR) -> bool: c, n, _ = nd return c > n def solucionesNR(n: int) -> list[SolNR]: nInicial: NodoNR = (1,n,[]) return [e for (_, _, e) in buscaProfundidad(sucesoresNR, esFinalNR, nInicial)] def primeraSolucionNR(n: int) -> SolNR: return solucionesNR(n)[0] def nSolucionesNR(n: int) -> int: return len(solucionesNR(n)) # Verificación # ============ def test_nReinas() -> None: assert solucionesNR(8)[:3] == \ [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)], [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)], [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]] assert nSolucionesNR(8) == 92 print("Verificado") # La verificación es # >>> test_nReinas() # Verificado |
5. Búsqueda en espacios de estados por anchura
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
1 2 |
buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] |
tal que buscaAnchura 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 anchura.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
module BusquedaEnAnchura (buscaAnchura) where import TAD.Cola (esVacia, inserta, primero, resto, vacia) buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] buscaAnchura sucesores esFinal inicial = aux (inserta inicial vacia) where aux p | esVacia p = [] | esFinal (primero p) = primero p : aux (resto p) | otherwise = aux (foldr inserta (resto p) (sucesores (primero p))) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from functools import reduce from sys import setrecursionlimit from typing import Callable, TypeVar from src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia A = TypeVar('A') setrecursionlimit(10**6) def buscaAnchura(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> list[A]: def aux(p: Cola[A]) -> list[A]: if esVacia(p): return [] if esFinal(primero(p)): return [primero(p)] + aux(resto(p)) return aux(reduce(lambda x, y: inserta(y, x), sucesores(primero(p)), resto(p))) return aux (inserta(inicial, vacia())) |