Backtracking é a mesma coisa que testar todas as combinações?

É parecido, mas mais esperto. A força bruta gera todas as combinações e só depois confere quais servem. O backtracking abandona um caminho assim que ele se mostra inviável, sem terminar de montá-lo. Essa poda corta ramos inteiros de uma vez e pode reduzir drasticamente o trabalho. No pior caso os dois se aproximam, mas na prática podar cedo faz o backtracking ser muito mais rápido.

Por que preciso marcar por onde passei?

Para não voltar a lugares já explorados e entrar em loop. Num labirinto, sem marcar o chão você andaria em círculos entre as mesmas casas. A marcação registra o que já faz parte da tentativa atual. E, ao voltar de um beco sem saída, você desmarca aquela casa, liberando-a para futuras tentativas por outro caminho. Marcar na ida e desmarcar na volta é o coração do backtracking.

Qual a relação entre backtracking e recursão?

A recursão dá o voltar de graça. Quando uma chamada não acha saída e retorna, o controle cai na chamada anterior, no ponto logo depois da escolha que ela fez, pronto para tentar a próxima opção. Por isso quase todo backtracking é escrito com recursão: a pilha de chamadas guarda o caminho percorrido e desfaz os passos na ordem certa, sem você precisar controlar isso à mão.

Que tipo de problema o backtracking resolve?

Problemas em que você precisa experimentar caminhos e alguns não dão certo: labirintos e busca de rotas, quebra-cabeças como sudoku e as oito rainhas, geração de todas as combinações ou permutações com regras, e alocação com restrições. O sinal é ter escolhas em cada passo, com a possibilidade de uma escolha travar mais adiante e exigir voltar.

O que é podar um ramo?

É abandonar um caminho assim que ele se revela sem futuro, antes de explorá-lo até o fim. Se a escolha atual já viola uma regra, não há razão para continuar: você volta na hora. Podar cedo elimina de uma vez todas as combinações que partiriam daquela escolha ruim, e é o que torna o backtracking viável em problemas com muitas possibilidades.

Backtracking sempre encontra a solução?

Se existe uma solução e o algoritmo explora todas as opções sem repetir estados, sim, ele acha. Se não existe solução, o backtracking esgota as possibilidades e termina informando que não há saída. O cuidado é garantir que ele não repita estados (por isso a marcação) e que reconheça os casos base, senão pode não terminar ou demorar demais.

Módulo 8 - Recursão avançada: dividir, voltar e escolher

Backtracking: tentar um caminho e voltar

8 min de leitura · por Cesar Gargiulo, revisado pela equipe ValorFinal e GuardiaSec · Atualizado em 12/07/2026

O que você vai aprender

Entender backtracking como tentar, checar e desfazer.
Reconhecer o padrão em labirintos, quebra-cabeças e combinações.
Perceber o papel da marcação para não repetir e do desfazer ao voltar.
Ligar o backtracking à volta natural da recursão (o retorno das chamadas).

Tentar, checar, desfazer

Nem todo problema se resolve com uma conta direta. Achar a saída de um labirinto, preencher um sudoku, montar todas as senhas possíveis com certas regras: nesses casos você não sabe a resposta de antemão, precisa experimentar. O backtracking organiza essa experimentação. A ideia, em três tempos, é simples. Escolha uma opção e avance como se ela fosse a certa. A cada passo, cheque se a situação ainda é viável, ou seja, se ainda pode levar a uma solução. Se em algum ponto travar, num beco sem saída, desfaça a última escolha e tente a próxima opção daquele ponto. Se todas as opções de um ponto falharem, volte mais um passo e repita. É tentar, checar e desfazer, insistentemente, até achar a saída ou esgotar as possibilidades.

A imagem mais fiel é a de andar num labirinto com um novelo de linha. Você entra por um corredor, marcando o chão para saber que já passou ali. Numa bifurcação, escolhe um lado. Se o corredor termina numa parede, você recua pela linha até a última bifurcação e tenta o outro lado. As marcas no chão são essenciais: sem elas, você voltaria a corredores já explorados e andaria em círculos. Esse desfazer ao recuar é o que separa o backtracking de simplesmente escolher errado: cada escolha é reversível, e ao voltar você limpa a marca ou libera o recurso, deixando o ponto pronto para a próxima tentativa.

Uma pequena árvore de decisões sobre um labirinto. A partida se ramifica em três tentativas de caminho. Dois ramos terminam em quadrados vermelhos rotulados beco sem saída, com setas curvas de retorno voltando ao ponto de escolha e o rótulo desfazer. O terceiro ramo segue em verde até um alvo rotulado solução, mostrando o caminho que deu certo depois de descartar os outros. — Backtracking explora ramos: os becos sem saída fazem o algoritmo voltar e tentar outro, até um ramo levar à solução.

A recursão que volta sozinha

