Espacio de estados del problema de las N reinas
El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es
|
1 2 3 4 5 6 7 8 9 |
|---|---|---|---| | | R | | | |---|---|---|---| | | | | R | |---|---|---|---| | R | | | | |---|---|---|---| | | | R | | |---|---|---|---| |
Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.
Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].
Usando la librería de árboles Data.Tree, definir las funciones
|
1 2 3 4 |
arbolReinas :: Int -> Tree [Int] nEstados :: Int -> Int soluciones :: Int -> [[Int]] nSoluciones :: Int -> Int |
tales que
- (arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
λ> putStrLn (drawTree (fmap show (arbolReinas 4))) [] | +- [1] | | | +- [3,1] | | | `- [4,1] | | | `- [2,4,1] | +- [2] | | | `- [4,2] | | | `- [1,4,2] | | | `- [3,1,4,2] | +- [3] | | | `- [1,3] | | | `- [4,1,3] | | | `- [2,4,1,3] | `- [4] | +- [1,4] | | | `- [3,1,4] | `- [2,4] λ> putStrLn (drawTree (fmap show (arbolReinas 5))) [] | +- [1] | | | +- [3,1] | | | | | `- [5,3,1] | | | | | `- [2,5,3,1] | | | | | `- [4,2,5,3,1] | | | +- [4,1] | | | | | `- [2,4,1] | | | | | `- [5,2,4,1] | | | | | `- [3,5,2,4,1] | | | `- [5,1] | | | `- [2,5,1] | +- [2] | | | +- [4,2] | | | | | `- [1,4,2] | | | | | `- [3,1,4,2] | | | | | `- [5,3,1,4,2] | | | `- [5,2] | | | +- [1,5,2] | | | | | `- [4,1,5,2] | | | `- [3,5,2] | | | `- [1,3,5,2] | | | `- [4,1,3,5,2] | +- [3] | | | +- [1,3] | | | | | `- [4,1,3] | | | | | `- [2,4,1,3] | | | | | `- [5,2,4,1,3] | | | `- [5,3] | | | `- [2,5,3] | | | `- [4,2,5,3] | | | `- [1,4,2,5,3] | +- [4] | | | +- [1,4] | | | | | +- [3,1,4] | | | | | | | `- [5,3,1,4] | | | | | | | `- [2,5,3,1,4] | | | | | `- [5,1,4] | | | | | `- [2,5,1,4] | | | `- [2,4] | | | `- [5,2,4] | | | `- [3,5,2,4] | | | `- [1,3,5,2,4] | `- [5] | +- [1,5] | | | `- [4,1,5] | +- [2,5] | | | `- [4,2,5] | | | `- [1,4,2,5] | | | `- [3,1,4,2,5] | `- [3,5] | `- [1,3,5] | `- [4,1,3,5] | `- [2,4,1,3,5] |
- (nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,
|
1 2 3 |
nEstados 4 == 17 nEstados 5 == 54 map nEstados [0..10] == [1,2,3,6,17,54,153,552,2057,8394,35539] |
- (soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,
|
1 2 3 4 5 |
λ> soluciones 4 [[3,1,4,2],[2,4,1,3]] λ> soluciones 5 [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3], [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]] |
- (nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,
|
1 2 3 |
nSoluciones 4 == 2 nSoluciones 5 == 10 map nSoluciones [0..10] == [1,1,0,0,2,10,4,40,92,352,724] |
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 |
import Data.List ((\\)) import Data.Tree -- Definición de arbolReinas -- ========================= arbolReinas :: Int -> Tree [Int] arbolReinas n = expansion n [] where expansion m xs = Node xs [expansion (m-1) ys | ys <- sucesores n xs] -- (sucesores n xs) es la lista de los sucesores del estado xs en el -- problema de las n reinas. Por ejemplo, -- sucesores 4 [] == [[1],[2],[3],[4]] -- sucesores 4 [1] == [[3,1],[4,1]] -- sucesores 4 [4,1] == [[2,4,1]] -- sucesores 4 [2,4,1] == [] sucesores :: Int -> [Int] -> [[Int]] sucesores n xs = [y:xs | y <- [1..n] \\ xs , noAtaca y xs 1] -- (noAtaca y xs d) se verifica si la reina en la fila y no ataca a las -- colocadas en las filas xs donde d es el número de columnas desde la -- de la posición de x a la primera de xs. noAtaca :: Int -> [Int] -> Int -> Bool noAtaca _ [] _ = True noAtaca y (x:xs) distH = abs(y-x) /= distH && noAtaca y xs (distH + 1) -- Definición de nEstados -- ====================== nEstados :: Int -> Int nEstados = length . arbolReinas -- Definición de solucionesReinas -- ============================== -- λ> soluciones 4 -- [[3,1,4,2],[2,4,1,3]] -- λ> soluciones 5 -- [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3], -- [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]] soluciones :: Int -> [[Int]] soluciones n = filter (\xs -> length xs == n) (estados n) -- (estados n) es la lista de estados del problema de las n reinas. Por -- ejemplo, -- λ> estados 4 -- [[], -- [1],[2],[3],[4], -- [3,1],[4,1],[4,2],[1,3],[1,4],[2,4], -- [2,4,1],[1,4,2],[4,1,3],[3,1,4], -- [3,1,4,2],[2,4,1,3]] estados :: Int -> [[Int]] estados = concat . levels . arbolReinas -- Definición de nSoluciones -- ========================= nSoluciones :: Int -> Int nSoluciones = length . soluciones |