18. Ideia de Ariadne

Na mitologia grega, Ariadne era uma princesa cretense e filha do rei Minos de Creta. Ariadne é conhecida, entre outras coisas, por ter dado uma baita ideia para que Teseu se guiasse dentro de uma labirinto e derrotasse o Minotauro.

Bem, uma das versões do mito diz que … o rei Minos atacou Atenas depois que seu filho, Androgeu, foi morto em Atenas. Após terem sido derrotados por Minos, como reparação, os atenienses concordaram em de \(x\) anos em \(x\) anos oferecerem como sacrifício jovens atenienses ao Minotauro que habitava no centro de um labirinto. O valor de \(x\) depende da versão do mito.

Minos colocou sua filha Ariadne no comando do labirinto onde eram feitos sacrifícios. Um dos sacrifícios incluiu o ateniense Teseu, filho do rei Egeu, que havia se voluntariado para entrar no labirinto para matar o Minotauro. Ariadne se apaixonou por Teseu à primeira vista ❤️ 🤟🏼 e forneceu-lhe uma espada 🗡️ para matar o Minotauro e um novelo de linha 🧵, o fio de Ariadne, para que ele pudesse se guiar no labirinto e encontrar a saída depois de ter derrotado o Minotauro. Teseu matou o Minotauro e é na mitologia grega é um grande herói de Atenas.

Não tem nada a ver, mas… depois… Ariadne foi abandonado por Teseu 💔 na ilha de Naxos, onde Dionísio a viu dormindo, se apaixonou 💗 🤟🏼 por Ariadne e mais tarde se casou 💒 com ela. Dionísio não tem nada a ver com que vamos discutir mais adiante, mas a ideia da Ariadne… tem tudo a ver!

18.1. Destino

O lugar de destaque, de muito destaque, mesmo que visitaremos nessa nossa jornada, neste capítulo é a baita ideia de Ariadne em usar um fio 🧵 para que Teseu registrasse as rotas percorridas. A cada passo feito por Teseu no labirinto ele desenrolava o fio, deixando-o preso ao chão. No labirinto os corredores sem fio algum eram aqueles em que Teseu não havia passado, os corredores com um fio eram aqueles em que Teseu havia percorrido em uma das direções e os corredores com dois fios eram os em que Teseu havia percorrido em ambas as direções depois de ter fracassado, ter chegado a um beco sem saída, em uma tentativa de rota.

Para Teseu o fio de Ariadne foi fundamental para não andar pelo labirinto desorientado, sem se perder, e para, depois de derrotar o Minotauro, voltar facilmente 🍰 ao portal de entrada do labirinto. O fio serviu para marcar físicamente todos os seus passos 👣, todas as suas decisões tomadas ao longo caminho. Essas marcas ou registros foram usadas para não repetir rotas já tentadas e para que a cada momento houvesse a possibilidade de retroceder até algum determinado ponto em que houvesse algum outro caminho ainda não tentado.

Um mecanismo com o fio de Ariadne pode ser aplicado a problemas em que a solução é formada por uma série de passos em que opções ou decisões são feitas de tempos em tempos. Um solução, caso exista, é alcançada por meio de uma tentativa exaustiva de todas as rotas disponíveis, sem que tenhamos o risco de revisitar rotas já tentadas. A ideia central do fio de Ariadne aplicado a um problema qualquer é a criação e manutenção de registros 📝, um log, que nos permita saber a cada instante quais são as opções disponíveis que ainda não foram exploradas. Uma das funções dos registros é permitir o retrocesso, isto é, reverter decisões anteriores e tentar novas alternativas (que as vezes recebe um nome bonito de backtracking). Tendo em mão 👐🏽 os registros 📖, a estratégia do algoritmo em qualquer ponto em que uma decisão deve ser tomada é basicamente a seguinte.

Se os registros 📖 indicam que desse ponto

• não há opções que possivelmente nos levem ao sucesso, ou seja, a uma solução, registramos ✍️ esse ponto como sendo de fracasso e voltamos ao último local em que os registros indicam que ainda há opções a serem consideradas e prosseguimos daquele ponto;

• há ainda opções a serem consideradas, fazemos uma escolha arbitrária entre aquelas que ainda não foram registradas ✍🏾 como fracassadas e seguimos a opção escolhida até onde for possível.

