{"id":8240,"date":"2023-07-03T06:00:13","date_gmt":"2023-07-03T04:00:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8240"},"modified":"2023-06-28T11:26:17","modified_gmt":"2023-06-28T09:26:17","slug":"03-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/03-jul-23\/","title":{"rendered":"El problema de las n reinas (mediante b\u00fasqueda por anchura en espacios de estados)"},"content":{"rendered":"<p>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\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal.<\/p>\n<p>Las posiciones de las reinas en el tablero se representan por su columna y su fila.<\/p>\n<pre lang=\"text\">\n   type Columna = Int\n   type Fila    = Int\n<\/pre>\n<p>Una soluci\u00f3n del problema de las n reinas es una lista de posiciones.<\/p>\n<pre lang=\"text\">\n   type SolNR = [(Columna,Fila)]\n<\/pre>\n<p>Usando el procedimiento de <a href=\"https:\/\/bit.ly\/3XBlqG7\">b\u00fasqueda en anchura<\/a>, definir las funciones<\/p>\n<pre lang=\"text\">\n   solucionesNR      :: Columna -> [SolNR]\n   primeraSolucionNR :: Columna -> SolNR\n   nSolucionesNR     :: Columna -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>solucionesNR n<\/code> es la lista de las soluciones del problema de las n reinas, por b\u00fasqueda de espacio de estados en anchura. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     take 3 (solucionesNR 8)\n     [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],\n      [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],\n      [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]\n<\/pre>\n<ul>\n<li><code>primeraSolucionNR n<\/code> es la primera soluci\u00f3n del problema de las n reinas, por b\u00fasqueda en espacio de estados por anchura. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> primeraSolucionNR 8\n     [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]\n<\/pre>\n<ul>\n<li><code>nSolucionesNR n<\/code> es el n\u00famero de soluciones del problema de las n reinas, por b\u00fasqueda en espacio de estados. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nSolucionesNR 8  ==  92\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 BEE_Reinas_Anchura where\n\nimport BusquedaEnAnchura (buscaAnchura)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Columna = Int\ntype Fila    = Int\ntype SolNR = [(Columna,Fila)]\n\n-- Los nodos del problema de las n reinas son ternas formadas por la\n-- columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n-- tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\ntype NodoNR = (Columna,Columna,SolNR)\n\nsolucionesNR :: Columna -> [SolNR]\nsolucionesNR n =\n  map estado (buscaAnchura sucesoresNR esFinalNR (1,n,[]))\n  where\n    estado (_,_,e) = e\n\nprimeraSolucionNR :: Columna -> SolNR\nprimeraSolucionNR =\n  head . solucionesNR\n\nnSolucionesNR :: Columna -> Int\nnSolucionesNR =\n  length . solucionesNR\n\n-- (valida sp p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n-- soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n-- ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n-- columnas). Por ejemplo,\n--    valida [(1,1)] (2,2)  ==  False\n--    valida [(1,1)] (2,3)  ==  True\nvalida :: SolNR -> (Columna,Fila) -> Bool\nvalida solp (c,r) = and [test s | s <- solp]\n  where test (c',r') = c'+r'\/=c+r &#038;&#038; c'-r'\/=c-r &#038;&#038; r'\/=r\n\n-- (sucesoresNR e) es la lista de los sucesores del estado e en el\n-- problema de las n reinas. Por ejemplo,\n--    \u03bb> sucesoresNR (1,4,[])\n--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\nsucesoresNR :: NodoNR -> [NodoNR]\nsucesoresNR (c,n,solp) =\n  [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]\n\n-- (esFinalNR e) se verifica si e es un estado final del problema de las\n-- n reinas.\nesFinalNR :: NodoNR -> Bool\nesFinalNR (c,n,_) = c > n\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    take 3 (solucionesNR 8) `shouldBe`\n    [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],\n     [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],\n     [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]\n  it \"e2\" $\n    nSolucionesNR 8 `shouldBe` 92\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.2116 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 src.BusquedaEnAnchura import buscaAnchura\n\nColumna = int\nFila = int\nSolNR = list[tuple[Columna, Fila]]\n\n# Los nodos del problema de las n reinas son ternas formadas por la\n# columna de la \u00faltima reina colocada, el n\u00famero de columnas del\n# tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente.\nNodoNR = tuple[Columna, Columna, SolNR]\n\n# valida(sp, p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n# soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n# ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n# columnas). Por ejemplo,\n#    valida([(1,1)], (2,2))  ==  False\n#    valida([(1,1)], (2,3))  ==  True\ndef valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:\n    c, r = p\n    def test(s: tuple[Columna, Fila]) -> bool:\n        c1, r1 = s\n        return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r\n\n    return all(test(s) for s in sp)\n\n# sucesoresNR(e) es la lista de los sucesores del estado e en el\n# problema de las n reinas. Por ejemplo,\n#    >>> sucesoresNR((1,4,[]))\n#    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\ndef sucesoresNR (nd: NodoNR) -> list[NodoNR]:\n    c,n,solp = nd\n    return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]\n\n# esFinalNR(e) se verifica si e es un estado final del problema de las\n# n reinas.\ndef esFinalNR(nd: NodoNR) -> bool:\n    c, n, _ = nd\n    return c > n\n\ndef solucionesNR(n: int) -> list[SolNR]:\n    nInicial: NodoNR = (1,n,[])\n    return [e for (_, _, e) in buscaAnchura(sucesoresNR,\n                                            esFinalNR,\n                                            nInicial)]\n\ndef primeraSolucionNR(n: int) -> SolNR:\n    return solucionesNR(n)[0]\n\ndef nSolucionesNR(n: int) -> int:\n    return len(solucionesNR(n))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_nReinas() -> None:\n    assert solucionesNR(5)[:3] == \\\n        [[(1,1),(2,3),(3,5),(4,2),(5,4)],\n         [(1,1),(2,4),(3,2),(4,5),(5,3)],\n         [(1,2),(2,4),(3,1),(4,3),(5,5)]]\n    assert nSolucionesNR(5) == 10\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_nReinas()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal. Las posiciones de las reinas en el tablero se representan por su columna y su fila. type Columna&#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\/8240"}],"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=8240"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8240\/revisions"}],"predecessor-version":[{"id":8241,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8240\/revisions\/8241"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8240"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8240"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8240"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}