{"id":8251,"date":"2023-07-07T06:00:44","date_gmt":"2023-07-07T04:00:44","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8251"},"modified":"2023-07-07T11:10:39","modified_gmt":"2023-07-07T09:10:39","slug":"07-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/07-jul-23\/","title":{"rendered":"El problema del 8 puzzle"},"content":{"rendered":"<p>Para el 8-puzzle se usa un caj\u00f3n cuadrado en el que hay situados  bloques cuadrados. El cuadrado restante est\u00e1 sin rellenar. Cada bloque tiene un n\u00famero. Un bloque adyacente al hueco puede deslizarse hacia \u00e9l. El juego consiste en transformar la posici\u00f3n inicial en la posici\u00f3n final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:<\/p>\n<pre lang=\"text\">\n   +---+---+---+                   +---+---+---+\n   |   | 1 | 3 |                   | 1 | 2 | 3 |\n   +---+---+---+                   +---+---+---+\n   | 8 | 2 | 4 |                   | 8 |   | 4 |\n   +---+---+---+                   +---+---+---+\n   | 7 | 5 | 5 |                   | 7 | 6 | 5 |\n   +---+---+---+                   +---+---+---+\n   Estado inicial                  Estado final\n<\/pre>\n<p>Para solucionar el problema se definen los siguientes tipos:<\/p>\n<ul>\n<li><code>Tablero<\/code> es una matriz de n\u00famero enteros (que representan las piezas en<br \/>\ncada posici\u00f3n y el 0 representa el hueco):<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Tablero  = Matrix Int\n<\/pre>\n<ul>\n<li><code>Estado<\/code> es una listas de tableros [t_n,&#8230;,t_1] tal que t_i es un<br \/>\nsucesor de t_(i-1).<\/li>\n<\/ul>\n<pre lang=\"text\">\n     newtype Estado = Est [Tablero]\n       deriving Show\n<\/pre>\n<p>Usando el procedimiento de <a href=\"???\">b\u00fasqueda por primero el mejor<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   solucion_8puzzle :: Tablero -> [Tablero]\n<\/pre>\n<p>tal que <code>(solucion_8puzzle t)<\/code> es la soluci\u00f3n del problema del problema del 8 puzzle a partir del tablero <code>t<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])\n   [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n    \u2502 0 1 3 \u2502  \u2502 1 0 3 \u2502  \u2502 1 2 3 \u2502\n    \u2502 8 2 4 \u2502  \u2502 8 2 4 \u2502  \u2502 8 0 4 \u2502\n    \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n    \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\n   \u03bb> length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]]))\n   21\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 BPM_8Puzzle where\n\nimport BusquedaPrimeroElMejor (buscaPM)\nimport Data.Matrix (Matrix, (!), fromLists, setElem, toLists)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Tablero  = Matrix Int\n\nnewtype Estado = Est [Tablero]\n  deriving (Eq, Show)\n\nsolucion_8puzzle :: Tablero -> [Tablero]\nsolucion_8puzzle t = reverse ts\n  where (Est ts) = head (buscaPM sucesores\n                                 esFinal\n                                 (inicial t))\n\n-- Estado inicial\n-- ==============\n\n-- (inicial t) es el estado inicial del problema del 8 puzzle a partir del\n-- tablero t.\ninicial :: Tablero -> Estado\ninicial t = Est [t]\n\n-- Estado final\n-- ============\n\n-- (esFinal e) se verifica si e es un estado final.\nesFinal :: Estado -> Bool\nesFinal (Est (n:_)) = n == tableroFinal\n\n-- tableroFinal es el estado tablero final del 8 puzzle.\ntableroFinal :: Tablero\ntableroFinal = fromLists [[1,2,3],\n                          [8,0,4],\n                          [7,6,5]]\n\n-- Sucesores\n-- =========\n\n-- (sucesores e) es la lista de sucesores del estado e. Por ejemplo,\n--    \u03bb> sucesores (Est [fromLists [[2,1,3],[8,0,4],[7,6,5]]])\n--    [Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 0 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 1 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 6 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 0 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 0 8 4 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518],\n--     Est [\u250c       \u2510  \u250c       \u2510\n--          \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--          \u2502 8 4 0 \u2502  \u2502 8 0 4 \u2502\n--          \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--          \u2514       \u2518, \u2514       \u2518]]\nsucesores :: Estado -> [Estado]\nsucesores (Est e@(t:_)) =\n  [Est (t':e) | t' <- tablerosSucesores t,\n                t' `notElem` e]\n\n-- (tablerosSucesores t) es la lista de los tableros sucesores del\n-- tablero t. Por ejemplo,\n--    \u03bb> tablerosSucesores (fromLists [[2,1,3],[8,0,4],[7,6,5]])\n--    [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n--     \u2502 2 0 3 \u2502  \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502  \u2502 2 1 3 \u2502\n--     \u2502 8 1 4 \u2502  \u2502 8 6 4 \u2502  \u2502 0 8 4 \u2502  \u2502 8 4 0 \u2502\n--     \u2502 7 6 5 \u2502  \u2502 7 0 5 \u2502  \u2502 7 6 5 \u2502  \u2502 7 6 5 \u2502\n--     \u2514       \u2518, \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\ntablerosSucesores :: Tablero -> [Tablero]\ntablerosSucesores t =\n  [intercambia t p q | q <- posicionesVecinas p]\n  where p = posicionHueco t\n\n-- Una posici\u00f3n es un par de enteros.\ntype Posicion = (Int,Int)\n\n-- (posicionesVecinas p) son las posiciones de la matriz cuadrada de\n-- dimensi\u00f3n 3 que se encuentran encima, abajo, a la izquierda y a la\n-- derecha de los posici\u00f3n p. Por ejemplo,\n--    \u03bb> posicionesVecinas (2,2)\n--    [(1,2),(3,2),(2,1),(2,3)]\n--    \u03bb> posicionesVecinas (1,2)\n--    [(2,2),(1,1),(1,3)]\n--    \u03bb> posicionesVecinas (1,1)\n--    [(2,1),(1,2)]\nposicionesVecinas :: Posicion -> [Posicion]\nposicionesVecinas (i,j) =\n  [(i-1,j) | i > 1] ++\n  [(i+1,j) | i < 3] ++\n  [(i,j-1) | j > 1] ++\n  [(i,j+1) | j < 3]\n\n-- (posicionHueco t) es la posici\u00f3n del hueco en el tablero t. Por\n-- ejemplo,\n--    \u03bb> posicionHueco (fromLists [[2,1,3],[8,0,4],[7,6,5]])\n--    (2,2)\nposicionHueco :: Tablero -> Posicion\nposicionHueco t =\n  posicionElemento t 0\n\n-- (posicionElemento t a) es la posici\u00f3n de elemento a en el tablero\n-- t. Por ejemplo,\n--    \u03bb> posicionElemento (fromLists [[2,1,3],[8,0,4],[7,6,5]]) 4\n--    (2,3)\nposicionElemento :: Tablero -> Int -> Posicion\nposicionElemento t a =\n  head [(i,j) | i <- [1..3],\n                j <- [1..3],\n                t ! (i,j) == a]\n\n-- (intercambia t p1 p2) es el tablero obtenido intercambiando en t los\n-- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo,\n--    \u03bb> intercambia (fromLists [[2,1,3],[8,0,4],[7,6,5]]) (1,2) (2,2)\n--    \u250c       \u2510\n--    \u2502 2 0 3 \u2502\n--    \u2502 8 1 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\nintercambia :: Tablero -> Posicion -> Posicion -> Tablero\nintercambia t p1 p2 =\n  setElem a2 p1 (setElem a1 p2 t)\n  where a1 = t ! p1\n        a2 = t ! p2\n\n-- Heur\u00edstica\n-- ==========\n\n-- (heuristica t) es la suma de la distancia Manhatan desde la posici\u00f3n de\n-- cada objeto del tablero a su posici\u00f3n en el tablero final. Por\n-- ejemplo,\n--    \u03bb> heuristica (fromLists [[0,1,3],[8,2,4],[7,6,5]])\n--    4\nheuristica :: Tablero  -> Int\nheuristica t =\n  sum [distancia (posicionElemento t i)\n                 (posicionElemento tableroFinal i)\n      | i <- [0..8]]\n\n-- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y\n-- p2. Por ejemplo,\n--    distancia (2,7) (4,1)  ==  8\ndistancia :: Posicion -> Posicion -> Int\ndistancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2)\n\n-- Comparaci\u00f3n de estados\n-- ======================\n\n-- Un estado es menor o igual que otro si tiene la heur\u00edstica de su\n-- primer tablero es menor o que la del segundo o so iguales y el\n-- primero es m\u00e1s corto.\ninstance Ord Estado where\n  Est (t1:ts1) <= Est (t2:ts2) = (heuristica t1 < heuristica t2) ||\n                                 ((heuristica t1 == heuristica t2) &#038;&#038;\n                                  (length ts1 <= length ts2))\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    map toLists (solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]]))\n   `shouldBe` [[[0,1,3],\n                [8,2,4],\n                [7,6,5]],\n               [[1,0,3],\n                [8,2,4],\n                [7,6,5]],\n               [[1,2,3],\n                [8,0,4],\n                [7,6,5]]]\n  it \"e2\" $\n    length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]]))\n    `shouldBe` 21\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.1361 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 copy import deepcopy\nfrom typing import Optional\n\nfrom src.BusquedaPrimeroElMejor import buscaPM\n\nTablero = list[list[int]]\n\n# Tablero final\n# =============\n\n# tableroFinal es el tablero final del 8 puzzle.\ntableroFinal: Tablero = [[1,2,3],\n                         [8,0,4],\n                         [7,6,5]]\n\n# Posiciones\n# ==========\n\n# Una posici\u00f3n es un par de enteros.\nPosicion = tuple[int,int]\n\n# Heur\u00edstica\n# ==========\n\n# distancia(p1, p2) es la distancia Manhatan entre las posiciones p1 y\n# p2. Por ejemplo,\n#    >>> distancia((2,7), (4,1))\n#    8\ndef distancia(p1: Posicion, p2: Posicion) -> int:\n    (x1, y1) = p1\n    (x2, y2) = p2\n    return abs(x1-x2) + abs (y1-y2)\n\n# posicionElemento(t, a) es la posici\u00f3n de elemento a en el tablero\n# t. Por ejemplo,\n#    \u03bb> posicionElemento([[2,1,3],[8,0,4],[7,6,5]], 4)\n#    (1, 2)\ndef posicionElemento(t: Tablero, a: int) -> Posicion:\n    for i in range(0, 3):\n        for j in range(0, 3):\n            if t[i][j] == a:\n                return (i, j)\n    return (4, 4)\n\n# posicionHueco(t) es la posici\u00f3n del hueco en el tablero t. Por\n# ejemplo,\n#    >>> posicionHueco([[2,1,3],[8,0,4],[7,6,5]])\n#    (1, 1)\ndef posicionHueco(t: Tablero) -> Posicion:\n    return posicionElemento(t, 0)\n\n# heuristica(t) es la suma de la distancia Manhatan desde la posici\u00f3n de\n# cada objeto del tablero a su posici\u00f3n en el tablero final. Por\n# ejemplo,\n#    >>> heuristica([[0,1,3],[8,2,4],[7,6,5]])\n#    4\ndef heuristica(t: Tablero) -> int:\n    return sum((distancia(posicionElemento(t, i),\n                          posicionElemento(tableroFinal, i))\n                for i in range(0, 10)))\n\n# Estados\n# =======\n\n# Un estado es una tupla (h, n, ts), donde ts es una listas de tableros\n# [t_n,...,t_1] tal que t_i es un sucesor de t_(i-1) y h es la\n# heur\u00edstica de t_n.\nEstado = tuple[int, int, list[Tablero]]\n\n# Estado inicial\n# ==============\n\n# inicial(t) es el estado inicial del problema del 8 puzzle a partir del\n# tablero t.\ndef inicial(t: Tablero) -> Estado:\n    return (heuristica(t), 1, [t])\n\n# Estado final\n# ============\n\n# esFinal(e) se verifica si e es un estado final.\ndef esFinal(e: Estado) -> bool:\n    (_, _, ts) = e\n    return ts[0] == tableroFinal\n\n# Sucesores\n# =========\n\n# posicionesVecinas(p) son las posiciones de la matriz cuadrada de\n# dimensi\u00f3n 3 que se encuentran encima, abajo, a la izquierda y a la\n# derecha de los posici\u00f3n p. Por ejemplo,\n#    >>> posicionesVecinas((1,1))\n#    [(0, 1), (2, 1), (1, 0), (1, 2)]\n#    >>> posicionesVecinas((0,1))\n#    [(1, 1), (0, 0), (0, 2)]\n#    >>> posicionesVecinas((0,0))\n#    [(1, 0), (0, 1)]\ndef posicionesVecinas(p: Posicion) -> list[Posicion]:\n    (i, j) = p\n    vecinas = []\n    if i > 0:\n        vecinas.append((i - 1, j))\n    if i < 2:\n        vecinas.append((i + 1, j))\n    if j > 0:\n        vecinas.append((i, j - 1))\n    if j < 2:\n        vecinas.append((i, j + 1))\n    return vecinas\n\n# intercambia(t,p1, p2) es el tablero obtenido intercambiando en t los\n# elementos que se encuentran en las posiciones p1 y p2. Por ejemplo,\n#    >>> intercambia([[2,1,3],[8,0,4],[7,6,5]], (0,1), (1,1))\n#    [[2, 0, 3], [8, 1, 4], [7, 6, 5]]\ndef intercambia(t: Tablero, p1: Posicion, p2: Posicion) -> Tablero:\n    (i1, j1) = p1\n    (i2, j2) = p2\n    t1 = deepcopy(t)\n    a1 = t1[i1][j1]\n    a2 = t1[i2][j2]\n    t1[i1][j1] = a2\n    t1[i2][j2] = a1\n    return t1\n\n# tablerosSucesores(t) es la lista de los tablrtos sucesores del\n# tablero t. Por ejemplo,\n#    >>> tablerosSucesores([[2,1,3],[8,0,4],[7,6,5]])\n#    [[[2, 0, 3], [8, 1, 4], [7, 6, 5]],\n#     [[2, 1, 3], [8, 6, 4], [7, 0, 5]],\n#     [[2, 1, 3], [0, 8, 4], [7, 6, 5]],\n#     [[2, 1, 3], [8, 4, 0], [7, 6, 5]]]\ndef tablerosSucesores(t: Tablero) -> list[Tablero]:\n    p = posicionHueco(t)\n    return [intercambia(t, p, q) for q in posicionesVecinas(p)]\n\n# (sucesores e) es la lista de sucesores del estado e. Por ejemplo,\n#    >>> t1 = [[0,1,3],[8,2,4],[7,6,5]]\n#    >>> es = sucesores((heuristica(t1), 1, [t1]))\n#    >>> es\n#    [(4, 2, [[[8, 1, 3],\n#              [0, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]]),\n#     (2, 2, [[[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]])]\n#    >>> sucesores(es[1])\n#    [(0, 3, [[[1, 2, 3],\n#              [8, 0, 4],\n#              [7, 6, 5]],\n#             [[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]]),\n#     (4, 3, [[[1, 3, 0],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[1, 0, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]],\n#             [[0, 1, 3],\n#              [8, 2, 4],\n#              [7, 6, 5]]])]\ndef sucesores(e: Estado) -> list[Estado]:\n    (_, n, ts) = e\n    return [(heuristica(t1), n+1, [t1] + ts)\n            for t1 in tablerosSucesores(ts[0])\n            if t1 not in ts]\n\n# Soluci\u00f3n\n# ========\n\ndef solucion_8puzzle(t: Tablero) -> Optional[list[Tablero]]:\n    r = buscaPM(sucesores, esFinal, inicial(t))\n    if r is None:\n        return None\n    (_, _, ts) = r\n    ts.reverse()\n    return ts\n\n# Verificaci\u00f3n\n# ============\n\ndef test_8puzzle() -> None:\n    assert solucion_8puzzle([[8,1,3],[0,2,4],[7,6,5]]) == \\\n        [[[8, 1, 3], [0, 2, 4], [7, 6, 5]],\n         [[0, 1, 3], [8, 2, 4], [7, 6, 5]],\n         [[1, 0, 3], [8, 2, 4], [7, 6, 5]],\n         [[1, 2, 3], [8, 0, 4], [7, 6, 5]]]\n\n# La verificaci\u00f3n es\n#    src> poetry run pytest -q BPM_8Puzzle.py\n#    1 passed in 0.10s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Para el 8-puzzle se usa un caj\u00f3n cuadrado en el que hay situados bloques cuadrados. El cuadrado restante est\u00e1 sin rellenar. Cada bloque tiene un n\u00famero. Un bloque adyacente al hueco puede deslizarse hacia \u00e9l. El juego consiste en transformar la posici\u00f3n inicial en la posici\u00f3n final mediante el deslizamiento de los bloques. En particular,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[581],"tags":[456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8251"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8251"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8251\/revisions"}],"predecessor-version":[{"id":8252,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8251\/revisions\/8252"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8251"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8251"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}