Este algoritmo terminará ao encontrarmos uma solução ou ao verificarmos que os registros 📖 nos dizem que todas as possíveis opções iniciais nos levarão ao fracasso, pois todas as opções iniciais foram registradas ✍🏼 como fracasso. Neste último caso, não há solução. Se embora tenhamos encontrado uma solução desejarmos realizar um exame minucioso, podemos registrar ✍🏼 o sucesso, voltar à decisão anterior e continuar como se nunca tivéssemos encontrado uma solução. Nesse caso o algoritmo consideraria todas as opções e encontraria todas as soluções.

A ideia do fio de Ariadne é utilizada em algoritmos fundamentais e cotidianamente utilizados em computação como a busca em largura (Breadth-first search) e a busca em profundidade (Depth-first search). O que veremos nesse capítulo é essencialmente a busca em profundidade. A busca em largura ficará para um dos próximos passeios.

18.2. Introdução

Ariadne deu a Teseu uma espada 🗡️ e um carretel com linha 🧵. Apesar da espada ter sido muito útil para Teseu derrotar o Minotauro, estamos totalmente interessados no papel que o carretel de linha 🧵 teve nessa aventura.

Para entendermos o problema que estamos visitando e inspecionarmos principalmente a estratégia empregada para solucioná-lo investigaremos 🕵🏽 bem cuidadosamente 🔍 👁️ a animação a seguir. Na animação o herói ateniense Teseu é mostrado entrando no labirinto, procurando o Minotauro e saindo do labirinto após ter encontrado e derrotado o Minotauro. Teseu é interpretado pela tartaruga 🐢 que está se movimentando pelo labirinto. O papel do Minotauro é feito pela tartaruga 🐢 que está parada no labirinto. Contemplemos :nerd_face: um pouco a animação antes de prosseguirmos com nossa diversão.

O livro de anotações 📘 em que são registradas ✏️ todas as decisões, todos passos, tomadas por Teseu é o próprio labirinto. 😮

No labirinto os retângulos totalmente preenchido, pintados

🟧, são as suas paredes. Posições livres são os corredores nos quais Teseu ainda não passou e são indicadas por um espaço vazio 🔲, exceto a posição onde está o Minotauro 🐢. As demais posições tem uma marca em seu interior que pode ser um círculo ⚫, um quadrado 🟥, ou um triângulo 🔺.

Os círculos ⚫, quadrados 🟥 e triângulos 🔺 são os registros 📝 feitos no caderno de anotações 📖 que é o labirinto. Os círculos e os quadrados fazem as vezes do fio de Ariadne utilizado para marcar os corredores percorridos por Teseu na sua procura pelo Minotauro. A primeira vez que Teseu percorre um corredor deixa um círculo. Depois de Teseu passar por um corredor, explorar todos os corredores alcançáveis a partir deste, e retroceder, Teseu marca esse corredor com um quadrado 🟥. Em cada momento da sua busca Teseu olha para as quatro direções adjacentes, NORTE, SUL, LESTE e OESTE. Durante a sua procura pelo Minotauro, em cada uma das direções, Teseu vê 👀 uma parede, ou um corredor que ele:

• ainda não percorreu 🔲;

• percorreu apenas uma vez ⚫ e que mostra a Teseu de onde veio e um caminho direto até a saída, para quando ele decidir que está na hora de vazar 🏃🏿‍♂️; ou

• percorreu em ambas a direção 🟥 e que levou a um beco sem saída e sem Minotauro.

Com isso podemos entender a baita ideia da Ariadne! O seu fio seria usado por Teseu para registrar 📚 os corredores percorridos e permitem a ele retroceder até um ponto onde já passou a procurar de outros corredores ainda não percorridos, tudo isso em busca do Minotauro. Um fato super bacana, relação invariante da ideia, é que a todo momento os círculos ⚫ mostram a Teseu um caminho direto e reto de sua posição até a saída do labirinto 😮‍💨. Os triângulos mostram os corredores em que Teseu passou até a saída após, para a alegria dos atenienses, ter derrotado o Minotauro.

De uma forma meio vaga o problema que trataremos nesse capítulo será o de Teseu.

Problema (de Teseu): Dado um labirinto com o Minotauro e uma posição inicial para Teseu, encontrar um caminho de Teseu até o Minotauro.

A solução desse problema é frequentemente adaptada para resolver problemas em que a solução pode ser obtida percorrendo-se de maneira sistemática uma estrutura formada por objetos que possuem uma relação de vizinhança que nos diz, para cada objeto, quem são seus vizinhos. 😖 No caso do nosso labirinto os objetos são posições e a relação de vizinhança é dada através da adjacência: os vizinhos de uma posição são as posições horizontais e verticais adjacentes a ela. 🤔

