Next: Árvore de Natal Up: Enunciados

Caminho

Num tabuleiro quadrado de tamanho N, por exemplo 4, dado pelo facto

         tamanho(4).

existe um ponto de partida (que é sempre o quadrado 1, 1) e um ponto de chegada, dado, por exemplo, pelo facto

         goto(1,4,f). % f = fim (do caminho)

Existe um caminho correcto entre o ponto de partida e o ponto de chegada e ele está marcado: cada quadrado do caminho contém a informação necessária para determinar o próximo quadrado do caminho, na forma de um facto:

goto(1,1,c). % significa que ao quadrado 1,1 sucede o quadrado 1,2 (c = cima)
goto(1,2,c).
goto(1,3,d). % significa que ao quadrado 1,3 sucede o quadrado 2,3 (d = direita)
goto(2,3,d).
goto(3,3,b). % significa que ao quadrado 3,3 sucede o quadrado 3,2 (b = baixo)
goto(3,2,b).
goto(3,1,d).

Um e teria significado, obviamente, 'esquerda'. A informação acima representa o tabuleiro:

Claro que não existe qualquer dificuldade em encontrar o caminho correcto de 1, 1 para 1, 4 em tal tabuleiro. Contudo, um vírus maligno no meu computador (para o qual, infelizmente, ainda não existe antídoto) remove informação do tabuleiro sempre que eu crio um. É por isso que vos estou a pedir ajuda. O vírus apaga alguns factos goto/3, de maneira que o caminho não fica completamente representado. Depois de algumas tentativas, cheguei à conclusão que, ainda assim, o vírus não é exageradamente maligno. Com efeito ele nunca remove a informação de dois quadrados vizinhos no caminho; nunca remove o ponto de chegada; e, no máximo, dois vizinhos de um quadrado removido pertencem ao caminho correcto (quadrados que se tocam na diagonal não são considerados vizinhos). Desde modo, ainda é fácil encontrar o caminho. Todavia, hoje fui infectado por um segundo vírus, mais maligno, que introduz informação para cada quadrado não no caminho e de tal modo que se seguirmos essa informação, das duas uma: ou andamos às voltas em círculos; ou saímos para fora do tabuleiro (em particular, não encontramos quadrados 'vazios'). De seguida mostro o tabuleiro acima depois de infectado pelos dois vírus:

O que vos peço é que escrevam um predicado caminho/1 que nos dê o caminho correcto, como uma lista começando por (1,1) e acabando no ponto de chegada. A lista deve estar ordenada ao longo do caminho. Assim, para o exemplo acima, devemos obter:

         ?- caminho(C).
            C = [(1,1),(1,2),(1,3),(2,3),(3,3),(3,2),(3,1),(4,1)]

Next: Árvore de Natal Up: Enunciados