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:
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
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