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, mediante búsqueda en espacio de estados, la función
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,
λ> 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..4], y <- [x..4]]) 0
Nota: Las librerías necesarias se encuentran en la página de códigos.
Soluciones
import I1M.BusquedaEnEspaciosDeEstados (buscaEE) import Data.List (delete) type Ficha = (Int,Int) -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type EstadoDomino = ([Ficha],[Ficha]) inicialDomino :: [Ficha] -> EstadoDomino inicialDomino fs = (fs,[]) esFinalDomino :: EstadoDomino -> Bool esFinalDomino (fs,_) = null fs sucesoresDomino :: EstadoDomino -> [EstadoDomino] sucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs] sucesoresDomino (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] solucionesDomino :: [Ficha] -> [EstadoDomino] solucionesDomino ps = buscaEE sucesoresDomino esFinalDomino (inicialDomino ps) domino :: [(Int,Int)] -> [[(Int,Int)]] domino ps = map snd (solucionesDomino ps)