{"id":3315,"date":"2013-05-07T15:33:32","date_gmt":"2013-05-07T15:33:32","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3315"},"modified":"2013-05-10T15:35:21","modified_gmt":"2013-05-10T15:35:21","slug":"i1m2012-el-problema-de-las-n-reinas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-problema-de-las-n-reinas-en-haskell\/","title":{"rendered":"I1M2012: El problema de las N reinas en Haskell"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el problema de las reinas (consistente en colocar N reinas en un tablero de dimensiones N por N de forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal) y su programaci\u00f3n en Haskell.<\/p>\n

El c\u00f3digo del problema de las N reinas es
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Enunciado                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Colocar N reinas en un tablero rectangular de dimensiones N por N de\r\n-- forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal,\r\n-- vertical o diagonal. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librerias auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List ((\\\\))\r\n\r\n-- El tablero se representa por una lista de n\u00fameros que indican las\r\n-- filas donde se han colocado las reinas. Por ejemplo, [3,5]\r\n-- indica que se han colocado las reinas (1,3) y (2,5). \r\ntype Tablero = [Int]  \r\n\r\n-- (reinas n) es la lista de soluciones del problema de las N\r\n-- reinas. Por ejemplo, \r\n--    reinas 4  == [[3,1,4,2],[2,4,1,3]].  \r\n-- La primera soluci\u00f3n [3,1,4,2] se interpreta como \r\n--    +---------------+\r\n--    |   | R |   |   |\r\n--    +---------------+\r\n--    |   |   |   | R |\r\n--    +---------------+\r\n--    | R |   |   |   |\r\n--    +---------------+\r\n--    |   |   | R |   |\r\n--    +---------------+\r\nreinas :: Int -> [Tablero]\r\nreinas n = aux n\r\n    where aux 0 = [[]]\r\n          aux m = [r:rs | rs <- aux (m-1),\r\n                          r <- ([1..n] \\\\ rs),\r\n                          noAtaca r rs 1]\r\n\r\n-- (noAtaca r rs d) se verifica si la reina r no ataca a niguna de las\r\n-- de la lista rs donde la primera de la lista est\u00e1 a una distancia\r\n-- horizontal d. \r\nnoAtaca :: Int -> Tablero -> Int -> Bool\r\nnoAtaca _ [] _ = True\r\nnoAtaca r (a:rs) distH = abs(r-a) \/= distH &&\r\n                         noAtaca r rs (distH+1)\r\n<\/pre>\n
Las transparencias usadas en la clase son desde la p\u00e1gina 37 a la 45 del tema 11<\/a>:
\n