A ideia de Ariadne poderia ser usado por Teseu para percorrer todos os corredores do labirinto sem se perder, como pode ser observado quando examinamos a animação abaixo.

As animações nesta seção são o resultado de pequenas alterações feitas no código no capítulo Recursão, seção 4.11. Explorando um Labirinto, do livro Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python.

18.3. Labirintos

Para começar precisamos fazer um combinado do que será para nós um labirinto, como iremos representá-lo e como poderemos manipulá-lo. Nesse seção vamos dizer quais são as regras do jogo.

Para nós um labirinto será representado por meio de um objeto que irá retratar um região retangular dividida em nlins linhas e ncols colunas. Cada posição desse labirinto é referenciada por um par de índices [lin,col] em que lin indica a linha e col indica a coluna da posição. Assumiremos que os elementos das posições serão caracteres, strings de comprimento 1. Cada um desses caracteres terá seu significado especifico, serão códigos. Usaremos os seguintes apelidos para esses códigos.

Listing 18.1 marcas.py

# apelidos para as marcas usadas nos registros do labirinto
PAREDE    = '#'
TESEU     = 'T'
MINOTAURO = 'M'
LIVRE     = ' '
FIO       = '*'
BECO      = 'b'
TESEU_MINOTAURO = '$'
MINOTAURO_DERROTADO = 'X'
SAIDA     = 's'

Para criar um objeto Labirinto fazemos

In [1]: from labirinto import Labirinto

In [2]: lbrnt = Labirinto("deadalus.txt")

In [3]: type(lbrnt)
Out[3]: labirinto_str.Labirinto

O argumento daedalus.txt é o nome de um arquivo com os caracteres que estão em cada posição do labirinto apelidado de lbrnt. O arquivo daedalus.txt foi usado na primeira animação da introdução e seu conteúdo é

In [4]: more deadalus.txt # exibe o conteúdo do arquivo deadlus.txt
######################
#   #   ## ##     #  T
# #   #       ### # ##
# # #  ##  ####   # ##
### ######    ### #  #
#          ##  ##    #
##### ######   ##### #
#     #   #######  # #
# #######   #  M##   #
#         #   #  # ###
################## ###

No arquivo deadalus.txt os caracteres são aqueles apelidados no arquivo marcas.py:

• PAREDE indica parede;

• TESEU mostra a posição em que Teseu está;

• MINOTAURO é onde está o Minotauro;

• LIVRE apresenta um corredor não explorado por Teseu;

• FIO aponta um corredor que Teseu percorreu em apenas uma das direções, apenas uma vez;

• BECO é um corredor que conduz a um beco sem saída, Teseu percorreu esse corredor em ambas as direções;

Um objeto Labirinto pode ser exibido pela função print().

 In [5]: print(f"Labirinto inicial:\n{lbrnt}")
Labirinto inicial:
     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  1| # |   |   |   | # |   |   |   | # | # |   | # | # |   |   |   |   |   | # |   |   | T |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  2| # |   | # |   |   |   | # |   |   |   |   |   |   |   | # | # | # |   | # |   | # | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  3| # |   | # |   | # |   |   | # | # |   |   | # | # | # | # |   |   |   | # |   | # | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  4| # | # | # |   | # | # | # | # | # | # |   |   |   |   | # | # | # |   | # |   |   | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  5| # |   |   |   |   |   |   |   |   |   |   | # | # |   |   | # | # |   |   |   |   | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  6| # | # | # | # | # |   | # | # | # | # | # | # |   |   |   | # | # | # | # | # |   | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  7| # |   |   |   |   |   | # |   |   |   | # | # | # | # | # | # | # |   |   | # |   | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  8| # |   | # | # | # | # | # | # | # |   |   |   | # |   |   | M | # | # |   |   |   | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  9| # |   |   |   |   |   |   |   |   |   | # |   |   |   | # |   |   | # |   | # | # | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 10| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |   | # | # | # |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Os símbolos +, - e os números não fazem parte do labirinto. Só estão ai para visualizarmos melhor o labirinto.

Para consultarmos o conteúdo da posição de índices [lin, col] de um objeto da classe Labirinto, como lbrnt, escrevemos

In [7]: lbrnt[1, 21] # posição de Teseu
Out[7]: 'T'

In [8]: lbrnt[8, 15] # posição do Minotauro
Out[8]: 'M'

In [8]: lbrnt[4, 2]  # parede
Out[8]: '#'

Contaremos com mais alguns métodos para manipularmos um objeto Labirinto na nossa solução do Problema de Teseu. Labirinto.corredor(lin, col) é um método que recebe um par de inteiros lin e col

