I1M2018: El problema del calendario mediante búsqueda en espacio de estado

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------
 
-- El problema del calendario, para una competición deportiva en la que
-- se enfrentan n participantes, consiste en elaborar un calendario de 
-- forma que: 
--    + el campeonato dure n-1 días,
--    + cada participante juegue exactamente un partido diario y
--    + cada participante juegue exactamente una vez con cada adversario.
-- Por ejemplo, con 8 participantes una posible solución es
--      | 1 2 3 4 5 6 7
--    --+--------------
--    1 | 2 3 4 5 6 7 8
--    2 | 1 4 3 6 5 8 7
--    3 | 4 1 2 7 8 5 6
--    4 | 3 2 1 8 7 6 5
--    5 | 6 7 8 1 2 3 4
--    6 | 5 8 7 2 1 4 3
--    7 | 8 5 6 3 4 1 2
--    8 | 7 6 5 4 3 2 1
-- donde las filas indican los jugadores y las columnas los días; es
-- decir, el elemento (i,j) indica el adversario del jugador i el día j;
-- por ejemplo, el adversario del jugador 2 el 4ª día es el jugador 6.
-- 
-- El objetivo de esta relación de ejercicios es resolver el problema
-- del calendario mediante búsqueda en espacio de estados, utilizando las
-- implementaciones estudiadas en el tema 23 que se pueden descargar desde 
--    http://www.cs.us.es/~jalonso/cursos/i1m-14/codigos
--
-- Las transparencias del tema 23 se encuentran en
--    http://www.cs.us.es/~jalonso/cursos/i1m-14/temas/tema-23.pdf
 
-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------
 
import I1M.BusquedaEnEspaciosDeEstados
import Data.Matrix
import Data.List
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir el tipo Calendario como una matriz de números
-- enteros. 
-- ---------------------------------------------------------------------
 
type Calendario = Matrix Int
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función 
--    inicial :: Int -> Calendario
-- tal que (inicial n) es el estado inicial para el problema del
-- calendario con n participantes; es decir, una matriz de n fila y n-1
-- columnas con todos sus elementos iguales a 0. Por ejemplo,
--    ghci> inicial 4
--    ( 0 0 0 )
--    ( 0 0 0 )
--    ( 0 0 0 )
--    ( 0 0 0 )
-- ---------------------------------------------------------------------
 
inicial :: Int -> Calendario
inicial n = zero n (n-1)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función 
--    sucesores :: Int -> Calendario -> [Calendario]
-- tal que (sucesores n c) es la lista de calendarios, para el problema
-- con n participantes, obtenidos poniendo en el lugar del primer
-- elemento nulo de c uno de los posibles jugadores de forma que se
-- cumplan las condiciones del problema. Por ejemplo,
--    ghci> sucesores 4 (fromLists [[2,0,0],[0,0,0],[0,0,0]])
--    [( 2 3 0 )
--     ( 0 0 0 )
--     ( 0 0 0 )
--    ,( 2 4 0 )
--     ( 0 0 0 )
--     ( 0 0 0 )]
--    ghci> sucesores 4 (fromLists [[2,3,0],[0,0,0],[0,0,0]])
--    [( 2 3 4 )
--     ( 0 0 0 )
--     ( 0 0 0 )]
--    ghci> sucesores 4 (fromLists [[2,3,4],[3,1,0],[0,0,0]])
--    []
-- ---------------------------------------------------------------------
 
sucesores :: Int -> Calendario -> [Calendario]
sucesores n c = 
    [setElem k (i,j) c |
     k <- [1..n] \\ (i : [c!(k,j) | k <- [1..i-1]]
                         ++ [c!(i,k) | k <- [1..j-1]])]
    where (i,j) = head [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    esFinal :: Int -> Calendario -> Bool
-- tal que (final n c) se verifica si c un estado final para el problema
-- del calendario con n participantes; es decir, no queda en c ningún
-- elemento igual a 0 (que es equivalente, por la manera de rellenar el
-- calendario, a decir que el elemento de c en la posición (n,n-1) es
-- distinto de 0). Por ejemplo, 
--    ghci> esFinal 4 (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]])
--    True
--    ghci> esFinal 4 (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]])
--    False
-- ---------------------------------------------------------------------
 
esFinal :: Int -> Calendario -> Bool
esFinal n c = c!(n,n-1) /= 0
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    calendario :: Int -> [Calendario]
-- tal que (calendario n) son las soluciones del problema del calendario,
-- con n participantes, mediante el patrón de búsqueda en espacio de
-- estados. Por ejemplo, 
--    ghci> head (calendario 5)
--    ( 2 3 4 5 )
--    ( 1 4 5 3 )
--    ( 4 5 1 2 )
--    ( 5 2 3 1 )
--    ( 3 1 2 4 )
--    
--    ghci> length (calendario 5)
--    1344
-- ---------------------------------------------------------------------
 
calendario :: Int -> [Calendario]
calendario n = buscaEE (sucesores n)
                       (esFinal n)        
                       (inicial n)