Espacio de estados

El problema del 8 puzzle

PorJosé A. Alonso 7-julio-20237-julio-2023

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 | 3 |                   | 1 | 2 | 3 |
   +---+---+---+                   +---+---+---+
   | 8 | 2 | 4 |                   | 8 |   | 4 |
   +---+---+---+                   +---+---+---+
   | 7 | 5 | 5 |                   | 7 | 6 | 5 |
   +---+---+---+                   +---+---+---+
   Estado inicial                  Estado final

+---+---+---+ +---+---+---+

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

Tablero es una matriz de número enteros (que representan las piezas en
cada posición y el 0 representa el hueco):

     type Tablero  = Matrix Int

1	type Tablero = Matrix Int

Estado es una listas de tableros [t_n,…,t_1] tal que t_i es un
sucesor de t_(i-1).

     newtype Estado = Est [Tablero]
       deriving Show

1 2	newtype Estado = Est [Tablero] deriving Show

Usando el procedimiento de búsqueda por primero el mejor, definir la función

   solucion_8puzzle :: Tablero -> [Tablero]

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,

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

λ> 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]]))

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

Búsqueda por primero el mejor

PorJosé A. Alonso 6-julio-20237-julio-2023

En la búsqueda por primero el mejor se supone que los estados están ordenados mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.

Definir la función

   buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

1	buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

tal que buscaPM 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 buscando por primero el mejor.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module BusquedaPrimeroElMejor (buscaPM)  where

import TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia)

buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]
buscaPM sucesores esFinal x = busca' (inserta x vacia) where
  busca' c
    | esVacia c = []
    | esFinal (primero c) = primero c : busca' (resto c)
    | otherwise = busca' (foldr inserta (resto c) (sucesores (primero c)))

module BusquedaPrimeroElMejor (buscaPM) where

import TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia)

buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

buscaPM sucesores esFinal x = busca' (inserta x vacia) where

busca' c

| esVacia c = []

| esFinal (primero c) = primero c : busca' (resto c)

| otherwise = busca' (foldr inserta (resto c) (sucesores (primero c)))

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from functools import reduce
from typing import Callable, Optional, Protocol, TypeVar

from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,
                                     resto, vacia)


class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def buscaPM(sucesores: Callable[[A], list[A]],
            esFinal: Callable[[A], bool],
            inicial: A) -> Optional[A]:
    c: CPrioridad[A] = inserta(inicial, vacia())

    while not esVacia(c):
        if esFinal(primero(c)):
            return primero(c)

        es = sucesores(primero(c))
        c = reduce(lambda x, y: inserta(y, x), es, resto(c))

    return None

from __future__ import annotations

from abc import abstractmethod

from functools import reduce

from typing import Callable, Optional, Protocol, TypeVar

from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,

resto, vacia)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def buscaPM(sucesores: Callable[[A], list[A]],

esFinal: Callable[[A], bool],

inicial: A) -> Optional[A]:

c: CPrioridad[A] = inserta(inicial, vacia())

while not esVacia(c):

if esFinal(primero(c)):

return primero(c)

es = sucesores(primero(c))

c = reduce(lambda x, y: inserta(y, x), es, resto(c))

return None

El problema de la mochila (mediante espacio de estados)

PorJosé A. Alonso 4-julio-20231-julio-2023

Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.

Para solucionar el problema se definen los siguientes tipos:

Una solución del problema de la mochila es una lista de objetos.

     type SolMoch = [Objeto]

1	type SolMoch = [Objeto]

Los objetos son pares formado por un peso y un valor

     type Objeto = (Peso,Valor)

1	type Objeto = (Peso,Valor)

Los pesos son número enteros

     type Peso = Int

1	type Peso = Int

Los valores son números reales.

     type Valor = Float

1	type Valor = Float

Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.

     type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

1	type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

Usando el procedimiento de búsqueda en profundidad, definir la función

   mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

1	mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,

   > mochila [(2,3),(3,5),(4,6),(5,10)] 8
   ([(5,10.0),(3,5.0)],15.0)
   > mochila [(2,3),(3,5),(5,6)] 10
   ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
   > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35
   ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)
   > mochila [(2,2.8),(3,4.4),(5,6.1)] 10
   ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

> mochila [(2,3),(3,5),(4,6),(5,10)] 8

([(5,10.0),(3,5.0)],15.0)

> mochila [(2,3),(3,5),(5,6)] 10

