El problema del 8 puzzle
Para el 8-puzzle se usa un cajón cuadrado en el que hay situados bloques cuadrados. El cuadrado restante está sin rellenar. Cada bloque tiene un número. Un bloque adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:
|
1 2 3 4 5 6 7 8 |
+---+---+---+ +---+---+---+ | | 1 | 3 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ | 8 | 2 | 4 | | 8 | | 4 | +---+---+---+ +---+---+---+ | 7 | 5 | 5 | | 7 | 6 | 5 | +---+---+---+ +---+---+---+ Estado inicial Estado final |
Para solucionar el problema se definen los siguientes tipos:
Tableroes una matriz de número enteros (que representan las piezas en
cada posición y el 0 representa el hueco):
|
1 |
type Tablero = Matrix Int |
Estadoes una listas de tableros [t_n,…,t_1] tal que t_i es un
sucesor de t_(i-1).
|
1 2 |
newtype Estado = Est [Tablero] deriving Show |
Usando el procedimiento de búsqueda por primero el mejor, definir la función
|
1 |
solucion_8puzzle :: Tablero -> [Tablero] |
tal que (solucion_8puzzle t) es la solución del problema del problema del 8 puzzle a partir del tablero t. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]]) [┌ ┐ ┌ ┐ ┌ ┐ │ 0 1 3 │ │ 1 0 3 │ │ 1 2 3 │ │ 8 2 4 │ │ 8 2 4 │ │ 8 0 4 │ │ 7 6 5 │ │ 7 6 5 │ │ 7 6 5 │ └ ┘, └ ┘, └ ┘] λ> length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]])) 21 |
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 |
module BPM_8Puzzle where import BusquedaPrimeroElMejor (buscaPM) import Data.Matrix (Matrix, (!), fromLists, setElem, toLists) import Test.Hspec (Spec, hspec, it, shouldBe) type Tablero = Matrix Int newtype Estado = Est [Tablero] deriving (Eq, Show) solucion_8puzzle :: Tablero -> [Tablero] solucion_8puzzle t = reverse ts where (Est ts) = head (buscaPM sucesores esFinal (inicial t)) -- Estado inicial -- ============== -- (inicial t) es el estado inicial del problema del 8 puzzle a partir del -- tablero t. inicial :: Tablero -> Estado inicial t = Est [t] -- Estado final -- ============ -- (esFinal e) se verifica si e es un estado final. esFinal :: Estado -> Bool esFinal (Est (n:_)) = n == tableroFinal -- tableroFinal es el estado tablero final del 8 puzzle. tableroFinal :: Tablero tableroFinal = fromLists [[1,2,3], [8,0,4], [7,6,5]] -- Sucesores -- ========= -- (sucesores e) es la lista de sucesores del estado e. Por ejemplo, -- λ> sucesores (Est [fromLists [[2,1,3],[8,0,4],[7,6,5]]]) -- [Est [┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 6 4 │ │ 8 0 4 │ -- │ 7 0 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 0 8 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 4 0 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘]] sucesores :: Estado -> [Estado] sucesores (Est e@(t:_)) = [Est (t':e) | t' <- tablerosSucesores t, t' `notElem` e] -- (tablerosSucesores t) es la lista de los tableros sucesores del -- tablero t. Por ejemplo, -- λ> tablerosSucesores (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- [┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ │ 2 1 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 6 4 │ │ 0 8 4 │ │ 8 4 0 │ -- │ 7 6 5 │ │ 7 0 5 │ │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘, └ ┘, └ ┘] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia t p q | q <- posicionesVecinas p] where p = posicionHueco t -- Una posición es un par de enteros. type Posicion = (Int,Int) -- (posicionesVecinas p) son las posiciones de la matriz cuadrada de -- dimensión 3 que se encuentran encima, abajo, a la izquierda y a la -- derecha de los posición p. Por ejemplo, -- λ> posicionesVecinas (2,2) -- [(1,2),(3,2),(2,1),(2,3)] -- λ> posicionesVecinas (1,2) -- [(2,2),(1,1),(1,3)] -- λ> posicionesVecinas (1,1) -- [(2,1),(1,2)] posicionesVecinas :: Posicion -> [Posicion] posicionesVecinas (i,j) = [(i-1,j) | i > 1] ++ [(i+1,j) | i < 3] ++ [(i,j-1) | j > 1] ++ [(i,j+1) | j < 3] -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- λ> posicionHueco (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- (2,2) posicionHueco :: Tablero -> Posicion posicionHueco t = posicionElemento t 0 -- (posicionElemento t a) es la posición de elemento a en el tablero -- t. Por ejemplo, -- λ> posicionElemento (fromLists [[2,1,3],[8,0,4],[7,6,5]]) 4 -- (2,3) posicionElemento :: Tablero -> Int -> Posicion posicionElemento t a = head [(i,j) | i <- [1..3], j <- [1..3], t ! (i,j) == a] -- (intercambia t p1 p2) es el tablero obtenido intercambiando en t los -- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, -- λ> intercambia (fromLists [[2,1,3],[8,0,4],[7,6,5]]) (1,2) (2,2) -- ┌ ┐ -- │ 2 0 3 │ -- │ 8 1 4 │ -- │ 7 6 5 │ -- └ ┘ intercambia :: Tablero -> Posicion -> Posicion -> Tablero intercambia t p1 p2 = setElem a2 p1 (setElem a1 p2 t) where a1 = t ! p1 a2 = t ! p2 -- Heurística -- ========== -- (heuristica t) es la suma de la distancia Manhatan desde la posición de -- cada objeto del tablero a su posición en el tablero final. Por -- ejemplo, -- λ> heuristica (fromLists [[0,1,3],[8,2,4],[7,6,5]]) -- 4 heuristica :: Tablero -> Int heuristica t = sum [distancia (posicionElemento t i) (posicionElemento tableroFinal i) | i <- [0..8]] -- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y -- p2. Por ejemplo, -- distancia (2,7) (4,1) == 8 distancia :: Posicion -> Posicion -> Int distancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2) -- Comparación de estados -- ====================== -- Un estado es menor o igual que otro si tiene la heurística de su -- primer tablero es menor o que la del segundo o so iguales y el -- primero es más corto. instance Ord Estado where Est (t1:ts1) <= Est (t2:ts2) = (heuristica t1 < heuristica t2) || ((heuristica t1 == heuristica t2) && (length ts1 <= length ts2)) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ map toLists (solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])) `shouldBe` [[[0,1,3], [8,2,4], [7,6,5]], [[1,0,3], [8,2,4], [7,6,5]], [[1,2,3], [8,0,4], [7,6,5]]] it "e2" $ length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]])) `shouldBe` 21 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.1361 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 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 |
from copy import deepcopy from typing import Optional from src.BusquedaPrimeroElMejor import buscaPM Tablero = list[list[int]] # Tablero final # ============= # tableroFinal es el tablero final del 8 puzzle. tableroFinal: Tablero = [[1,2,3], [8,0,4], [7,6,5]] # Posiciones # ========== # Una posición es un par de enteros. Posicion = tuple[int,int] # Heurística # ========== # distancia(p1, p2) es la distancia Manhatan entre las posiciones p1 y # p2. Por ejemplo, # >>> distancia((2,7), (4,1)) # 8 def distancia(p1: Posicion, p2: Posicion) -> int: (x1, y1) = p1 (x2, y2) = p2 return abs(x1-x2) + abs (y1-y2) # posicionElemento(t, a) es la posición de elemento a en el tablero # t. Por ejemplo, # λ> posicionElemento([[2,1,3],[8,0,4],[7,6,5]], 4) # (1, 2) def posicionElemento(t: Tablero, a: int) -> Posicion: for i in range(0, 3): for j in range(0, 3): if t[i][j] == a: return (i, j) return (4, 4) # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # >>> posicionHueco([[2,1,3],[8,0,4],[7,6,5]]) # (1, 1) def posicionHueco(t: Tablero) -> Posicion: return posicionElemento(t, 0) # heuristica(t) es la suma de la distancia Manhatan desde la posición de # cada objeto del tablero a su posición en el tablero final. Por # ejemplo, # >>> heuristica([[0,1,3],[8,2,4],[7,6,5]]) # 4 def heuristica(t: Tablero) -> int: return sum((distancia(posicionElemento(t, i), posicionElemento(tableroFinal, i)) for i in range(0, 10))) # Estados # ======= # Un estado es una tupla (h, n, ts), donde ts es una listas de tableros # [t_n,...,t_1] tal que t_i es un sucesor de t_(i-1) y h es la # heurística de t_n. Estado = tuple[int, int, list[Tablero]] # Estado inicial # ============== # inicial(t) es el estado inicial del problema del 8 puzzle a partir del # tablero t. def inicial(t: Tablero) -> Estado: return (heuristica(t), 1, [t]) # Estado final # ============ # esFinal(e) se verifica si e es un estado final. def esFinal(e: Estado) -> bool: (_, _, ts) = e return ts[0] == tableroFinal # Sucesores # ========= # posicionesVecinas(p) son las posiciones de la matriz cuadrada de # dimensión 3 que se encuentran encima, abajo, a la izquierda y a la # derecha de los posición p. Por ejemplo, # >>> posicionesVecinas((1,1)) # [(0, 1), (2, 1), (1, 0), (1, 2)] # >>> posicionesVecinas((0,1)) # [(1, 1), (0, 0), (0, 2)] # >>> posicionesVecinas((0,0)) # [(1, 0), (0, 1)] def posicionesVecinas(p: Posicion) -> list[Posicion]: (i, j) = p vecinas = [] if i > 0: vecinas.append((i - 1, j)) if i < 2: vecinas.append((i + 1, j)) if j > 0: vecinas.append((i, j - 1)) if j < 2: vecinas.append((i, j + 1)) return vecinas # intercambia(t,p1, p2) es el tablero obtenido intercambiando en t los # elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, # >>> intercambia([[2,1,3],[8,0,4],[7,6,5]], (0,1), (1,1)) # [[2, 0, 3], [8, 1, 4], [7, 6, 5]] def intercambia(t: Tablero, p1: Posicion, p2: Posicion) -> Tablero: (i1, j1) = p1 (i2, j2) = p2 t1 = deepcopy(t) a1 = t1[i1][j1] a2 = t1[i2][j2] t1[i1][j1] = a2 t1[i2][j2] = a1 return t1 # tablerosSucesores(t) es la lista de los tablrtos sucesores del # tablero t. Por ejemplo, # >>> tablerosSucesores([[2,1,3],[8,0,4],[7,6,5]]) # [[[2, 0, 3], [8, 1, 4], [7, 6, 5]], # [[2, 1, 3], [8, 6, 4], [7, 0, 5]], # [[2, 1, 3], [0, 8, 4], [7, 6, 5]], # [[2, 1, 3], [8, 4, 0], [7, 6, 5]]] def tablerosSucesores(t: Tablero) -> list[Tablero]: p = posicionHueco(t) return [intercambia(t, p, q) for q in posicionesVecinas(p)] # (sucesores e) es la lista de sucesores del estado e. Por ejemplo, # >>> t1 = [[0,1,3],[8,2,4],[7,6,5]] # >>> es = sucesores((heuristica(t1), 1, [t1])) # >>> es # [(4, 2, [[[8, 1, 3], # [0, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (2, 2, [[[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] # >>> sucesores(es[1]) # [(0, 3, [[[1, 2, 3], # [8, 0, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (4, 3, [[[1, 3, 0], # [8, 2, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] def sucesores(e: Estado) -> list[Estado]: (_, n, ts) = e return [(heuristica(t1), n+1, [t1] + ts) for t1 in tablerosSucesores(ts[0]) if t1 not in ts] # Solución # ======== def solucion_8puzzle(t: Tablero) -> Optional[list[Tablero]]: r = buscaPM(sucesores, esFinal, inicial(t)) if r is None: return None (_, _, ts) = r ts.reverse() return ts # Verificación # ============ def test_8puzzle() -> None: assert solucion_8puzzle([[8,1,3],[0,2,4],[7,6,5]]) == \ [[[8, 1, 3], [0, 2, 4], [7, 6, 5]], [[0, 1, 3], [8, 2, 4], [7, 6, 5]], [[1, 0, 3], [8, 2, 4], [7, 6, 5]], [[1, 2, 3], [8, 0, 4], [7, 6, 5]]] # La verificación es # src> poetry run pytest -q BPM_8Puzzle.py # 1 passed in 0.10s |