%%%%%%%%%%%% %% HECHOS %% %%%%%%%%%%%% mujer(pepa). mujer(lucía). mujer(blanca). mujer(rosa). mujer(alba). mujer(inés). mujer(irene). hombre(armando). hombre(julián). hombre(esteban). hombre(mario). hombre(alejandro). hombre(martín). hombre(matías). progenitor(pepa,lucía). progenitor(pepa,blanca). progenitor(pepa,mario). progenitor(lucía,rosa). progenitor(lucía,alba). progenitor(blanca,inés). progenitor(blanca,martín). progenitor(irene,matías). progenitor(armando,lucía). progenitor(armando,blanca). progenitor(armando,mario). progenitor(julián,rosa). progenitor(julián,alba). progenitor(alejandro,inés). progenitor(alejandro,martín). progenitor(mario,matías). %%%%%%%%%%%% %% REGLAS %% %%%%%%%%%%%% padre(X,Y) :- hombre(X), progenitor(X,Y). madre(X,Y) :- mujer(X), progenitor(X,Y). hijo(X,Y) :- hombre(X), progenitor(Y,X). hija(X,Y) :- mujer(X), progenitor(Y,X). abuelo(X,Y) :- hombre(X), progenitor(X,Z), progenitor(Z,Y). abuela(X,Y) :- mujer(X), progenitor(X,Z), progenitor(Z,Y). hermano(X,Y) :- hombre(X), progenitor(Z,X), progenitor(Z,Y), not(X=Y). hermana(X,Y) :- mujer(X), progenitor(Z,X), progenitor(Z,Y), not(X=Y). tío(X,Y) :- hermano(X,Z), progenitor(Z,Y). tía(X,Y) :- hermana(X,Z), progenitor(Z,Y). primo(X,Y) :- hijo(X,Z), progenitor(W,Y), ( hermano(Z,W) ; hermana(Z,W) ). prima(X,Y) :- hija(X,Z), progenitor(W,Y), ( hermano(Z,W) ; hermana(Z,W) ). hijoúnico(X) :- not(hermano(_,X) ; hermana(_,X)). % vamos a ver más sobre este problema en la clase
Otra opción para hijo único que funciona mejor, más acorde a nuestras intuiciones sobre el concepto:
hijoúnico(X) :- ( hombre(X) ; mujer(X) ) , ( not(hermano(_,X) ; hermana(_,X)) ).
Esta opción funciona mejor porque el árbol de búsqueda de resultados que se arma y sobre el cual el intérprete hace backtracking es considerablemente distinto.
Incorporamos cuñados, suegras y demás familias políticas. Para ello nos resultará muy útil definir el predicado “pareja”, y podremos escribir el resto de relaciones en función de ella.
pareja(X,Y) :- progenitor(X,Z), progenitor(Y,Z). cuñado(X,Y) :- hermano(X,Z), pareja(Z,Y). cuñada(X,Y) :- hermana(X,Z), pareja(Z,Y). suegra(X,Y) :- madre(X,Z), pareja(Y,Z). suegro(X,Y) :- padre(X,Z), pareja(Y,Z).
Fíjense que no hay que explicitar el sexo del cuñado, suegra, etc. porque ya está implícito en los predicados “hermano” y “madre”, respectivamente.
Para incorporar la regla “hermano mayor”, la única posibilidad es declarar hechos nuevos, en concreto, hechos que nos permitan saber si alguien es mayor o menor que otra persona. Eso se puede hacer más o menos ad hoc: lo más ad hoc que se me ocurre es declarar el hecho mayorQue entre los pares de hermanos, lo menos ad hoc, declarar la edad de cada persona e inferir de ese dato la relación mayorQue, de la siguiente manera:
%%% declaramos hechos sobre la edad de algunos miembros de la familia %%% edad(lucía,28). edad(blanca,26). edad(mario,24). mayor(X,Y) :- edad(X,EX), edad(Y,EY), EX>EY. hermanoMayor(X,Y) :- hermano(X,Y), mayor(X,Y). hermanoMenor(X,Y) :- hermano(X,Y), mayor(Y,X). hermanaMayor(X,Y) :- hermana(X,Y), mayor(X,Y). hermanaMenor(X,Y) :- hermana(X,Y), mayor(Y,X).
ordena :: (Int,Int) → (Int,Int) que, dados dos enteros, los ordena de menor a mayor.ordena :: (Int,Int) -> (Int,Int)
ordena (x,y) | x < y = (x,y)
| x > y = (y,x)
| x == y = (x,y)
ordena' :: (Int,Int) -> (Int,Int)
ordena' (x,y) | x <= y = (x,y)
| x > y = (y,x)
ambospositivos :: Int → Int → Bool, que dados dos enteros devuelve True si los dos son positivos.ambospositivos :: Int -> Int -> Bool
ambospositivos x y | x >= 0 && y >= 0 = True
| x >= 0 || y < 0 = False
ambospositivos'' :: Int -> Int -> Bool ambospositivos'' x y = x >= 0 && y >= 0
edad :: (Int, Int, Int) → (Int, Int, Int) → Int que dadas dos fechas indica los años transcurridos entre ellas. Por ejemplo edad (20,10,1968) (30,4,1987) = 18.edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int
edad (diaN,mesN,anioN) (diaA,mesA,anioA) | (mesN < mesA) || (mesN == mesA && diaN < diaA) = (anioA - anioN) - 1
| otherwise = anioA - anioN
cabeza :: [a] –> a, que devuelve el primer elemento de una lista.cabeza :: [a] -> a cabeza (x:_) = x cabeza [] = error "la lista es vacía y por lo tanto no tiene cabeza!"
cola :: [a] –> [a], que devuelve toda la lista menos el primer elemento.cola :: [a] -> [a] cola (_:xs) = xs cola [] = []
area :: Int -> Int -> Int -> Int
area alto ancho fondo = 2*frente + 2*lado + 2*tapa
where
frente = alto * ancho
lado = alto * fondo
tapa = ancho * fondo
esVaciaOPrimer0 :: [Int] → Bool que dada una lista decida si es vacía o bien su primer elemento es 0.esVaciaOPrimer0 :: [Int] -> Bool
esVaciaOPrimer0 [] = True
esVaciaOPrimer0 (x:_) | x == 0 = True
| otherwise = False
esVaciaOPrimer0' :: [Int] -> Bool esVaciaOPrimer0' [] = True esVaciaOPrimer0' (x:_) = x == 0
segundoEsSegundo :: (Int,Int) → [Int] → Bool que dada una tupla de enteros y una lista de enteros comprueba si el segundo elemento de la tupla es igual al segundo elemento de la lista.segundoEsSegundo :: (Int,Int) -> [Int] -> Bool segundoEsSegundo (_,x) (_:y:_) = x == y
recortaDia :: [Char] → [Char] que dada una lista de caracteres, comprueba si las letras de la lista forman el nombre de un día de la semana, si es así, si el día no es del fin de semana, devuelven la primera letra solamente, en cambio, si el día es de fin de semana, devuelven el nombre del día completo. Ayuda: fíjense que el resultado siempre debe ser una lista de caracteresrecortaDia :: [Char] -> [Char]
recortaDia x:xs | (x:xs) == "lunes" || (x:xs) == "martes" || (x:xs) == "miercoles" || (x:xs) == "jueves" || (x:xs) == "viernes" = [x]
| (x:xs) == "sabado" || (x:xs) == "domingo" = (x:xs)
| otherwise = error "el string de entrada no es un dia de la semana o tiene mayusculas o acentos"
averaver :: (Int,Int,Int) → (Int,Int,Int) que, dada una tresupla de enteros, si todos son positivos, invierte su orden, si todos son negativos, los cambia a positivos, y en cualquier otro caso, devuelve la misma tresupla.
averaver :: (Int,Int,Int) -> (Int,Int,Int)
averaver x y z | x > 0 && y > 0 && z > 0 = (z,y,x)
| x < 0 && y < 0 && z < 0 = ((-x),(-y),(-z))
| otherwise = (x,y,z)
ordenaSiPositivos :: (Int,Int) → (Int,Int), que ordena los números de una tupla de enteros si ambos son positivos, pero si son negativos los deja sin ordenar.
ordenaSiPositivos :: (Int,Int) -> (Int,Int)
ordenaSiPositivos (x,y) | x > 0 && y > 0 && x <= y = (x,y)
| x > 0 && y > 0 = (y,x)
| otherwise = (x,y)
o podemos colapsar los casos que tienen el mismo resultado:
ordenaSiPositivos' :: (Int,Int) -> (Int,Int)
ordenaSiPositivos' (x,y) | x > 0 && y > 0 && x > y = (y,x)
| otherwise = (x,y)
veintePorCiento :: [Float] → [Float] que dada una lista de números devuelve una lista con el 20% de cada elemento de la lista, y su generalización porCiento :: Float → [Float] → [Float] que dado un número n y una lista, devuelve el n por ciento de cada uno de los elementos de la lista.
veintePorCiento :: [Float] -> [Float] veintePorCiento [] = [] veintePorCiento (x:xs) = 0.2*x : veintePorCiento xs
porCiento :: Float -> [Float] -> [Float] porCiento n [] = [] porCiento n (x:xs) = n/100*x : porCiento n xs
multiplicar :: Int → [Int] → [Int] que dada un número n y una lista, multiplica cada uno de los elementos por n
multiplicar :: Int -> [Int] -> [Int] multiplicar n [] = [] multiplicar n (x:xs) = n*x : multiplicar n xs
soloPares :: [Int] → [Int] que dada una lista de enteros devuelve una lista que contiene sólo los pares de la lista original.
soloPares :: [Int] -> [Int]
soloPares [] = []
soloPares (x:xs) | mod x 2 == 0 = x : soloPares xs
| otherwise = soloPares xs
ningunFalse :: [Bool] → [Bool] que dada una lista de booleanos devuelve una lista sin ningún booleano False.
ningunFalse :: [Bool] -> [Bool]
ningunFalse [] = []
ningunFalse (x:xs) | x == True = x : ningunFalse xs
| otherwise = ningunFalse xs
soloMultiplos3 :: [Int] → [Int], que dada una lista de enteros devuelve una lista que contiene sólo los múltiplos de 3 de la lista original.
soloMultiplos3 :: [Int] -> [Int]
soloMultiplos3 [] = []
soloMultiplos3 (x:xs) | mod x 3 == 0 = x : soloMultiplos3 xs
| otherwise = soloMultiplos3 xs
productoria :: [Int] → Int que dada una lista devuelve el producto de sus elementos.
productoria :: [Int] -> Int productoria [] = 1 productoria (x:xs) = x * productoria xs
longitud :: [Int] → Int que dada una lista de enteros computa su largo.
longitud :: [Int] -> Int longitud [] = 0 longitud (x:xs) = 1 + longitud xs
sonTodos0 :: [Int] → Bool, que dada una lista devuelve True si todos los elementos de la lista son 0.
sonTodos0 :: [Int] -> Bool sonTodos0 [] = True sonTodos0 (x:xs) = x == 0 && sonTodos0 xs
todos0y1 : [Int] → Bool que dada una lista devuelve True si ésta consiste sólo de 0s y 1s.
todos0y1 :: [Int] -> Bool todos0y1 [] = True todos0y1 (x:xs) = ( x==0 || x==1 ) && todos0y1 xs
paratodo :: a → [a] → Bool, que dado un elemento y una lista, devuelve True si todos los elementos de la lista son iguales al elemento que damos como primer argumento. Fíjense que se trata de una generalización de los ejercicios anteriores.
paratodo :: Eq a => a -> [a] -> Bool paratodo e [] = True paratodo e (x:xs) = e == x && paratodo e xs
Fíjense que tenemos que añadir a la signatura el preámbulo Eq a ⇒, que indica que la variable de tipo a no puede representar a un tipo cualquiera, sino a un tipo que pertenezca a los tipos de clase Eq, que son los que se pueden comparar.
hayun0 :: [Int] → Bool, que dada una lista devuelve True si hay algún 0 en la lista.
hayun0 :: [Int] -> Bool hayun0 [] = False hayun0 (x:xs) = x == 0 || hayun0 xs
existe :: a → [a] → Bool, que dado un elemento y una lista, devuelve True si el elemento está en la lista. Fíjense que se trata de una generalización del ejercicio anterior.
existe :: a -> [a] -> Bool existe e [] = False existe e (x:xs) = e == x || existe e xs
Escribir la función que calcula la Sucesión de Fibonacci, fib :: Int → Int, que se define así: fib (n+2) = fib (n+1) + fib n.
fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n+2 = fib (n+1) + fib n
sumaPares :: [(Int, Int)] → Int, que dada una lista de pares de números, devuelve la sumatoria de todos los números de todos los pares.
sumaPares :: [(Int, Int)] -> Int sumaPares [] = 0 sumaPares ((x,y):xs) = x + y + sumaPares xs
repetir :: Int → a → [a] que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones.
repetir :: Int -> a -> [a] repetir 0 a = [] repetir n a = a : repetir (n-1) a
esMultiploLista :: Int → [Int] → [Bool] que dado un entero n y una lista de enteros xs devuelve una lista de booleanos que indica si n es múltiplo de cada uno de los elementos de la lista xs.
esMultiploLista :: Int -> [Int] -> [Bool] esMultiploLista n [] = [] esMultiploLista n (x:xs) = mod n x == 0 : esMultiploLista n xs
sumaPares :: [Int] → Int, que suma sólo los elementos pares de una lista.
sumaPares :: [Int] -> Int
sumaPares [] = 0
sumaPares (x:xs) | mod x 2 == 0 = x + sumaPares xs
| otherwise = sumaPares xs
sumaPares' :: [Int] -> Int sumaPares' xs = sumatoria (soloPares xs)
estudiantesMayores35 :: [(String,Int,Int,Int)] → Int, que dada una lista de cuatro-uplas (String,Int,Int,Int) que se corresponden con (Nombre,Año-Nacimiento,Año-Inicio-Estudios,Año-Fin-Estudios), devuelve la cantidad de estudiantes que fueron mayores de 35 años en algún momento en el transcurso de sus estudios.
estudiantesMayores35 :: [(String,Int,Int,Int)] -> Int
estudiantesMayores35 [] = 0
estudiantesMayores35 ((n,nac,ini,fin):xs) | (fin - nac) > 35 = 1 + estudiantesMayores35 xs
| otherwise = estudiantesMayores35 xs
estudiantesMayores35' :: [(String,Int,Int,Int)] -> Int
estudiantesMayores35' xs = longitud (mayores35 xs)
mayores35 :: [(String,Int,Int,Int)] -> [String]
mayores35 [] = []
mayores35 ((n,nac,ini,fin):xs) | (fin - nac) > 35 = n : estudiantesMayores35 xs
| otherwise = estudiantesMayores35 xs
listaMayorQue :: Int → a → Bool, que dado un número n y una lista de listas, devuelve True si todas las listas de la lista tienen por lo menos n elementos.
listaMayorQue :: Int -> [[a]] -> Bool listaMayorQue n [] = True listaMayorQue n (x:xs) = n <= (longitud x) && listaMayorQue n xs
totalSueldos :: [Float] → Float, que dada una lista con el monto de cada uno de los sueldos que paga una empresa, aplica una suba del 5% a todos los sueldos y devuelve el monto total que gastará la empresa en sueldos.
totalSueldos :: [Float] -> Float totalSueldos [] = 0 totalSueldos (x:xs) = porCiento 5 x + x + totalSueldos xs
totalSueldos' :: [Float] -> Float totalSueldos' xs = sumatoria (incrementaPorCiento 5 xs) incrementaPorCiento :: Float -> [Float] -> [Float] incrementaPorCiento n [] = [] incrementaPorCiento n (x:xs) = porCiento n x + x : incrementaPorCiento n xs
impuestoLujo :: [(String,Float)] → [(String,Float)], que dada una lista de tuplas (Producto, Precio), aplica un impuesto del 21% extra a todos los productos que salen más de 10000 pesos.
impuestoLujo :: [(String,Int)] -> [(String,Int)]
impuestoLujo [] = []
impuestoLujo ((n,x):xs) | x > 10000 = (n,(porCiento 21 x + x)) : impuestoLujo xs
| otherwise = (n,x) : impuestoLujo xs
cuentaInteresantes :: [(String,Bool)] → Int, que cuenta la cantidad de libros interesant es que hay en una biblioteca. Los libros están representados mediante una tupla (String, Bool), que contiene el título del libro en el primer elemento y en el segundo el elemento contiene True si el libro es interesante y False si no lo es.
cuentaInteresantes :: [(String,Bool)] -> Int
cuentaInteresantes [] = 0
cuentaInteresantes ((x,y):xs) | y == True = 1 + cuentaInteresantes xs
| otherwise = cuentaInteresantes xs
cuentaInteresantes' :: [(String,Bool)] -> Int
cuentaInteresantes' xs = sumatoria (interesantes xs)
interesantes :: [(String,Bool)] -> [String]
interesantes [] = []
interesantes ((x,y):xs) | y == True = x : cuentaInteresantes xs
| otherwise = cuentaInteresantes xs
edadPromedio :: [(String,Int)] → Int, que dada una lista de pares (nombre,edad), retorna el promedio de edad de las personas.
edadPromedio :: [(String,Int)] -> Int edadPromedio xs = (sumatoriaSegundo xs) / (longitud xs) sumatoriaSegundo :: [(String,Int)] -> Int sumatoriaSegundo [] = 0 sumatoriaSegundo ((x,y):xs) = y + sumatoriaSegundo xs
A partir de la siguiente base de conocimiento en prolog, crear las reglas necesarias para que el intérprete nos diga si una persona alérgica a la frutilla puede comer helado de frutilla:
esAlérgico(pepe,kiwi). esAlérgico(juan,frutilla). esAlérgico(maría,melocotón). tiene(helado,Y) :- helado(Y). tiene(torta,Y) :- torta(Y).
Creamos la regla:
puedeComer(X,Y) :-
( esAlérgico(X,Z) , not(tiene(Y,Z)) ) ,
( not(esAlérgico(X,W)) , tiene(X,W) ).
A partir de la siguiente base de conocimiento en prolog, crear las reglas necesarias para que el intérprete nos diga qué alimento puede comer cada animal:
herbívoro(vaca). herbívoro(oveja). carnívoro(león). hortaliza(tomate). hortaliza(zanahoria). fruta(manzana). pescado(besugo). carne(salchicha). fideos(spaghetti).
Creamos las reglas:
planta(X) :- hortaliza(X) ; fruta(X) ; fideos(X).
animal(X) :- carne(X) ; pescado(X) ; herbívoro(X) ; carnívoro(X).
come(X,Y) :-
( herbívoro(X) , planta(Y) ) ;
( carnívoro(X) , animal(Y) ) .
soloEntre0y9 :: [Int] → [Int], que dada una lista de enteros devuelve una lista que contiene sólo aquellos miembros de la lista original mayores o iguales que 0 y menores o iguales que 9.
soloEntre0y9 :: [Int] -> [Int]
soloEntre0y9 [] = []
soloEntre0y9 (x:xs) | 0 <= x && x <= 9 = x : soloEntre0y9 xs
| otherwise = soloEntre0y9 xs
sumatoriaEsPar:: [Int] → Bool, que dada una lista de enteros, suma cada uno de sus elementos y devuelve True si el resultado es par y False si es impar.
sumatoriaEsPar :: [Int] -> Bool sumatoriaEsPar xs = mod (sumatoria xs) 2 == 0
cuantos0 :: [Int] → Int, que dada una lista de enteros devuelve un entero con la cantidad de números 0 que hay en la lista original.
cuantos0 :: [Int] -> Int
cuantos0 xs = longitud (solo 0 xs)
solo :: Eq a => a -> [a] -> [a]
solo e [] = []
solo e (x:xs) | e == x = x : solo e xs
| otherwise = solo e xs
paresHasta :: Int → [Int], que dado un número devuelve la lista de pares que hay desde 0 hasta ese número.
paresHasta :: Int -> [Int]
paresHasta n = paresHasta' n 0
paresHasta' :: Int -> Int -> [Int]
paresHasta' n m | n <= m = []
| otherwise = m : paresHasta' n (m+2)
iguales :: Eq a ⇒ [a] → [a] → Bool que decide si dos listas son iguales.
iguales :: Eq a => [a] -> [a] -> Bool iguales [] [] = True iguales (x:xs) (y:ys) = x == y && iguales xs ys
encuentraEstafador' :: [Int] → [Int] → [Int], que opera sobre dos listas ordenadas de menor a mayor, y aprovecha este hecho para recorrerlas una sola vez.
encuentraEstafador' :: [Int] -> [Int] -> [Int]
encuentraEstafador' [] [] = []
encuentraEstafador' [] (y:ys) = []
encuentraEstafador' (x:xs) [] = []
encuentraEstafador' (x:xs) (y:ys) | x > y = encuentraEstafador' (x:xs) ys
| x < y = encuentraEstafador' xs (y:ys)
| x == y = x : encuentraEstafador' xs ys
encuentraEstafador'' :: [Int] -> [Int] -> [Int]
encuentraEstafador'' (x:xs) (y:ys) | x > y = encuentraEstafador'' (x:xs) ys
| x < y = encuentraEstafador'' xs (y:ys)
| x == y = x : encuentraEstafador'' xs ys
encuentraEstafador'' _ _ = []
cuantosCumplen :: (Int → Bool) → [Int] → Int, que dado un predicado p y una lista de enteros xs, cuenta cuántos elementos de la lista cumplen con p.
cuantosCumplen :: (Int -> Bool) -> [Int] -> Int
cuantosCumplen p [] = 0
cuantosCumplen p (x:xs) | p x = 1 + cuantosCumplen p xs
| otherwise = cuantosCumplen p xs
cuantosCumplen' :: (Int -> Bool) -> [Int] -> Int cuantosCumplen' p xs = sumatoria (filter p xs)
Redefinir todos los ejercicios recursivos en listas propuestos en las clases anteriores aplicando las generalizaciones filter, map y foldr. En algún caso no es posible aplicar estas generalizaciones.
mayor(clara,esteban). mayor(esteban,paula). mayor(paula,marcos). mayor(marcos,elena).
mayorQue(X,Y) :- mayor(X,Y). mayorQue(X,Y) :- mayor(X,Z) , mayorQue(Z,Y).
conectadas(Tarragona,Barcelona). . ¿Cómo sería un programa que nos ayudara a saber si podemos llegar de una ciudad a otra, es decir, si existe una lista de conexiones que nos lleve de una ciudad a otra, o bien eso es imposible? La solución, en la clase 8.Encontrarán una posible solución al problema de recomendar amigos en una red social tipo facebook en la clase 9.
También damos una posible solución al problema de calcular el porcentaje de estudiantes que aprueban o promocionan la materia en la clase 9.
ingredientes(tortilla,[huevos,papas,cebolla,sal,aceite,pimienta]). ingredientes(papafrita,[papas,aceite,sal]). ingredientes(huevofrito,[huevos,aceite,sal]). ingredientes(pizza,[prepizza,salsa,queso]). ingredientes(asado,[carne]). ingredientes(crema,[leche,huevos,azúcar,maicena,canela]). tengo(sal). tengo(azúcar). tengo(pimienta). tengo(canela). tengo(huevos). tengo(leche). tengo(queso). tengo(maicena). puedoCocinar(Platillo) :- ingredientes(Platillo,Ingredientes) , tengoTodos(Ingredientes). tengoTodos([]). tengoTodos([I|Ingredientes]) :- tengo(I) , tengoTodos(Ingredientes).
queda(jeringas,8). queda(vendas,20). queda(curitas,30). minimo(jeringas,5). minimo(vendas,10). minimo(curitas,20). bajoMinimo(Insumo,Cantidad) :- queda(Insumo,Reserva) , minimo(Insumo,Minimo) , (Reserva - Cantidad) =< Minimo .
mamifero(vaca). mamifero(delfín). mamifero(nutria). acuatico(delfín). acuatico(nutria). pez(trucha). pez(guppi). viviparo(guppi). terrestre(X) :- mamifero(X) , not(acuatico(X)). acuatico(X) :- pez(X). viviparo(X) :- mamifero(X). oviparo(X) :- pez(X) , not(viviparo(X)).
El problema del máximo común divisor se soluciona muy fácilmente si por azar sabemos que hay una recetita maravillosa que dice así: dados dos números, si uno es divisor del otro, entonces ese será el máximo común divisor. Si no, se resta el número menor al mayor y volvemos a comprobar si uno es divisor del otro. Si no, se resta el menor al mayor, y así hasta llegar a algún caso en el que uno de los dos números sea divisor del otro.
mcd :: Int -> Int -> Int
mcd a b | mod a b == 0 = b
| mod b a == 0 = a
| otherwise = mcd (min a b) ((max a b) - (min a b))
El problema de las n reinas (perdón, no eran 9 :-} ). Está muy bien explicado en el blog de programación lógica de un estudiante de informática, tanto para haskell como para prolog.
El problema de misioneros y caníbales está bien explicado como caso particular de un problema de búsqueda en estas filminas sobre búsqueda.