Guía de Ejercicios en Prolog

Lección 5 - Laberinto

Tenemos el siguiente laberinto:

que se puede representar mediante la siguiente base de conocimientos, al estilo de un grafo:

%
% archivo: laberinto.pl
%

conectado(inicio, 2).
conectado(1, 7).
conectado(2, 3).
conectado(2, 8).
conectado(3, 4).
conectado(3, 9).
conectado(4, 10).
conectado(5, 6).
conectado(5, 11).
conectado(7, 13).
conectado(8, 9).
conectado(10, 16).
conectado(11, 17).
conectado(12, 18).
conectado(13, 14).
conectado(14, 15).
conectado(14, 20).
conectado(15, 21).
conectado(16, 22).
conectado(17, 23).
conectado(18, 24).
conectado(19, 25).
conectado(20, 26).
conectado(21, 22).
conectado(23, 29).
conectado(30, 36).
conectado(25, 31).
conectado(26, 27).
conectado(27, 28).
conectado(28, 34).
conectado(30, 36).
conectado(31, 32).
conectado(32, fin).
conectado(32, 33).
conectado(33, 34).
conectado(34, 35).
conectado(35, 36).

conectado_a(X, Y) :- conectado(Y, X).
conectado_a(X, Y) :- conectado(X, Y).

Fíjate que se los últimos dos predicados convierten al grafo dirigido (i.e. uno que posee arcos) en un grafo no-dirigido (i.e. que posee aristas). Sin embargo, la descripción de la propiedad de simetría tuvo que realizarse por medio de un predicado auxiliar conectado_a para evitar loops infinitos en las consultas.

Es decir, si hubiésemos descrito la simetría por medio de:

...
conectado(34, 35).
conectado(35, 36).

conectado(X, Y) :- conectado(X, Y).

Se generarían loops infinitos en las consultas.

Escribe un predicado resolver_laberinto/0 que resuelve el laberinto, partiendo desde inicio y finalizando en fin, imprimiendo la solución en pantalla. Ojo: ¡no te olvides de evitar pasar dos veces por el mismo lugar!