e retorna True se [lin, col] é uma posição de um corredor do labirinto e retorna False em caso contrário.

In [4]: lbrnt.corredor(9, 1)
Out[4]: True

In [5]: lbrnt.corredor(10, 1)
Out[5]: False

In [6]: lbrnt.corredor(11, 1) # [11, 1] nem está no labirinto...
Out[6]: False

In [7]: lbrnt.corredor(10, 18) # é uma entrada/saída
Out[7]: True

In [8]: lbrnt.corredor(1, 21) # é uma entrada/saída
Out[8]: True

O método Labirinto.registre(lin, col, marca) que recebe índices [lin, col] de uma posição do labirinto e um

caractere marca para colocar nessa posição. O efeito é o mesmo que se fizéssemos Labirinto[lin, col] = marca.

In [9]: from marcas import *

In [10]: lbrnt.registre(10, 18, BECO)

In [11]: lbrnt[10, 18]
Out[11]: 'b'

In [12]: lbrnt[1, 20]
Out[12]: ' '

In [13]: lbrnt.registre(1, 20, TESEU)

In [14]: lbrnt[1, 20]
Out[14]: 'T'

In [15]: lbrnt[1, 21]
Out[15]: 'T'

In [16]: lbrnt.registre(1, 21, FIO)

In [17]: lbrnt[1, 21]
Out[18]: '*'

In [21]: lbrnt[3, 15]
Out[21]: ' '

In [22]: lbrnt[3, 15] = BECO # o mesmos lbrnt.registre(3, 15, BECO)

In [23]: lbrnt[3, 15]
Out[23]: 'b'

Mais um método que utilizaremos é Labirinto.minotauro(lin, col) que recebe os índices [lin, col] de uma posição do labirinto e retorna True se o Minotauro está na posição [lin, col] e retorna False em caso contrário.

In [5]: lbrnt[8, 15]
Out[5]: 'M'

In [6]: lbrnt.minotauro(8, 15)
Out[6]: True

In [7]: lbrnt[1, 19]
Out[7]: ' '

In [8]: lbrnt.minotauro(1, 19)
Out[8]: False

In [9]: lbrnt[2, 20]
Out[9]: '#'

In [10]: lbrnt.minotauro(2, 20)
Out[10]: False

Por último, um objeto Labirinto sabe a posição inicial de entrada de Teseu no labirinto e a posição do Minotauro. Os atributos de estados teseu_lin, teseu_col dizem a posição inicial de Teseu e os atributos de estado minouro_lin e minotauro_col são os responsáveis pela posição secreta do Minotauro. Se não tivermos Minotauro no labirinto suporemos que minouro_lin e minotauro_col são None.

In [11]: lbrnt.teseu_lin
Out[11]: 1

In [12]: lbrnt.tedeu_col
Out[12]: 21

In [13]: lbrnt.minotauro_lin
Out[13]: 8

In [14]: lbrnt.minotauro_col
Out[14]: 15

18.4. Pequena aventura

Para aquecer os nossos motores escrevemos uma solução para uma versão super simplificada do problema de Teseu em que o labirinto é um mero corredor. Bem, um corredor não dá para ser chamado de um labirinto… Tudo bem, o que vale a intenção e isso servirá para testarmos ideias!

O labirinto que usaremos é algo como

   0   1   2   3   4   5   6   7   8   9  10  11  12
 +---+---+---+---+---+---+---+---+---+---+---+---+---+
0| # | # | # | # | # | # | # | # | # | # | # | # | # |
 +---+---+---+---+---+---+---+---+---+---+---+---+---+
1| T |   |   |   |   |   |   | M |   |   |   |   | # |
 +---+---+---+---+---+---+---+---+---+---+---+---+---+
2| # | # | # | # | # | # | # | # | # | # | # | # | # |
 +---+---+---+---+---+---+---+---+---+---+---+---+---+

Teseu está na entrada do corredor na posição [1,0] e o Minotauro está paradinho na posição [1,7].

In [1]: from labirinto import Labirinto

In [2]: lbrnt = Labirinto("corredor.txt")

In [3]: more corredor.txt
#############
T      M    #
#############

Faremos uma função teseu() que resolve o

Problema (simplificado de Teseu): Dado um “labirinto horizontal” com Teseu na entrada, a posição mais à esquerda, encontrar um caminho de Teseu até o Minotauro.

Faremos três versões de uma função recursiva teseu() para o problema simplificado. A expressão da solução de forma recursiva se ajusta como uma luva. 🧤

A reflexão que faremos agora é semelhante àquela que fizemos na seção Rastros em que traçavamos um paralelo entre a execução função factorialR(k) para o calculo recursivo de fatorial de k e as bonicas Matryoshka 🪆. Examinemos um pouco a animação a seguir antes de partirmos para a nossa solução. Na animação o papel do Teseu e desempenhado pela tartaruga que se move. Em uma solução recursiva, cada chamada a função teseu(), cria mais um Teseu no labirinto que corresponde a uma chamada ainda ativa, que não foi encerrada, da função teseu(). Nessa animação cada posição em que nas nossas animações anteriores havia um círculo ⚫, o fio de Ariadne, é mostrado agora mais um Teseu. Cada Teseu representa portanto uma chamada da função teseu() que ainda está ativa. Tudo se passa como se uma tarefa grande que Teseu deveria realizar foi desmembrada em tarefa menores, uma tarefa realizada por cada um dos Teseus: cada Teseu deve seguir o roteiro descrito na função teseu() para a posição em que se encontra.

A nossa função estará preparada para o causo em que o Minotauro não está no labirinto. vai que ele saiu do labirinto para tomar um ar. 🌞 😎

A função teseu() receberá um “labirinto horizontal” lbrnt, no fundo um mero corredor, e a posição [lin,col] do Teseu responsável pela posição. A base da recursão será quando [lin,col] é a posição de uma PAREDE ou a parte do corredor em está o Minotauro. Como no caso Teseu só pode andar para a direita, de uma posição [lin,col] para uma posição [lin,col+1] e função teseu() na sua versão mais simples fica com cara de fatorial recursivo. Tá na cara que uma 😉 que uma função recursiva como esse poderia ser facilmente adaptada para sua versão iterativa, com algum while....

Listing 18.2 teseu_simplificada.py

def teseu(lbrnt, lin, col):
    '''(Labirinto, int, int) -> bool
    RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto.
    RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário.
    '''
    # base da recursão: posição [lin,col] não é (parte de) corredor
    if not lbrnt.corredor(lin, col): return False
    # base da recursão: Minotauro esta na posição [lin,col]
    if lbrnt.minotauro(lin, col): return True

    # resolva recursivamente: passe a bola para um novo Teseu na direita
    encontrou = teseu(lbrnt, lin, col+1)
    return encontrou

Essa versão da função teseu() é até bacaninha 🤭 e resolvem o problema. Entretanto, faremos uma melhorias nessa versão que nos ajudarão mais adiante, mas que no momento podem ser até desnecessárias.

Na nossa nova versão registraremos 📝 todos os passos 👣 feito pelo Teseu responsável pela recursão que trata da posição [lin,col] No código usamos os apelidos em marcas.py e as nova linhas estão em destaque.

Listing 18.3 teseu_melhorado.py

def teseu(lbrnt, lin, col):
    '''(Labirinto, int, int) -> bool
    RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto.
    RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário.
    '''
    # base da recursão: posição [lin,col] não é (parte de) corredor
    if not lbrnt.corredor(lin, col): return False
    # base da recursão: Minotauro esta na posição [lin,col]
    if lbrnt.minotauro(lin, col):
        lbrnt.registre(lin, col, MINOTAURO_DERROTADO)
        return True

    # registre a posição em que Teseu está
    lbrnt.registre(lin, col, FIO)

    # resolva recursivamente: passe a bola para um novo Teseu na direita
    encontrou = teseu(lbrnt, lin, col+1)

    # registre o resultado da busca
    if encontrou: # derrotou o Minotauro e esta voltando para a saída
       lbrnt.registre(lin, col, SAIDA)
    else: # não encontro o Minotauro e está voltando para a saída
       lbrnt.registre(lin, col, BECO)

    return encontrou

Vejamos o resultado produzido por essa função melhora. Em particular vamos dar uma olhada nos livros de notas 📚. Olhemos os registros 📖 feitos pala função no labirinto.

In [1]: from labirinto import Labirinto

In [2]: lbrnt = Labirinto("corredor.txt")

In [3]: print(lbrnt)
    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| T |   |   |   |   |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+

In [4]: from teseu_simplificado import teseu

In [5]: teseu(lbrnt, lbrnt.teseu_lin, lbrnr.teseu_col)
Out[5]: True

In [6]: print(lbrnt)
    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| s | s | s | s | s | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+

