Paradigmas de Lenguajes de Programación
1◦ cuatrimestre de 2008
Trabajo Práctico 2 - Programación Lógica
Comequesos
Fecha de entrega: jueves 5 de junio, hasta las 21 hs.
En este trabajo práctico se debe definir un conjunto de hechos y reglas que nos permitan
conocer propiedades sobre laberintos. Los laberintos sólo pueden contener un ratón, gatos y
pedacitos de queso. El ratón recorre el laberinto comiendo los pedacitos de queso y evitando
encontrarse con los gatos. Si el ratón llega a encontrarse con un gato, muere. Además, el ratón
no puede continuar su recorrido si llega a salirse de los lı́mites del laberinto.
El objetivo de este trabajo práctico es escribir predicados que nos permitan averiguar
propiedades sobre los recorridos que realiza el ratón en el laberinto.
1. Laberintos y recorridos
Todos los laberintos deben ser rectangulares y tener al menos una casilla. Cada posición del
laberinto puede tener de cero a tres paredes a los costados; no se permiten casillas totalmente
cerradas. Observar que un laberinto donde algunas de las casillas no tienen paredes también
es un laberinto válido.
Las posiciones en el laberinto se representan mediante un par de números naturales,
comenzando desde cero. Si se considera al laberinto como una matriz, la primera coordenada
corresponde al número de la fila, y la segunda a número de la columna. La casilla (0, 0) es la
esquina noroeste del laberinto y está representada por el primer elemento de la primer lista
del laberinto.
Cada posición del laberinto puede contener un gato o un pedacito de queso, o puede estar
vacı́a. La posición donde comienza el recorrido el ratón se especificará en forma separada a la
estructura del laberinto.
Figura 1: Un laberinto de ejemplo.
Un laberinto se representará con una lista de filas. Cada fila será una lista de casillas. Una
casilla se representará con la siguiente estructura:
casilla(Izq, Arr, Der, Aba, Personaje)
Página 1 de 4
Paradigmas de Lenguajes de Programación
1◦ cuatrimestre de 2008
Las direcciones Izq, Arr, Der y Aba indican la presencia de paredes en cada una de esas
direcciones. La presencia de una pared se indica mediante un 1, y su ausencia, mediante un
0.
En Personaje se debe indicar si en la casilla hay un gato o un pedacito de queso, o si
está vacı́a. Por lo tanto, los valores posibles para Personaje son: gato, queso, vacio.
Por ejemplo, si queremos definir el laberinto de la figura anterior, serı́a:
[[casilla(1,1,0,0,queso),
casilla(0,1,1,1,vacio),
casilla(1,1,0,0,vacio), ...], ...]
El ratón comienza el recorrido desde una posición dada y a partir de allı́ trata de avanzar
por el laberinto mientras no se encuentre con un gato o salga del laberinto (en cualquiera
de estos casos, finaliza el recorrido del ratón). Durante el recorrido, el ratón puede moverse
hacia arriba, abajo, izquierda o derecha, respetando la estructura del laberinto. Si el ratón se
encuentra en una posición en la que hay un pedacito de queso, se lo come.
Los recorridos se representan con una lista de posiciones por las que pasa el ratón. El
recorrido incluye la posición inicial del ratón y la posición final. Si el ratón se encuentra con
un gato en una posición del laberinto, el recorrido concluye en dicha posición. Un recorrido
tampoco puede continuar si el ratón sale del laberinto.
Por ejemplo, los siguientes son algunos de los recorridos válidos en el laberinto de la figura:
[(2,2),(3,2),(4,2)] Sale del laberinto
[(2,2),(3,2),(3,3),(3,4)] Come un queso y lo mata un gato
[(2,2),(2,3),(2,2),(2,3)] Avanza y vuelve sobre sus pasos
2. Predicados pedidos
Se pide definir los siguientes predicados, respetando la instanciación pedida y de tal manera
que no se cuelguen ni se devuelvan soluciones repetidas:
1. esLaberinto(+Laberinto)
Este predicado verifica que el argumento sea un laberinto válido. Notar que esto incluye
la verificación de coherencia entre las paredes de las casillas y que las casillas estén
vacı́as, tengan gatos o pedacitos de queso.
2. recorrido(+Laberinto, +PosicionInicial, -Recorrido, -CantQueso)
Este predicado verifica que el ratón puede realizar un recorrido en un laberinto válido
desde la posición inicial consumiendo exactamente la cantidad de queso indicada. Ob-
servar que una vez que el ratón consume el queso de una casilla, si vuelve a pasar por
ella ya no hay más queso que comer en la misma.
Recordar que un recorrido no puede continuar si el ratón sale del laberinto o lo come
un gato.
Página 2 de 4
Paradigmas de Lenguajes de Programación
1◦ cuatrimestre de 2008
Por otra parte observar que los recorridos pueden ser arbitrariamente largos y eventual-
mente se deben devolver todos. En otras palabras, este predicado podrı́a tener infinitas
soluciones distintas.
3. recorridoSinRepetidos(+Laberinto, +PosicionInicial, -Recorrido, -CantQueso)
Igual al predicado anterior pero el ratón no puede pasar dos veces por la misma casilla
en el transcurso del recorrido.
En este caso no hay infinitos recorridos distintos, por lo tanto el intérprete debe devolver
No cuando ya se hayan presentado todos ellos.
4. comeMucho(+Laberinto, +PosicionInicial, -Recorrido)
Este predicado verifica que el ratón puede realizar un recorrido sin repetidos en un
laberinto válido desde la posición inicial consumiendo la mayor cantidad posible de
queso.
Tal como en el ejercicio anterior, observar que no hay infinitos recorridos ya que el ratón
no puede pasar dos veces por el mismo casillero.
5. comeTodo(+Laberinto, +PosicionInicial, -Recorrido)
Igual al predicado anterior pero verifica además que el ratón consuma todo el queso del
laberinto.
Nuevamente el ratón no tiene permitido repetir casilleros.
6. sale(+Laberinto, +PosicionInicial, -Recorrido)
Este predicado verifica que el ratón puede realizar un recorrido en un laberinto válido
desde la posición inicial hasta salir del mismo.
Tal como en el ejercicio 2, se permite que el ratón repita casilleros, con lo cual puede
haber infinitas soluciones. Observar que si el ratón no tiene niguna forma de salir del
laberinto, se debe programar el predicado de forma tal que el intérprete diga no.
2.1. Juego adicional (opcional)
meJuegoPor(-N)
Este predicado es verdadero si N es el número entero por el que se juega el grupo. El grupo
que elija el número que resulte más cercano a la mediana de todos los números elegidos por
todos los grupos será ganador de un premio sorpresa. En caso de empate se eligirá al menor
de ellos y de seguir habiendo empate se sorteará un ganador usando una moneda (en caso de
que consigamos una).
Por ejemplo:
?- meJuegoPor(N).
N = 4
No
Página 3 de 4
Paradigmas de Lenguajes de Programación
1◦ cuatrimestre de 2008
3. Condiciones de aprobación
El principal objetivo de este trabajo es evaluar el correcto uso del lenguaje PROLOG de
forma declarativa para resolver el problema planteado. Se pedirá un pequeño informe donde
se explique cada predicado definido, aclarando cómo se relaciona, en caso de hacerlo, con los
demás predicados (por ejemplo, indicando los predicados que hacen referencia a ellos) y cómo
interviene en la solución del problema. También se debe explicitar cuáles de los argumentos
de los predicados auxiliares deben estar instanciados usando + y -.
Observar que el ejercicio opcional es opcional.
4. Pautas de entrega
Se debe entregar el código impreso con la implementación de los predicados pedidos. Cada
predicado debe contar con un comentario donde se explique su funcionamiento. Asimismo, se
debe enviar un mail conteniendo el código fuente Prolog a la dirección de correo electróni-
co plp-docentes@[Link]. Solamente el código Prolog comentado (no debe incluirse
el informe) debe acompañar el mail en forma de archivo adjunto. El mismo debe poder
ejecutarse en SWI-Prolog (indicar claramente cómo se debe ejecutar).
A. Algunos predicados y metapredicados definidos en SWI-
Prolog
Esta sección contiene algunos predicados y metapredicados ya definidos en la actual imple-
mentación de SWI-Prolog que pueden ser de utilidad para el desarrollo de trabajo práctico.
La descripción de los mismos la pueden hallar en la ayuda de SWI-Prolog (invocada con el
predicado help).
nth0(-N, -List, -Elem)
member(-Elem, -List)
append(-List1, -List2, -List3)
sublist(+Pred, +List1, -List2)
subset(+Subset, -Set)
maplist(+Pred, -List)
maplist(+Pred, -List1, -List2)
maplist(+Pred, -List1, -List2, -List3)
setof(+Template, +Goal, -Set)
not(+Goal)
Página 4 de 4