{"id":5038,"date":"2019-05-27T06:00:36","date_gmt":"2019-05-27T04:00:36","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5038"},"modified":"2019-05-26T19:35:14","modified_gmt":"2019-05-26T17:35:14","slug":"el-problema-de-las-n-torres","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-problema-de-las-n-torres\/","title":{"rendered":"El problema de las N torres"},"content":{"rendered":"

El problema de las N torres<\/strong> consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.<\/p>\n

Cada soluci\u00f3n del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,<\/p>\n

 \n   ( 0 1 0 )\n   ( 1 0 0 )\n   ( 0 0 1 )\n<\/pre>\n
representa una soluci\u00f3n del problema de las 3 torres.<\/p>\n
Definir las funciones<\/p>\n
 \n   torres  :: Int -> [Matrix Int]\n   nTorres :: Int -> Integer\n<\/pre>\n
tales que<\/p>\n
    \n
  • (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,<\/li>\n<\/ul>\n
     \n      \u03bb> torres 3\n      [( 1 0 0 )\n       ( 0 1 0 )\n       ( 0 0 1 )\n      ,( 1 0 0 )\n       ( 0 0 1 )\n       ( 0 1 0 )\n      ,( 0 1 0 )\n       ( 1 0 0 )\n       ( 0 0 1 )\n      ,( 0 1 0 )\n       ( 0 0 1 )\n       ( 1 0 0 )\n      ,( 0 0 1 )\n       ( 1 0 0 )\n       ( 0 1 0 )\n      ,( 0 0 1 )\n       ( 0 1 0 )\n       ( 1 0 0 )\n      ]\n<\/pre>\n
    donde se ha indicado con 1 las posiciones ocupadas por las torres.<\/p>\n
      \n
    • (nTorres n) es el n\u00famero de soluciones del problema de las n torres. Por ejemplo,   <\/li>\n<\/ul>\n
       \n      \u03bb> nTorres 3\n      6\n      \u03bb> length (show (nTorres (10^4)))\n      35660\n<\/pre>\n
      Soluciones<\/h4>\n
      [schedule expon=’2019-06-03′ expat=\u00bb06:00″]<\/p>\n
        \n
      • Las soluciones se pueden escribir en los comentarios hasta el 03 de junio.\n
      • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang=\u00bbhaskell\u00bb> y otra con <\/pre>\n<\/ul>\n
        Pensamiento<\/h4>\n
        \nNubes, sol, prado verde y caser\u00edo \\\\
        \nen la loma revueltos. Primavera \\\\
        \npuso en el aire de este campo fr\u00edo \\\\
        \nla gracia de sus chopos de ribera.<\/p>\n
        Antonio Machado\n<\/p><\/blockquote>\n
        [\/schedule]<\/p>\n
        [schedule on=’2019-06-03′ at=\u00bb06:00″]<\/p>\n
        \r\nimport Data.List (genericLength, sort, permutations)\r\nimport Data.Matrix \r\n\r\n-- 1\u00aa definici\u00f3n de torres\r\n-- =======================\r\n\r\ntorres1 :: Int -> [Matrix Int]\r\ntorres1 n = \r\n    [permutacionAmatriz n p | p <- sort (permutations [1..n])]\r\n\r\npermutacionAmatriz :: Int -> [Int] -> Matrix Int\r\npermutacionAmatriz n p =\r\n    matrix n n f\r\n    where f (i,j) | (i,j) `elem` posiciones = 1\r\n                  | otherwise               = 0\r\n          posiciones = zip [1..n] p    \r\n\r\n-- 2\u00aa definici\u00f3n de torres\r\n-- =======================\r\n\r\ntorres2 :: Int -> [Matrix Int]\r\ntorres2 = map fromLists . permutations . toLists . identity\r\n\r\n-- El c\u00e1lculo con la definici\u00f3n anterior es:\r\n--    \u03bb> identity 3\r\n--    ( 1 0 0 )\r\n--    ( 0 1 0 )\r\n--    ( 0 0 1 )\r\n--    \r\n--    \u03bb> toLists it\r\n--    [[1,0,0],[0,1,0],[0,0,1]]\r\n--    \u03bb> permutations it\r\n--    [[[1,0,0],[0,1,0],[0,0,1]],\r\n--     [[0,1,0],[1,0,0],[0,0,1]],\r\n--     [[0,0,1],[0,1,0],[1,0,0]],\r\n--     [[0,1,0],[0,0,1],[1,0,0]],\r\n--     [[0,0,1],[1,0,0],[0,1,0]],\r\n--     [[1,0,0],[0,0,1],[0,1,0]]]\r\n--    \u03bb> map fromLists it\r\n--    [( 1 0 0 )\r\n--     ( 0 1 0 )\r\n--     ( 0 0 1 )\r\n--    ,( 0 1 0 )\r\n--     ( 1 0 0 )\r\n--     ( 0 0 1 )\r\n--    ,( 0 0 1 )\r\n--     ( 0 1 0 )\r\n--     ( 1 0 0 )\r\n--    ,( 0 1 0 )\r\n--     ( 0 0 1 )\r\n--     ( 1 0 0 )\r\n--    ,( 0 0 1 )\r\n--     ( 1 0 0 )\r\n--     ( 0 1 0 )\r\n--    ,( 1 0 0 )\r\n--     ( 0 0 1 )\r\n--     ( 0 1 0 )\r\n--    ]\r\n\r\n-- 1\u00aa definici\u00f3n de nTorres\r\n-- ========================\r\n\r\nnTorres1 :: Int -> Integer\r\nnTorres1 = genericLength . torres1\r\n\r\n-- 2\u00aa definici\u00f3n de nTorres\r\n-- ========================\r\n\r\nnTorres2 :: Int -> Integer\r\nnTorres2 n = product [1..fromIntegral n]\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n--    \u03bb> nTorres1 9\r\n--    362880\r\n--    (4.22 secs, 693,596,128 bytes)\r\n--    \u03bb> nTorres2 9\r\n--    362880\r\n--    (0.00 secs, 0 bytes)\r\n<\/pre>\n
        [\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"
        El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna. Cada soluci\u00f3n del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las…<\/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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5038"}],"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=5038"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5038\/revisions"}],"predecessor-version":[{"id":5041,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5038\/revisions\/5041"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5038"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5038"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5038"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}