O backtracking casa perfeitamente com a recursão, porque a volta já vem de graça. Quando uma chamada recursiva não encontra saída e retorna, o controle cai automaticamente na chamada anterior, exatamente no ponto após a escolha que ela havia feito. Ali o código tenta a próxima opção. Ou seja, o desfazer acontece sozinho no retorno da recursão; você só precisa, ao voltar, limpar a marca que fez na ida (tirar o número que pôs na casa do sudoku, apagar a pegada no labirinto). O esqueleto é quase sempre o mesmo: para cada opção possível, marque, chame a recursão para o próximo passo, e se a chamada falhar, desmarque e siga para a opção seguinte.

// achar caminho num labirinto com backtracking
FUNÇÃO resolver(l, c)
  SE (l, c) é o objetivo ENTÃO
    RETORNE verdadeiro          // chegou
  FIM
  SE fora da grade OU é parede OU já visitei (l, c) ENTÃO
    RETORNE falso               // beco sem saída, volta
  FIM
  marcar (l, c) como visitado    // tentar por aqui
  SE resolver(l, c + 1) ENTÃO RETORNE verdadeiro FIM   // direita
  SE resolver(l + 1, c) ENTÃO RETORNE verdadeiro FIM   // baixo
  SE resolver(l, c - 1) ENTÃO RETORNE verdadeiro FIM   // esquerda
  SE resolver(l - 1, c) ENTÃO RETORNE verdadeiro FIM   // cima
  desmarcar (l, c)               // desfazer: nenhuma direção deu
  RETORNE falso
FIM

Marca, tenta as quatro direções por recursão, e se nenhuma leva ao objetivo, desmarca e volta. Esse desmarcar é o backtracking.

🎮 Jogo da aula

Ache a saída do labirinto

Leve o robô da partida até a estrela. As paredes formam becos sem saída: quando um caminho travar, volte e tente outra direção, como faz o backtracking. Existe um caminho que dá certo.

⭐

Podar para não testar tudo

Sem cuidado, experimentar caminhos pode significar testar um número enorme de combinações. O que salva o backtracking é a poda: abandonar um ramo assim que ele se mostra sem futuro, antes de explorá-lo até o fim. No sudoku, se pôr o número 5 numa casa já viola a regra da linha, não adianta continuar preenchendo o resto: você volta na hora. Cada volta antecipada elimina de uma vez todas as combinações que começariam por aquela escolha ruim. É a diferença entre um algoritmo esperto, que descarta becos cedo, e a força bruta cega, que gera tudo para só depois conferir. Quanto mais cedo você reconhece o beco sem saída, menos trabalho o backtracking faz.

Teste rápido

No backtracking, o que acontece quando a tentativa atual chega a um beco sem saída?

Perguntas frequentes

Backtracking é a mesma coisa que testar todas as combinações?: É parecido, mas mais esperto. A força bruta gera todas as combinações e só depois confere quais servem. O backtracking abandona um caminho assim que ele se mostra inviável, sem terminar de montá-lo. Essa poda corta ramos inteiros de uma vez e pode reduzir drasticamente o trabalho. No pior caso os dois se aproximam, mas na prática podar cedo faz o backtracking ser muito mais rápido.
Por que preciso marcar por onde passei?: Para não voltar a lugares já explorados e entrar em loop. Num labirinto, sem marcar o chão você andaria em círculos entre as mesmas casas. A marcação registra o que já faz parte da tentativa atual. E, ao voltar de um beco sem saída, você desmarca aquela casa, liberando-a para futuras tentativas por outro caminho. Marcar na ida e desmarcar na volta é o coração do backtracking.
Qual a relação entre backtracking e recursão?: A recursão dá o voltar de graça. Quando uma chamada não acha saída e retorna, o controle cai na chamada anterior, no ponto logo depois da escolha que ela fez, pronto para tentar a próxima opção. Por isso quase todo backtracking é escrito com recursão: a pilha de chamadas guarda o caminho percorrido e desfaz os passos na ordem certa, sem você precisar controlar isso à mão.
Que tipo de problema o backtracking resolve?: Problemas em que você precisa experimentar caminhos e alguns não dão certo: labirintos e busca de rotas, quebra-cabeças como sudoku e as oito rainhas, geração de todas as combinações ou permutações com regras, e alocação com restrições. O sinal é ter escolhas em cada passo, com a possibilidade de uma escolha travar mais adiante e exigir voltar.
O que é podar um ramo?: É abandonar um caminho assim que ele se revela sem futuro, antes de explorá-lo até o fim. Se a escolha atual já viola uma regra, não há razão para continuar: você volta na hora. Podar cedo elimina de uma vez todas as combinações que partiriam daquela escolha ruim, e é o que torna o backtracking viável em problemas com muitas possibilidades.
Backtracking sempre encontra a solução?: Se existe uma solução e o algoritmo explora todas as opções sem repetir estados, sim, ele acha. Se não existe solução, o backtracking esgota as possibilidades e termina informando que não há saída. O cuidado é garantir que ele não repita estados (por isso a marcação) e que reconheça os casos base, senão pode não terminar ou demorar demais.

Fontes

Seu progresso fica salvo neste aparelho. Assinantes sincronizam entre os aparelhos.

← A árvore de recursão: enxergar o trabalho total Concluir e avançar →