El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)
El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.
Las posiciones de las reinas en el tablero se representan por su columna y su fila.
|
1 2 |
type Columna = Int type Fila = Int |
Una solución del problema de las n reinas es una lista de posiciones.
|
1 |
type SolNR = [(Columna,Fila)] |
Usando el procedimiento de búsqueda en profundidad, definir las funciones
|
1 2 3 |
solucionesNR :: Columna -> [SolNR] primeraSolucionNR :: Columna -> SolNR nSolucionesNR :: Columna -> Int |
tales que
solucionesNR nes la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en profundidad. Por ejemplo,
|
1 2 3 4 |
take 3 (solucionesNR 8) [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)], [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)], [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]] |
primeraSolucionNR nes la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,
|
1 2 |
λ> primeraSolucionNR 8 [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)] |
nSolucionesNR nes el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,
|
1 |
nSolucionesNR 8 == 92 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
module BEE_Reinas_Profundidad where import BusquedaEnProfundidad (buscaProfundidad) import Test.Hspec (Spec, hspec, it, shouldBe) type Columna = Int type Fila = Int type SolNR = [(Columna,Fila)] -- Los nodos del problema de las n reinas son ternas formadas por la -- columna de la última reina colocada, el número de columnas del -- tablero y la solución parcial de las reinas colocadas anteriormente. type NodoNR = (Columna,Columna,SolNR) solucionesNR :: Columna -> [SolNR] solucionesNR n = map estado (buscaProfundidad sucesoresNR esFinalNR (1,n,[])) where estado (_,_,e) = e primeraSolucionNR :: Columna -> SolNR primeraSolucionNR = head . solucionesNR nSolucionesNR :: Columna -> Int nSolucionesNR = length . solucionesNR -- (valida sp p) se verifica si la posición p es válida respecto de la -- solución parcial sp; es decir, la reina en la posición p no amenaza a -- ninguna de las reinas de la sp (se supone que están en distintas -- columnas). Por ejemplo, -- valida [(1,1)] (2,2) == False -- valida [(1,1)] (2,3) == True valida :: SolNR -> (Columna,Fila) -> Bool valida solp (c,r) = and [test s | s <- solp] where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r -- (sucesoresNR e) es la lista de los sucesores del estado e en el -- problema de las n reinas. Por ejemplo, -- λ> sucesoresNR (1,4,[]) -- [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] sucesoresNR :: NodoNR -> [NodoNR] sucesoresNR (c,n,solp) = [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)] -- (esFinalNR e) se verifica si e es un estado final del problema de las -- n reinas. esFinalNR :: NodoNR -> Bool esFinalNR (c,n,_) = c > n -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ take 3 (solucionesNR 8) `shouldBe` [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)], [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)], [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]] it "e2" $ nSolucionesNR 8 `shouldBe` 92 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.1173 seconds -- 2 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from src.BusquedaEnProfundidad import buscaProfundidad Columna = int Fila = int SolNR = list[tuple[Columna, Fila]] # Los nodos del problema de las n reinas son ternas formadas por la # columna de la última reina colocada, el número de columnas del # tablero y la solución parcial de las reinas colocadas anteriormente. NodoNR = tuple[Columna, Columna, SolNR] # valida(sp, p) se verifica si la posición p es válida respecto de la # solución parcial sp; es decir, la reina en la posición p no amenaza a # ninguna de las reinas de la sp (se supone que están en distintas # columnas). Por ejemplo, # valida([(1,1)], (2,2)) == False # valida([(1,1)], (2,3)) == True def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool: c, r = p def test(s: tuple[Columna, Fila]) -> bool: c1, r1 = s return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r return all(test(s) for s in sp) # sucesoresNR(e) es la lista de los sucesores del estado e en el # problema de las n reinas. Por ejemplo, # >>> sucesoresNR((1,4,[])) # [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] def sucesoresNR (nd: NodoNR) -> list[NodoNR]: c,n,solp = nd return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))] # esFinalNR(e) se verifica si e es un estado final del problema de las # n reinas. def esFinalNR(nd: NodoNR) -> bool: c, n, _ = nd return c > n def solucionesNR(n: int) -> list[SolNR]: nInicial: NodoNR = (1,n,[]) return [e for (_, _, e) in buscaProfundidad(sucesoresNR, esFinalNR, nInicial)] def primeraSolucionNR(n: int) -> SolNR: return solucionesNR(n)[0] def nSolucionesNR(n: int) -> int: return len(solucionesNR(n)) # Verificación # ============ def test_nReinas() -> None: assert solucionesNR(8)[:3] == \ [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)], [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)], [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]] assert nSolucionesNR(8) == 92 print("Verificado") # La verificación es # >>> test_nReinas() # Verificado |