Considere um labirinto com as seguintes propriedades: cada posição no labirinto é caracterizada por duas coordenadas (X,Y), ambas inteiras. O labirinto tem uma entrada, por convenção na posição (1,1), e uma saída -- já adivinhou: terá de encontrar as coordenadas da saída. O labirinto tem um estado interno chamado posicao_corrente, que é colocado, no início, na posição de entrada e que representa a posição onde estamos no labirinto. No entanto, não temos acesso directo a este estado interno! Podemos interrogar o labirinto por meio de dois predicados: move/2 e fim/0. O predicado fim/0 retorna ``sim'' se, e sómente se, posicao_corrente coincide com a saída. O predicado move/2 é um pouco mais complicado. Chamamo-lo com os argumentos instanciados, representando uma posição. Por exemplo
?- move(3,4).
Se o labirinto for tal, que possamos ir, num único passo, da posicao_corrente
para a posição (3,4), o predicado retorna ``sim'' e actualiza o estado interno posicao_corrente
para (3,4). Se não for possível ir num passo da posicao_corrente para (3,4),
o predicado falha (retorna ``não'') e o estado interno posicao_corrente é
reinicializado para a posição de entrada, isto é, somos colocados, de novo, na
posição inicial, quando tentamos fazer um passo não admissível. O mesmo acontece se
chamarmos move/2 com argumentos por instanciar ou com argumento(s)
``incorrecto(s)''. Para limitar as possibilidades, um passo directo é apenas possível
para uma posição adjacente: as coordenadas X ou Y diferem de uma
unidade.
Deve escrever um predicado saida/2 que será chamado com os argumentos livres
(por instanciar) e cujos argumentos serão, em caso de sucesso, instanciados com as
coordenadas da saída do labirinto. O tamanho do labirinto não é dado (o predicado move/2
falha quando dada uma posição não existente).
Existem duas subtilezas neste problema: