{"id":2451,"date":"2016-05-17T06:44:27","date_gmt":"2016-05-17T04:44:27","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2451"},"modified":"2022-03-26T14:30:20","modified_gmt":"2022-03-26T12:30:20","slug":"problema-del-domino-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/problema-del-domino-1\/","title":{"rendered":"Problema del domin\u00f3"},"content":{"rendered":"<p>Las fichas del domin\u00f3 se pueden representar por pares de n\u00fameros enteros. El problema del domin\u00f3 consiste en colocar todas las fichas de una lista dada de forma que el segundo n\u00famero de cada ficha coincida con el primero de la siguiente.<\/p>\n<p>Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   domino :: [(Int,Int)] -> [[(Int,Int)]]\n<\/pre>\n<p>tal que (domino fs) es la lista de las soluciones del problema del domin\u00f3 correspondiente a las fichas fs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ghci> domino [(1,2),(2,3),(1,4)]\n   [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]\n   ghci> domino [(1,2),(1,1),(1,4)]\n   [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]\n   ghci> domino [(1,2),(3,4),(2,3)]\n   [[(1,2),(2,3),(3,4)]]\n   ghci> domino [(1,2),(2,3),(5,4)]\n   []\n   ghci> domino [(x,y) | x <- [1..2], y <- [x..2]]\n   [[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]\n   \u03bb> [(x,y) | x <- [1..3], y <- [x..3]]\n   [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]\n   \u03bb> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])\n   [(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]\n   [(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]\n   [(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]\n   [(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]\n   [(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]\n   [(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]\n   [(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]\n   [(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]\n   [(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]\n   ghci> length (domino [(x,y) | x <- [1..4], y <- [x..4]])\n   0\n<\/pre>\n<p>Nota: Las librer\u00edas necesarias se encuentran en la <a href=\"https:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/codigosDeTemas.php\">p\u00e1gina de c\u00f3digos<\/a>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEspaciosDeEstados (buscaEE)\nimport Data.List (delete)\n\ntype Ficha  = (Int,Int)\n\n-- Los estados son los pares formados por la listas sin colocar y las\n-- colocadas. \ntype EstadoDomino = ([Ficha],[Ficha])\n\ninicialDomino :: [Ficha] -> EstadoDomino\ninicialDomino fs = (fs,[])\n\nesFinalDomino :: EstadoDomino -> Bool\nesFinalDomino (fs,_) = null fs \n\nsucesoresDomino :: EstadoDomino -> [EstadoDomino]\nsucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs]\nsucesoresDomino (fs,n@((x,y):qs)) =\n    [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u \/= v, v == x] ++\n    [(delete (u,v) fs,(v,u):n) | (u,v) <- fs, u \/= v, u == x] ++\n    [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u == v, u == x] \n\nsolucionesDomino :: [Ficha] -> [EstadoDomino]\nsolucionesDomino ps = buscaEE sucesoresDomino\n                              esFinalDomino         \n                              (inicialDomino ps)\n\ndomino :: [(Int,Int)] -> [[(Int,Int)]]\ndomino ps = map snd (solucionesDomino ps)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Las fichas del domin\u00f3 se pueden representar por pares de n\u00fameros enteros. El problema del domin\u00f3 consiste en colocar todas las fichas de una lista dada de forma que el segundo n\u00famero de cada ficha coincida con el primero de la siguiente. Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n domino :: [(Int,Int)] ->&#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":[7],"tags":[353,8,498,25,456,10,27,11,16],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2451"}],"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=2451"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2451\/revisions"}],"predecessor-version":[{"id":2487,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2451\/revisions\/2487"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}