{"id":6671,"date":"2019-05-17T12:20:41","date_gmt":"2019-05-17T10:20:41","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6671"},"modified":"2019-05-17T12:20:41","modified_gmt":"2019-05-17T10:20:41","slug":"i1m2018-el-rompecabeza-del-triomino-mediante-divide-y-venceras","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-el-rompecabeza-del-triomino-mediante-divide-y-venceras\/","title":{"rendered":"I1M2018: El rompecabeza del triomin\u00f3 mediante divide y vencer\u00e1s"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han resuelto ejercicios de la relaci\u00f3n 41 sobre la soluci\u00f3n del problema del triomin\u00f3 mediante divide y vencer\u00e1s.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\n-- Un poliomin\u00f3 es una figura geom\u00e9trica plana formada conectando dos o\n-- m\u00e1s cuadrados por alguno de sus lados. Los cuadrados se conectan lado\n-- con lado, pero no se pueden conectar ni por sus v\u00e9rtices, ni juntando\n-- solo parte de un lado de un cuadrado con parte de un lado de otro. Si\n-- unimos dos cuadrados se obtiene un domin\u00f3, si se juntan tres\n-- cuadrados se construye un triomin\u00f3.  \n--\n-- S\u00f3lo existen dos triomin\u00f3s, el I-triomino (por tener forma de I) y el\n-- L-triomin\u00f3 (por su forma de L) como se observa en la siguiente figura \n--\n--    X   \n---   X     X\n--    X     XX\n--   \n-- El rompecabeza del triomin\u00f3 consiste en cubrir un tablero cuadrado\n-- con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla,\n-- con L-triomin\u00f3s de formas que cubran todas las casillas excepto la\n-- eliminada y los triomin\u00f3s no se solapen.\n--\n-- La casilla eliminada se representar\u00e1 con -1 y los L-triomin\u00f3s con\n-- sucesiones de tres n\u00fameros consecutivos en forma de L. Con esta\n-- representaci\u00f3n una soluci\u00f3n del rompecabeza del triomin\u00f3 con 4 filas\n-- y la fila eliminada en la posici\u00f3n (4,4) es\n--    (  3  3  2  2 )\n--    (  3  1  1  2 )\n--    (  4  1  5  5 )\n--    (  4  4  5 -1 )\n--\n-- En esta relaci\u00f3n resolveremos el rompecabeza del triomin\u00f3 mediante\n-- divide y vencer\u00e1s, utilizando las implementaciones estudiadas en el\n-- tema 23 que se pueden descargar desde  \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\/codigos\n--\n-- Las transparencias del tema 23 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\/temas\/tema-23.pdf\n--\n-- La t\u00e9cnica \"divide y vencer\u00e1s\" consta de los siguientes pasos:\n-- 1. Dividir el problema en subproblemas menores.\n-- 2. Resolver por separado cada uno de los subproblemas; si los\n--    subproblemas son complejos, usar la misma t\u00e9cnica recursivamente;\n--    si son simples, resolverlos directamente.\n-- 3. Combinar todas las soluciones de los subproblemas en una soluci\u00f3n\n--    simple. \n-- \n-- Con (divideVenceras ind resuelve divide combina pbInicial) se\n-- resuelve el problema pbInicial mediante la t\u00e9cnica de divide y\n-- vencer\u00e1s, donde \n-- * (ind pb) se verifica si el problema pb es indivisible \n-- * (resuelve pb) es la soluci\u00f3n del problema indivisible pb\n-- * (divide pb) es la lista de subproblemas de pb\n-- * (combina pb ss) es la combinaci\u00f3n de las soluciones ss de los\n--      subproblemas del problema pb.\n-- * pbInicial es el problema inicial\n--\n-- En los distintos apartados de esta relaci\u00f3n se ir\u00e1n definiendo las\n-- anteriores funciones.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport I1M.DivideVenceras\nimport Data.Matrix\nimport Data.List (delete)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Tipos                                                            --\n-- ---------------------------------------------------------------------\n\n-- Los tableros son matrices de n\u00fameros enteros donde -1 representa el\n-- hueco, 0 las posiciones sin rellenar y los n\u00fameros mayores que 0\n-- representan los triomin\u00f3s.\n\ntype Tablero = Matrix Int\n    \n-- Los problemas se representar\u00e1n mediante pares formados por un n\u00famero\n-- natural mayor que 0 (que indica el n\u00famero con el que se formar\u00e1 el\n-- siguiente triomin\u00f3 que se coloque) y un tablero.\n\ntype Problema = (Int,Tablero)\n\n-- Las posiciones son pares de n\u00fameros enteros\n\ntype Posicion = (Int,Int)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Problema inicial                                                 --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    tablero :: Int -> Posicion -> Tablero\n-- tal que (tablero n p) es el tablero inicial del problema del triomin\u00f3\n-- en un cuadrado nxn en el que se ha eliminado la casilla de la\n-- posici\u00f3n (i,j). Por ejemplo,\n--    ghci> tablero 4 (3,4)\n--    (  0  0  0  0 )\n--    (  0  0  0  0 )\n--    (  0  0  0 -1 )\n--    (  0  0  0  0 )\n-- ---------------------------------------------------------------------\n\ntablero :: Int -> Posicion -> Tablero\ntablero n (i,j) =\n    setElem (-1) (i,j) (zero n n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    pbInicial :: Int -> Posicion -> Problema\n-- tal que (pbInicial n p) es el problema inicial del rompecabeza del\n-- triomin\u00f3 en un cuadrado nxn en el que se ha eliminado la casilla de\n-- la posici\u00f3n p. Por ejemplo,\n--    ghci> pbInicial 4 (4,4)\n--    (1,(  0  0  0  0 )\n--       (  0  0  0  0 )\n--       (  0  0  0  0 )\n--       (  0  0  0 -1 ))\n-- ---------------------------------------------------------------------\n\npbInicial :: Int -> Posicion -> Problema\npbInicial n p = (1,tablero n p)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Problemas indivisibles                                           --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    ind :: Problema -> Bool\n-- tal que (ind pb) se verifica si el problema pb es indivisible. Por\n-- ejemplo, \n--    ind (pbInicial 2 (1,2))  ==  True\n--    ind (pbInicial 4 (1,2))  ==  False\n-- ---------------------------------------------------------------------\n\nind :: Problema -> Bool\nind (_,p) = ncols p == 2\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Resoluci\u00f3n de problemas indivisibles                             --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    posicionHueco :: Tablero -> Posicion\n-- tal que (posicionHueco t) es la posici\u00f3n del hueco en el tablero\n-- t. Por ejemplo,\n--    posicionHueco (tablero 8 (5,2))  ==  (5,2)\n-- ---------------------------------------------------------------------\n\nposicionHueco :: Tablero -> Posicion\nposicionHueco p = \n    head [(i,j) | i <- [1..nrows p],\n                  j <- [1..ncols p],\n                  p!(i,j) \/= 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    cuadranteHueco :: Tablero -> Int\n-- tal que (cuadranteHueco p) es el cuadrante donde se encuentra el\n-- hueco del tablero t (donde la numeraci\u00f3n de los cuadrantes es 1 el\n-- superior izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4\n-- el inferior derecho). Por ejemplo,\n--    cuadranteHueco (tablero 8 (4,4))  ==  1\n--    cuadranteHueco (tablero 8 (5,2))  ==  2\n--    cuadranteHueco (tablero 8 (3,6))  ==  3\n--    cuadranteHueco (tablero 8 (6,6))  ==  4\n-- ---------------------------------------------------------------------\n\ncuadranteHueco :: Tablero -> Int\ncuadranteHueco t \n    | i <= x &#038;&#038; j <= x = 1\n    | i >  x && j <= x = 2\n    | i <= x &#038;&#038; j >  x = 3\n    | otherwise        = 4\n    where (i,j) = posicionHueco t\n          x     = nrows t `div` 2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    centralHueco :: Tablero -> Posicion\n-- tal que (centralHueco t) es la casilla central del cuadrante del\n-- tablero t donde se encuentra el hueco. Por ejemplo,\n--    centralHueco (tablero 8 (5,2))  ==  (5,4)\n--    centralHueco (tablero 8 (4,4))  ==  (4,4)\n--    centralHueco (tablero 8 (3,6))  ==  (4,5)\n--    centralHueco (tablero 8 (6,6))  ==  (5,5)\n-- ---------------------------------------------------------------------\n\ncentralHueco :: Tablero -> Posicion\ncentralHueco t = case (cuadranteHueco t) of\n                   1 -> (x,x)\n                   2 -> (x+1,x)\n                   3 -> (x,x+1)\n                   4 -> (x+1,x+1)\n    where x = nrows t `div` 2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    centralesSinHueco :: Tablero -> [Posicion]\n-- (centralesSinHueco t) son las posiciones centrales del tablero t de\n-- los cuadrantes sin hueco. Por ejemplo,\n--    centralesSinHueco (tablero 8 (5,2))  ==  [(4,4),(4,5),(5,5)]\n-- ---------------------------------------------------------------------\n\ncentralesSinHueco :: Tablero -> [Posicion]\ncentralesSinHueco t = \n    delete (i,j) [(x,x),(x+1,x),(x,x+1),(x+1,x+1)]\n    where x     = nrows t `div` 2\n          (i,j) = centralHueco t\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    actualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a\n-- tal que (actualiza t ps) es la matriz obtenida cambiando en t los\n-- valores del las posiciones indicadas en ps por sus correspondientes\n-- valores. Por ejemplo,\n--    ghci> actualiza (identity 3) [((1,2),4),((3,1),5)]\n--    ( 1 4 0 )\n--    ( 0 1 0 )\n--    ( 5 0 1 )\n-- ---------------------------------------------------------------------\n\nactualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a\nactualiza p []             = p\nactualiza p (((i,j),x):zs) = setElem x (i,j) (actualiza p zs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    triominoCentral :: Problema -> Tablero\n-- tal que (triominoCentral (n,t) es el tablero obtenido colocando el\n-- triomin\u00f3 formado por el n\u00famero n en las posiciones centrales de los 3\n-- cuadrantes que no contienen el hueco. Por ejemplo,\n--    ghci> triominoCentral (7,tablero 4 (4,4))\n--    (  0  0  0  0 )\n--    (  0  7  7  0 )\n--    (  0  7  0  0 )\n--    (  0  0  0 -1 )\n-- ---------------------------------------------------------------------\n\ntriominoCentral :: Problema -> Tablero\ntriominoCentral (n,t) =\n    actualiza t [((i,j),n) | (i,j) <- centralesSinHueco t]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    resuelve :: Problema -> Tablero\n-- tal que (resuelve p) es la soluci\u00f3n del problema indivisible p. Por\n-- ejemplo,  \n--    ghci> tablero 2 (2,2)\n--    (  0  0 )\n--    (  0 -1 )\n--    \n--    ghci> resuelve (5,tablero 2 (2,2))\n--    (  5  5 )\n--    (  5 -1 )\n-- ---------------------------------------------------------------------\n\nresuelve :: Problema -> Tablero\nresuelve = triominoCentral\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Divisi\u00f3n en subproblemas                                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    divide :: Problema -> [Problema]\n-- tal que (divide (n,t)) es la lista de de los problemas obtenidos\n-- colocando el triomin\u00f3 n en las casillas centrales de t que no\n-- contienen el hueco y dividir el tablero en sus cuatros cuadrantes y\n-- aumentar en uno el n\u00famero del correspondiente triomin\u00f3. Por ejemplo,\n--    ghci> divide (3,tablero 4 (4,4))\n--    [(4,(  0  0 )\n--        (  3  0 )),\n--     (5,(  0  0 )\n--        (  0  3 )),\n--     (6,(  0  3 )\n--        (  0  0 )),\n--     (7,(  0  0 )\n--        (  0 -1 ))]\n-- ---------------------------------------------------------------------\n\ndivide :: Problema -> [Problema]\ndivide (n,t) = \n    [(n+1, submatrix 1     x (x+1) m q),\n     (n+2, submatrix 1     x 1     x q),\n     (n+3, submatrix (x+1) m 1     x q),\n     (n+4, submatrix (x+1) m (x+1) m q)]\n    where q = triominoCentral (n,t)\n          m = nrows t\n          x = m `div` 2\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaci\u00f3n de soluciones                                        --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    combina :: Problema -> [Tablero] -> Tablero\n-- tal que (combina p ts) es la combinaci\u00f3n de las soluciones ts de los\n-- subproblemas del problema p. Por ejemplo,\n--    ghci> let inicial = (1,tablero 4 (4,4)) :: (Int,Matrix Int)\n--    ghci> let [p1,p2,p3,p4] = divide inicial\n--    ghci> let [s1,s2,s3,s4] = map resuelve [p1,p2,p3,p4]\n--    ghci> combina 1 [s1,s2,s3,s4]\n--    (  3  3  2  2 )\n--    (  3  1  1  2 )\n--    (  4  1  5  5 )\n--    (  4  4  5 -1 )\n-- ---------------------------------------------------------------------\n\ncombina :: Problema -> [Tablero] -> Tablero\ncombina _ [s1,s2,s3,s4] = joinBlocks (s2,s1,s3,s4)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Soluci\u00f3n mediante divide y vencer\u00e1s                              --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    triomino :: Int -> Posicion -> Tablero\n-- tal que (triomino n p) es la soluci\u00f3n, mediante divide y vencer\u00e1s,\n-- del rompecabeza del triomin\u00f3 en un cuadrado nxn en el que se ha\n-- eliminado la casilla de la posici\u00f3n p. Por ejemplo,\n--    ghci> triomino 4 (4,4)\n--    (  3  3  2  2 )\n--    (  3  1  1  2 )\n--    (  4  1  5  5 )\n--    (  4  4  5 -1 )\n--    \n--    ghci> triomino 4 (2,3)\n--    (  3  3  2  2 )\n--    (  3  1 -1  2 )\n--    (  4  1  1  5 )\n--    (  4  4  5  5 )\n--    \n--    ghci> triomino 16 (5,6)\n--    (  7  7  6  6  6  6  5  5  6  6  5  5  5  5  4  4 )\n--    (  7  5  5  6  6  4  4  5  6  4  4  5  5  3  3  4 )\n--    (  8  5  9  9  7  7  4  8  7  4  8  8  6  6  3  7 )\n--    (  8  8  9  3  3  7  8  8  7  7  8  2  2  6  7  7 )\n--    (  8  8  7  3  9 -1  8  8  7  7  6  6  2  8  7  7 )\n--    (  8  6  7  7  9  9  7  8  7  5  5  6  8  8  6  7 )\n--    (  9  6  6 10 10  7  7 11  8  8  5  9  9  6  6 10 )\n--    (  9  9 10 10 10 10 11 11  1  8  9  9  9  9 10 10 )\n--    (  8  8  7  7  7  7  6  1  1  9  8  8  8  8  7  7 )\n--    (  8  6  6  7  7  5  6  6  9  9  7  8  8  6  6  7 )\n--    (  9  6 10 10  8  5  5  9 10  7  7 11  9  9  6 10 )\n--    (  9  9 10  4  8  8  9  9 10 10 11 11  5  9 10 10 )\n--    (  9  9  8  4  4 10  9  9 10 10  9  5  5 11 10 10 )\n--    (  9  7  8  8 10 10  8  9 10  8  9  9 11 11  9 10 )\n--    ( 10  7  7 11 11  8  8 12 11  8  8 12 12  9  9 13 )\n--    ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )\n\ntriomino :: Int -> Posicion -> Tablero\ntriomino n p =\n    divideVenceras ind resuelve divide combina (pbInicial n p)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han resuelto ejercicios de la relaci\u00f3n 41 sobre la soluci\u00f3n del problema del triomin\u00f3 mediante divide y vencer\u00e1s. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[320],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6671"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=6671"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6671\/revisions"}],"predecessor-version":[{"id":6672,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6671\/revisions\/6672"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6671"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6671"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6671"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}