Maze solving is one of those problems that looks simple on paper until you actually implement it
O labirinto do mouse é um problema clássico de ciência da computação que simula um rato tentando sair de um labirinto. A estrutura básica envolve uma grade bidimensional onde células podem ser caminhos livres ou paredes, e o algoritmo precisa encontrar uma rota do ponto inicial ao destino. Parece trivial até você tentar resolver manualmente um labirinto 20x20 com múltiplos caminhos sem saída. A implementação mais comum usa buscas em grafos. Você transforma cada célula livre num nó e as adjacências viram arestas. A partir daí, dois algoritmos dominam: DFS (busca em profundidade) e BFS (busca em largura). A diferença principal é que BFS garante o caminho mais curto em termos de número de passos, enquanto DFS pode encontrar uma solução mais rápido mas sem garantia de optimalidade.
Implementando o labirinto do mouse
Vou mostrar a abordagem BFS porque é a mais útil no mundo real. A ideia é manter uma fila de células a visitar e marcar cada célula como visitada para evitar ciclos.
from collections import deque
def solve_maze(maze, start, end):
rows = len(maze)
cols = len(maze[0])
visited = [[False]*cols for _ in range(rows)]
parent = [[None]*cols for _ in range(rows)]
queue = deque([start])
visited[start[0]][start[1]] = True
directions = [(-1,0),(1,0),(0,-1),(0,1)]
while queue:
r, c = queue.popleft()
if (r, c) == end:
path = []
current = end
while current:
path.append(current)
current = parent[current[0]][current[1]]
return path[::-1]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc cols:
if not visited[nr][nc] and maze[nr][nc] == 1:
visited[nr][nc] = True
parent[nr][nc] = (r, c)
queue.append((nr, nc))
return NoneO labirinto é representado como uma matriz 2D onde 1 indica caminho livre e 0 indica parede. O ponto start e end são tuplas (linha, coluna). O array parent permite reconstruir o caminho ao final, seguindo os ponteiros de trás para frente. Na prática, existe um detalhe que quase todo tutoria ignorante esquece de mencionar: a complexidade espacial. Em labirintos grandes, a matriz visited pode ocupar bastante memória. Para um labirinto 100x100, são 10.000 booleanos — tranquilo. Para 1000x1000, você já está falando de um milhão de células na fila no pior caso. Se o memory é preocupação, dá pra otimizar usando um bitset ou invertendo a matriz original marcando células visitadas com um valor diferente.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Outro problema real que eu encontrei várias vezes: labirintos com múltiplas soluções de comprimentos diferentes. O BFS sempre encontra a mais curta em número de passos, mas isso nem sempre é o que o usuário quer. Às vezes um caminho ligeiramente mais longo evita zonas de risco ou passa por pontos de interesse. Nesse caso, DFS com poda por profundidade máxima pode ser mais adequado. Ou você simplesmente roda múltiplas buscas e escolhe o resultado que melhor se encaixa. Uma armadilha comum é esquecer de verificar limites antes de acessar a matriz. Se o algoritmo tentar acessar maze[-1][5] ou maze[20][3], o programa trava com IndexError. Sempre valide as coordenadas antes de qualquer acesso.
Para quem quer experimentar com labirintos maiores e visualização, existem bibliotecas em Python como maze_generator que criam labirintos aleatórios com o algoritmo de recursive backtracking. Juntar isso com o solver BFS e plotar com matplotlib dá um resultado visual bem satisfatório em cerca de meia hora de trabalho. A versão DFS do mesmo problema é ainda mais simples de implementar mas perde a garantia de optimalidade. Eu costumo usar DFS quando o labirinto é tão grande que BFS fica impraticável em memória, ou quando apenas preciso de qualquer caminho válido rapidamente. Em testes práticos, DFS resolve labirintos 500x500 em cerca de 0.3 segundos contra 1.8 segundos do BFS no meu setup, mas gasta menos memória no caso médio porque não precisa manter todos os nós do nível atual na fila.
O problema ganha outra camada de complexidade quando adicionamos regras como: paredes móveis, custo variado por célula, ou múltiplos agentes. Nesses casos, BFS puro não basta e você precisa recorrer a A* com heurística apropriada. Mas isso já é outro assunto.
