{"id":4904,"date":"2015-05-13T17:43:02","date_gmt":"2015-05-13T15:43:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4904"},"modified":"2015-05-15T13:45:02","modified_gmt":"2015-05-15T11:45:02","slug":"i1m2014-el-rompecabeza-del-triomino-mediante-divide-y-venceras","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-rompecabeza-del-triomino-mediante-divide-y-venceras\/","title":{"rendered":"I1M2014: El rompecabeza del triomin\u00f3 mediante divide y vencer\u00e1s"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 35 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-14\/codigos\n--\n-- Las transparencias del tema 23 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/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 clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 35 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":"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":[238],"tags":[244,270,305],"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\/4904"}],"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=4904"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4904\/revisions"}],"predecessor-version":[{"id":4905,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4904\/revisions\/4905"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4904"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4904"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4904"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}