🤔 Hmm. A chamada teseu(lbrnt, 1, 0) retornou True. Depois da chamada a posição [1, 7] em que estava o Minotauro ficou marcada com o caractere MINOTAURO_DERROTADO e as posições da entrada do labirinto até o Minotauro estão com um sinal de SAIDA. As marcas SAIDA foram todas deixadas enquanto Teseu voltava das chamadas recursivas. Cada uma das chamadas, cada Teseu reponsável pela posição ficou encarredado de fazer esse registro antes de passar a bola para o Teseu que o chamou.

Apliquemos agora a função melhorada a um labirinto horizontal em que o Minotauro não está presente e vejamos o resultado.

In [8]: lbrnt = Labirinto("corredor_sem_minotauro.txt")

In [9]: print(lbrnt)
    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| T |   |   |   |   |   |   |   |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+

In [10]: teseu(lbrnt, 1, 0)
Out[10]: False

In [11]: print(lbrnt)
    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| b | b | b | b | b | b | b | b | b | b | b | b | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+

Desta vez a função retornou False, já que o Minotauro não estava no labirinto. Vemos a marca BECO em todas as posições. Teseu recursivamente andou todo o corredor a procura do Minoutauro, não encontrou, e na volta da recursão cada Teseu marcou a posição sob sua responsabilidade com BECO sinalizando que o Minoutauro não está naquela direção. Para compreendermos a recursão é indispensável percebermos que há um Teseu responsável por cada posição e que cada Teseu está associado a uma chamada da função teseu. 😖

Para entendermos completamente, e assistamos um passo 👣 a passo 👣 da função teseu() faremos uma última versão mais verborrágica. Nessa versão Teseu tem um radio transmissor e nos informa a cada momento onde está e o que está fazendo na sua missão no labirinto. É conveniente colocar no meio do código chamadas à uma função pause() que está a seguir.

def pause():
    input("Tecle ENTER para continuar.")

Chamadas à pause() nos permitem que monitoremos 🔍 cada passo de Teseu, ou dos Teseus, no labirinto. No código a seguir as linhas com o código da nossa primeira versão, o nosso esqueleto de solução, estão em destaque.

Listing 18.4 teseu_verborragico.py

def teseu(lbrnt, lin, col):
    '''(Labirinto, int, int) -> bool
    RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto.
    RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário.
    '''
    # base da recursão: posição [lin,col] não é (parte de) corredor
    if not lbrnt.corredor(lin, col): return False
    # base da recursão: Minotauro esta na posição [lin,col]
    if lbrnt.minotauro(lin, col):
        lbrnt.registre(lin, col, TESEU_MINOTAURO)
        print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Estou com o Minotauro!"')
        pause() # pare e aprecie
        lbrnt.registre(lin, col, MINOTAURO_DERROTADO)
        print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Derrotei o Minotauro! Missão cumprida! Vamos para a saída!"')
        pause()
        return True

    # registre a posição em que Teseu está
    lbrnt.registre(lin, col, TESEU)
    print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Avançamos até a posição [{lin},{col}]."')
    pause() # pare e aprecie
    lbrnt.registre(lin, col, FIO)

    # resolva recursivamente: passe a bola para um novo Teseu na direita
    encontrou = teseu(lbrnt, lin, col+1)

    # registre o resultado da busca
    lbrnt.registre(lin, col, TESEU)
    if encontrou:
        print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Missão cumprida! Vamos para a saída!"')
        lbrnt.registre(lin, col, SAIDA)
    else:
        print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Minha posição leva a um beco sem saída. Voltar!"')
        lbrnt.registre(lin, col, BECO)
    pause() # pare e aprecie
    return encontrou

Aqui vai a longa sequência de mensagens enviadas pelo(s) Teseu(s) para o nosso centro de controle.

In [1]: from labirinto_str import Labirinto

In [2]: lbrnt = Labirinto("corredor.txt")

In [3]: from teseu_simplificado import teseu

In [4]: teseu(lbrnt, lbrnt.teseu_lin, lbrnt.teseu_col)
    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| T |   |   |   |   |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,0]: "Avançamos até a posição [1,0]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | T |   |   |   |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,1]: "Avançamos até a posição [1,1]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | T |   |   |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,2]: "Avançamos até a posição [1,2]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | T |   |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,3]: "Avançamos até a posição [1,3]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | T |   |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,4]: "Avançamos até a posição [1,4]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | T |   | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,5]: "Avançamos até a posição [1,5]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | * | T | M |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,6]: "Avançamos até a posição [1,6]."
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | * | * | $ |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,7]: "Estou com o Minotauro!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | * | * | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,7]: "Derrotei o Minotauro! Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | * | T | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,6]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | * | T | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,5]: "Missão cumprida Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | * | T | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,4]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | * | T | s | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,3]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | * | T | s | s | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,2]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| * | T | s | s | s | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,1]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

    0   1   2   3   4   5   6   7   8   9  10  11  12
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 0| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 1| T | s | s | s | s | s | s | X |   |   |   |   | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
 2| # | # | # | # | # | # | # | # | # | # | # | # | # |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+
