Menu Close

El problema de las N torres

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ón 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,

   ( 0 1 0 )
   ( 1 0 0 )
   ( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

   torres  :: Int -> [Matrix Int]
   nTorres :: Int -> Integer

tales que
+ (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

      λ> torres 3
      [( 1 0 0 )
       ( 0 1 0 )
       ( 0 0 1 )
      ,( 1 0 0 )
       ( 0 0 1 )
       ( 0 1 0 )
      ,( 0 1 0 )
       ( 1 0 0 )
       ( 0 0 1 )
      ,( 0 1 0 )
       ( 0 0 1 )
       ( 1 0 0 )
      ,( 0 0 1 )
       ( 1 0 0 )
       ( 0 1 0 )
      ,( 0 0 1 )
       ( 0 1 0 )
       ( 1 0 0 )
      ]
  • (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,
      λ> nTorres 3
      6
      λ> length (show (nTorres (10^4)))
      35660

Soluciones

import Data.List (genericLength, sort, permutations)
import Data.Matrix 
 
-- 1ª definición de torres
-- =======================
 
torres1 :: Int -> [Matrix Int]
torres1 n = 
    [permutacionAmatriz n p | p <- sort (permutations [1..n])]
 
permutacionAmatriz :: Int -> [Int] -> Matrix Int
permutacionAmatriz n p =
    matrix n n f
    where f (i,j) | (i,j) `elem` posiciones = 1
                  | otherwise               = 0
          posiciones = zip [1..n] p    
 
-- 2ª definición de torres
-- =======================
 
torres2 :: Int -> [Matrix Int]
torres2 = map fromLists . permutations . toLists . identity
 
-- El cálculo con la definición anterior es:
--    λ> identity 3
--    ( 1 0 0 )
--    ( 0 1 0 )
--    ( 0 0 1 )
--    
--    λ> toLists it
--    [[1,0,0],[0,1,0],[0,0,1]]
--    λ> permutations it
--    [[[1,0,0],[0,1,0],[0,0,1]],
--     [[0,1,0],[1,0,0],[0,0,1]],
--     [[0,0,1],[0,1,0],[1,0,0]],
--     [[0,1,0],[0,0,1],[1,0,0]],
--     [[0,0,1],[1,0,0],[0,1,0]],
--     [[1,0,0],[0,0,1],[0,1,0]]]
--    λ> map fromLists it
--    [( 1 0 0 )
--     ( 0 1 0 )
--     ( 0 0 1 )
--    ,( 0 1 0 )
--     ( 1 0 0 )
--     ( 0 0 1 )
--    ,( 0 0 1 )
--     ( 0 1 0 )
--     ( 1 0 0 )
--    ,( 0 1 0 )
--     ( 0 0 1 )
--     ( 1 0 0 )
--    ,( 0 0 1 )
--     ( 1 0 0 )
--     ( 0 1 0 )
--    ,( 1 0 0 )
--     ( 0 0 1 )
--     ( 0 1 0 )
--    ]
 
-- 1ª definición de nTorres
-- ========================
 
nTorres1 :: Int -> Integer
nTorres1 = genericLength . torres1
 
-- 2ª definición de nTorres
-- ========================
 
nTorres2 :: Int -> Integer
nTorres2 n = product [1..fromIntegral n]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nTorres1 9
--    362880
--    (4.22 secs, 693,596,128 bytes)
--    λ> nTorres2 9
--    362880
--    (0.00 secs, 0 bytes)
Avanzado

3 soluciones de “El problema de las N torres

  1. alerodrod5
     
    import I1M.BusquedaEnEspaciosDeEstados
    import Data.List
    import Data.Matrix
     
     
    type SolNT = [(Int,Int)]
     
     
    valida :: SolNT -> (Int,Int) -> Bool
    valida solp (c,r) = and [test s | s <- solp]
        where test (c',r') = r'/=r
     
    type NodoNT = (Int,Int,SolNT)
     
    sucesoresNT :: NodoNT -> [NodoNT]
    sucesoresNT (c,n,solp)
        = [(c+1,n,solp++[(c,r)]) | r <- [1..n] , valida solp (c,r)]
     
    esFinalNT :: NodoNT -> Bool
    esFinalNT (c,n,solp) = c > n
     
    buscaEE_NT :: Int -> [NodoNT]
    buscaEE_NT n = buscaEE sucesoresNT esFinalNT (1,n,[])
     
     
    elimina (x,y,z) = z
     
    creaLista n = map elimina (buscaEE_NT n)
     
    transforma [] = []
    transforma ((x,y):xs) = [[(y,1)]] ++ transforma xs
     
    ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a
    ampliada = (fromLists .) . map . filaAmpliada
     
    filaAmpliada :: Num a => Int -> [(Int,a)] -> [a]
    filaAmpliada n xs =
      [f (lookup i xs) | i <- [1..n]]
      where f Nothing  = 0
            f (Just x) = x
    torres  :: Int -> [Matrix Int]
    torres n = map (ampliada n) (map transforma (creaLista n))
    nTorres :: Int -> Integer
    nTorres n = 
        genericLength (buscaEE sucesoresNT 
                        esFinalNT 
                        (1,n,[]))
     
    nTorres2 :: Int -> Integer
    nTorres2 n = factorial n
     
    factorial :: Int -> Integer
    factorial n = product [1..toInteger n]
  2. jaibengue
    import Data.List
    import Data.Matrix
     
    torres :: Int -> [Matrix Int]
    torres n = construye (permutations [1..n]) 
      where construye (xs:xss) = (mat xs 1) : construye xss
              where mat (x:xs) v = setElem 1 (v,x) (mat xs (v+1))
                    mat _  _     = zero n n
            construye _ = []
     
    nTorres :: Int -> Integer
    nTorres 0 = 1
    nTorres n = fromIntegral n * nTorres (n-1)
  3. albcarcas1
     
    import Data.Matrix as M
     
    torres :: Int -> [M.Matrix Int]
    torres =  map M.fromLists . permutations . M.toLists. M.identity
    nTorres :: Int -> Integer
    nTorres n = toInteger(product[1..n])
    nTorres2 :: Int -> Integer
    nTorres2 = genericLength . torres

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.