([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

> mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35

([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)

> mochila [(2,2.8),(3,4.4),(5,6.1)] 10

([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module BEE_Mochila where

import BusquedaEnProfundidad (buscaProfundidad)
import Data.List (sort)
import Test.Hspec (Spec, hspec, it, shouldBe)

type Peso     = Int
type Valor    = Float
type Objeto   = (Peso,Valor)
type SolMoch  = [Objeto]
type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

mochila :: [Objeto] -> Peso -> (SolMoch,Valor)
mochila os l = (sol,v)
  where
    (v,_,_,_,sol) =
      maximum (buscaProfundidad sucesoresMoch
                                esObjetivoMoch
                                (inicial os l))

-- (inicial os l) es el estado inicial del problema de la mochila
-- para la lista de objetos os y el límite de capacidad l
inicial :: [Objeto] -> Peso -> NodoMoch
inicial os l =
  (0,0,l,sort os,[])

-- (sucesoresMoch e) es la lista de los sucesores del estado e en el
-- problema de la mochila para la lista de objetos os y el límite de
-- capacidad l.
sucesoresMoch :: NodoMoch -> [NodoMoch]
sucesoresMoch (v,p,l,os,solp) =
  [( v+v',
     p+p',
     l,
     [o | o@(p'',_) <- os, p''>=p'],
     (p',v'):solp )
  | (p',v') <- os,
    p+p' <= l]

-- (esObjetivoMoch e) se verifica si e es un estado final el problema de
-- la mochila para la lista de objetos os y el límite de capacidad l .
esObjetivoMoch :: NodoMoch -> Bool
esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    mochila [(2,3),(3,5),(4,6),(5,10)] 8
    `shouldBe` ([(5,10.0),(3,5.0)],15.0)
  it "e2" $
    mochila [(2,3),(3,5),(5,6)] 10
    `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
  it "e3" $
    mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35
    `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)
  it "e4" $
    mochila [(2,2.8),(3,4.4),(5,6.1)] 10
    `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0424 seconds
--    4 examples, 0 failures

module BEE_Mochila where

import BusquedaEnProfundidad (buscaProfundidad)

import Data.List (sort)

import Test.Hspec (Spec, hspec, it, shouldBe)

type Peso = Int

type Valor = Float

type Objeto = (Peso,Valor)

type SolMoch = [Objeto]

type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

mochila os l = (sol,v)

where

(v,_,_,_,sol) =

maximum (buscaProfundidad sucesoresMoch

esObjetivoMoch

(inicial os l))

-- (inicial os l) es el estado inicial del problema de la mochila

-- para la lista de objetos os y el límite de capacidad l

inicial :: [Objeto] -> Peso -> NodoMoch

inicial os l =

(0,0,l,sort os,[])

-- (sucesoresMoch e) es la lista de los sucesores del estado e en el

-- problema de la mochila para la lista de objetos os y el límite de

-- capacidad l.

sucesoresMoch :: NodoMoch -> [NodoMoch]

sucesoresMoch (v,p,l,os,solp) =

[( v+v',

p+p',

[o | o@(p'',_) <- os, p''>=p'],

(p',v'):solp )

| (p',v') <- os,

p+p' <= l]

-- (esObjetivoMoch e) se verifica si e es un estado final el problema de

-- la mochila para la lista de objetos os y el límite de capacidad l .

esObjetivoMoch :: NodoMoch -> Bool

esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

mochila [(2,3),(3,5),(4,6),(5,10)] 8

`shouldBe` ([(5,10.0),(3,5.0)],15.0)

it "e2" $

mochila [(2,3),(3,5),(5,6)] 10

`shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

it "e3" $

mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35

`shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)

it "e4" $

mochila [(2,2.8),(3,4.4),(5,6.1)] 10

`shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0424 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad

Peso = int
Valor = float
Objeto = tuple[Peso, Valor]
SolMoch = list[Objeto]
NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]

# inicial(os, l) es el estado inicial del problema de la mochila
# para la lista de objetos os y el límite de capacidad l
def inicial(os: list[Objeto], l: Peso) -> NodoMoch:
    return (0,0,l,sorted(os),[])

# sucesoresMoch(e) es la lista de los sucesores del estado e en el
# problema de la mochila para la lista de objetos os y el límite de
# capacidad l.
def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:
    (v,p,l,os,solp) = n
    return [( v+v1,
              p+p1,
              l,
              [(p2,v2) for (p2,v2) in os if p2 >= p1],
              [(p1,v1)] + solp )
            for (p1,v1) in os if p + p1 <= l]

# esObjetivoMoch(e) se verifica si e es un estado final el problema de
# la mochila para la lista de objetos os y el límite de capacidad l .
def esObjetivoMoch(e: NodoMoch) -> bool:
    (_, p, l, os, _) = e
    (p_, _) = os[0]
    return p + p_ > l

def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:
    (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,
                                         esObjetivoMoch,
                                         inicial(os, l)))
    return (sol, v)

# Verificación
# ============

def test_Mochila() -> None:
    assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \
        ([(5,10.0),(3,5.0)],15.0)
    assert mochila([(2,3),(3,5),(5,6)], 10) == \
        ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
    assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \
        ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)
    print("Verificado")

# La verificación es
#    >>> test_Mochila()
#    Verificado

from src.BusquedaEnProfundidad import buscaProfundidad

Peso = int

Valor = float

Objeto = tuple[Peso, Valor]

SolMoch = list[Objeto]

NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]

# inicial(os, l) es el estado inicial del problema de la mochila

# para la lista de objetos os y el límite de capacidad l

def inicial(os: list[Objeto], l: Peso) -> NodoMoch:

return (0,0,l,sorted(os),[])

# sucesoresMoch(e) es la lista de los sucesores del estado e en el

# problema de la mochila para la lista de objetos os y el límite de

# capacidad l.

def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:

(v,p,l,os,solp) = n

return [( v+v1,

p+p1,

[(p2,v2) for (p2,v2) in os if p2 >= p1],

[(p1,v1)] + solp )

for (p1,v1) in os if p + p1 <= l]

# esObjetivoMoch(e) se verifica si e es un estado final el problema de

# la mochila para la lista de objetos os y el límite de capacidad l .

def esObjetivoMoch(e: NodoMoch) -> bool:

(_, p, l, os, _) = e

(p_, _) = os[0]

return p + p_ > l

def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:

(v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,

esObjetivoMoch,

inicial(os, l)))

return (sol, v)

# Verificación

# ============

def test_Mochila() -> None:

assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \

([(5,10.0),(3,5.0)],15.0)

assert mochila([(2,3),(3,5),(5,6)], 10) == \

([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \

([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

print("Verificado")

# La verificación es

# >>> test_Mochila()

# Verificado

El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)

PorJosé A. Alonso 3-julio-202328-junio-2023

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.

   type Columna = Int
   type Fila    = Int

1 2	type Columna = Int type Fila = Int

Una solución del problema de las n reinas es una lista de posiciones.

   type SolNR = [(Columna,Fila)]

1	type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en anchura, definir las funciones

   solucionesNR      :: Columna -> [SolNR]
   primeraSolucionNR :: Columna -> SolNR
   nSolucionesNR     :: Columna -> Int

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 anchura. Por ejemplo,

     take 3 (solucionesNR 8)
     [[(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)]]

take 3 (solucionesNR 8)

[[(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)]]

primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,

     λ> primeraSolucionNR 8
     [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]

1 2	λ> primeraSolucionNR 8 [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]

nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

     nSolucionesNR 8  ==  92

1	nSolucionesNR 8 == 92

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module BEE_Reinas_Anchura where

import BusquedaEnAnchura (buscaAnchura)
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 (buscaAnchura 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,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)]]
  it "e2" $
    nSolucionesNR 8 `shouldBe` 92

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.2116 seconds
--    2 examples, 0 failures

module BEE_Reinas_Anchura where

import BusquedaEnAnchura (buscaAnchura)

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 (buscaAnchura 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,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)]]