Teseu da posição [1,0]: "Missão cumprida! Vamos para a saída!"
Tecle enter para continuar.

Out[4]: True

Todas essas ações que procuram mimetizar a ideia da Ariadne, registros 📝 e labirinto como livro de anotações 📖, serão usadas na solução do problema de Teseu.

18.5. Aventura de Teseu

Na nossa solução para o problema de Teseu estenderemos as ideias presentes na solução do problema simplificado. Acrescentaremos apenas mais algumas elementos na base da recursão referentes a mais algumas possibilidades para retrocedermos. Devemos ainda levar em consideração as demais direções nas quais Teseu pode se movimentar. A animação abaixo mostra a função teseu() durante o horário de serviço.

Hmm. 🤔 Notemos que a cada momento há várias tartarugas Teseu 🐢 🐢 🐢… Do ponto de vista 👀 de recursão é útil imaginarmos, como na animação, que no labirinto há vários Teseus, em vez de apenas um Teseu como no mito. Cada Teseu 🐢 corresponde a uma chamada recursiva ainda ativa da função teseu() e será o responsável pela posição em que está. Notemos pela animação que os Teseus das chamadas ativas formam um caminho do Teseu mais avançado até a saída do labirinto, fazem o papel do fio 🧵 de Ariadne.

O caminho de volta a entrada do labirinto será percorrido quando as chamadas recursivas estiverem sendo encerradas e, antes de retorno da chamada, um triângulo é registrado 📝 no caderno de anotações 📚 que é próprio labirinto. As posições com os triângulos são verdadeiramente a solução do problema.

Desenvolveremos a seguir o roteiro que estará descrito em Python pela função teseu() no final desta seção. Mãos à obra! 👐

A função teseu() recebe um labirinto lbrnt, objeto da classe Labirinto, e uma posição [lin,col] que será de responsabilidade do Teseu da chamada. No início Teseu está na entrada do labirinto, na posição [lbrnt.teseu_lin, lbrnt.teseu_col]. Para resolver o problema de Teseu a chamada inicial da função é

teseu(lbrnt, lbrnt.teseu_lin, lbrnt.teseu_col)

Comecemos a considerar o casos bases de teseu() em que a função retorna imediatamente o valor False. A função deve retornar False sempre que a posição [lin, col] está fora do labirinto ou está marcada com o símbolo:

• PAREDE, já que não podemos emparedar um Teseu; 😄

• BECO, pois esse símbolo índica que a região do labirinto que tem essa posição como porta de entrada já fui completamente explorada pelos Teseus;

• FIO, uma vez que essa marca mostra por onde já passou a busca e que já há um Teseu responsável por essa posição.

No código da função as linha \(6\) a \(11\) correspondem ao que acabamos de considerado.

A função deve imediatamente retornar True se na posição estiver o Minotauro e deixar uma marca que nos diz que ali temos um MINOTAURO_DERROTADO. Isso é de responsabilidade das linhas \(12\) a \(15\) do código da função. Com isso concluímos a base da recursão. Faz sentido? ¯\_(ツ)_/¯

Se no roteiro a função não parou na base podemos afirma que a posição [lin,col] da chamada é LIVRE. Nesse caso, o Teseu da chamada percorrerá o corredor correspondente e deve portanto marcá-lo como FIO. Esse é o trabalho feito pelas linhas \(17\) e \(18\) do código da função.

Feito tudo isso, o nosso roteiro chegou em um ponto que o Teseu da vez deve pedir ajuda aos seu clones para continuar a busca. O Teseu responsável pelo posição [lin,col] enxegar quatro posições vizinhas:

• [lin-1,col] ao NORTE;

• [lin,col+1] a LESTE;

• [lin+1,col] ao SUL; e

• [lin,col-1] a OESTE.

A recursão deve avançar em cada uma dessas direções, uma por vez, e deve parar assim que um dos clones reportar que encontrou o Minotauro, retornou True. Esse é o papel desempenhado pelas linhas \(20\) a \(24\) do código em que as chamada são feitas sequencialmente, uma após a outra. Como as chamadas estão sendo concatenadas com operador lógico or, assim que uma retornar True as seguintes não serão feitas. Em programação o comportamento desses operadores lógicos Python é conhecido pelo nome de curto circuito (= short circuit evaluation),

