Problema del dominó
Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.
Definir la función
|
1 |
domino :: [(Int,Int)] -> [[(Int,Int)]] |
tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. 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 |
λ> domino [(1,2),(2,3),(1,4)] [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] λ> domino [(1,2),(1,1),(1,4)] [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] λ> domino [(1,2),(3,4),(2,3)] [[(1,2),(2,3),(3,4)]] λ> domino [(1,2),(2,3),(5,4)] [] λ> domino [(x,y) | x <- [1..2], y <- [x..2]] [[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]] λ> [(x,y) | x <- [1..3], y <- [x..3]] [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]]) [(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)] [(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)] [(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)] [(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)] [(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)] [(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)] [(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)] [(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)] [(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)] λ> length (domino [(x,y) | x <- [1..3], y <- [x..3]]) 9 λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]]) 0 λ> length (domino [(x,y) | x <- [1..5], y <- [x..5]]) 84480 |
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 |
import I1M.BusquedaEnEspaciosDeEstados (buscaEE) import Data.List (delete) -- 1ª solución (por búsqueda en anchura) -- ===================================== -- Las fichas son pares de números enteros. type Ficha = (Int,Int) -- Un problema está definido por la lista de fichas que hay que colocar type Problema = [Ficha] -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type Estado = ([Ficha],[Ficha]) -- (inicial p) es el estado inicial del problema p. inicial :: Problema -> Estado inicial p = (p,[]) -- (es final e) se verifica si e es un estado final. esFinal :: Estado -> Bool esFinal (fs,_) = null fs sucesores :: Estado -> [Estado] sucesores (fs,[]) = [(delete f fs, [f]) | f <- fs] sucesores (fs,n@((x,y):qs)) = [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u /= v, v == x] ++ [(delete (u,v) fs,(v,u):n) | (u,v) <- fs, u /= v, u == x] ++ [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u == v, u == x] soluciones :: Problema -> [Estado] soluciones p = busca [(inicial p)] where busca [] = [] busca (e:es) | esFinal e = e : busca es | otherwise = busca (es ++ sucesores e) domino :: Problema -> [[Ficha]] domino ps = map snd (soluciones ps) -- 2ª solución (por búsqueda en profundidad) -- ========================================= soluciones2 :: Problema -> [Estado] soluciones2 p = busca [(inicial p)] where busca [] = [] busca (e:es) | esFinal e = e : busca es | otherwise = busca (sucesores e ++ es) domino2 :: Problema -> [[Ficha]] domino2 ps = map snd (soluciones2 ps) -- 3ª solución (con I1M.BusquedaEnEspaciosDeEstados) -- ================================================= domino3 :: Problema -> [[Ficha]] domino3 ps = map snd (soluciones3 ps) soluciones3 :: Problema -> [Estado] soluciones3 ps = buscaEE sucesores esFinal (inicial ps) |
Un comentario