it "e2" $

nSolucionesNR 8 `shouldBe` 92

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.2116 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.BusquedaEnAnchura import buscaAnchura

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 buscaAnchura(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(5)[:3] == \
        [[(1,1),(2,3),(3,5),(4,2),(5,4)],
         [(1,1),(2,4),(3,2),(4,5),(5,3)],
         [(1,2),(2,4),(3,1),(4,3),(5,5)]]
    assert nSolucionesNR(5) == 10
    print("Verificado")

# La verificación es
#    >>> test_nReinas()
#    Verificado

from src.BusquedaEnAnchura import buscaAnchura

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 buscaAnchura(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(5)[:3] == \

[[(1,1),(2,3),(3,5),(4,2),(5,4)],

[(1,1),(2,4),(3,2),(4,5),(5,3)],

[(1,2),(2,4),(3,1),(4,3),(5,5)]]

assert nSolucionesNR(5) == 10

print("Verificado")

# La verificación es

# >>> test_nReinas()

# Verificado

Búsqueda por anchura en espacios de estados

PorJosé A. Alonso 30-junio-202328-junio-2023

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

   buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                              -> nodo -> [nodo]

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.

Soluciones en Haskell

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

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

Soluciones en Python

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()))

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()))

El problema del 8 puzzle

Búsqueda por primero el mejor

El problema de la mochila (mediante espacio de estados)

El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)

Búsqueda por anchura en espacios de estados

Entradas recientes

Buscar

Correo electrónico