Finalmente, quando há um retrocesso na busca, após as chamadas recursivas, no final da função, o Teseu responsável pela posição deixa nela uma marca indicando o ele e seus colegas Teseus descobriram ao investigar 🔎 a região do labirinto que tem essa posição como porta de entrada. Por último, Teseu retorna ao clone, colega que o chamou, o resultado da busca, True ou False. Quando os Teseus não encontraram o Minotauro é deixada a marca BECO 🟥 e quando o Minotauro é encontrado é deixado a marca SAIDA 🔺. Tudo isso é feito a partir da linha \(26\) até o final.

Vamos ao código que apresenta em Python o todo o roteiro apresentado. No código abaixo as linhas em destaque são aquelas que foram acrescentadas à função herdada da solução do problema simplificado.

Listing 18.5 teseu.py

def teseu(lbrnt, lin, col):
    '''(Labirinto, int, int) -> bool
    RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto.
    RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário.
    '''
    # base da recursão: posição [lin,col] não é corredor
    if not lbrnt.corredor(lin, col): return False
    # base da recursão: posição [lin,col] nos leva a um beco sem saida
    if lbrnt[lin, col] == BECO: return False
    # base da recursão: ja passamos na posição [lin,col] é já há um Teseu responsável por ela
    if not lbrnt[lin, col] == FIO: return False
    # base da recursão: Minotauro esta na posição [lin,col]
    if lbrnt.minotauro(lin, col):
        lbrnt.registre(lin, col, MINOTAURO_DERROTADO)
        return True

    # registre a posição em que Teseu desta chamada está
    lbrnt.registre(lin, col, FIO)

    # resolva recursivamente: passe a bola para novos Teseus em posições adjacentes
    encontrou = teseu(lbrnt, lin-1, col  ) or \
                teseu(lbrnt, lin  , col+1) or \
                teseu(lbrnt, lin+1, col  ) or \
                teseu(lbrnt, lin  , col+1)

    # registre o resultado da busca
    if encontrou: # derrotou o Minotauro e esta voltando para a saída
       lbrnt.registre(lin, col, SAIDA)
    else: # não encontro o Minotauro e está retrocedento
       lbrnt.registre(lin, col, BECO)

    return encontrou

18.6. Por onde passamos

Passamos pela ideia de Ariadne de registramos 🖊 os nossos passos 👣 ao longo de algum caminho. Isso permite que quando chegamos a um beco sem saída retrocedamos rapidamente até algum ponto da nossa sequência de decisões em que haja ainda alguma possibilidade não explorada. 😵‍💫 Esse ideia é aplicada na solução de vários problemas nos quais fazemos uma busca por um espaço de soluções em que os estados são dotados de uma relação de adjacência, cada estado sabe quais são os seus vizinhos. É isso que é feito por um algoritmo aplicado cotidianamente chamado de busca em profundidade. 😮

18.7. Veja se entendeu

1. Implemente uma classe Labirinto que tenhe comportamento semelhante ao da classe Labirinto descrita na seção Labirintos e usada por nós ao longo do nosso passeio pela ideia de Ariadne e a aventura de Teseu.

2. Escreva uma implementação iterativa da função teseu().

3. Escreva uma função caminho() que recebe um objeto lbrnt da classe Labirinto após a execução de teseu(lbrnt,lbrnt.teseu_lin,lbrnt.teseu_lin) e retorna uma lista com as posições percorridas por Teseu do Minotauro até a entrada/saída do labirinto.

18.8. O que é …

Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. 🤓

Ariadne

Na mitologia grega, é a princesa de Creta, filha do rei Minos e da rainha Pasífae.

Teseu

Na mitologia grega, um grande herói ateniense.

Minotauro

Na mitologia grega, era uma criatura com a cabeça de um touro sobre o corpo de um homem.

Labirinto

Construção de percursos intrincados criados com a intenção de desorientar quem os percorre.

18.9. Para saber mais

• Recursão e algoritmos recursivos de Projeto de Algoritmos de Paulo Feofiloff.

• Recursão de Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python de Brad Miller e David Ranum.

• Recursão de Como Pensar Como um Cientista da Computação de Brad Miller e David Ranum.

• Recursion de Introduction to Programming in Python. de Robert Sedgewick, Kevin Wayne e Robert Dondero.