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,
|
1 2 3 |
( 0 1 0 ) ( 1 0 0 ) ( 0 0 1 ) |
representa una solución del problema de las 3 torres.
Definir las funciones
|
1 2 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
λ> 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,
|
1 2 3 4 |
λ> nTorres 3 6 λ> length (show (nTorres (10^4))) 35660 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
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) |