Técnicas II: Backtracking

Introdução Teórica

O Backtracking (ou “retrocesso”) é uma estratégia algorítmica de força bruta refinada para encontrar soluções de problemas computacionais, notadamente problemas de satisfação de restrições.

A Ideia Central

Imagine que você está tentando sair de um labirinto: 1. Você anda até chegar a uma bifurcação. 2. Escolhe um caminho aleatoriamente e segue. 3. Se chegar a um beco sem saída, você volta (faz backtrack) até a última bifurcação. 4. Escolhe o próximo caminho não explorado.

Computacionalmente, construímos uma Árvore de Espaço de Estados onde a raiz é o estado inicial e as folhas são soluções completas ou becos sem saída.

Poda (Pruning)

A grande vantagem sobre a força bruta pura é a Poda. Se no meio do caminho percebemos que a solução parcial atual viola alguma restrição e nunca levará a uma solução válida, abandonamos aquele ramo imediatamente, economizando tempo.

Problema Clássico

Problema: O Labirinto (Desenhando Labirintos) Link: Beecrowd 1076

Descrição: Basicamente um problema de travessia em grafo, mas pode ser modelado como: “visite todos os nós e retorne gastando o mínimo, onde cada aresta tem peso”. O backtracking puro geralmente explora caminhos. No caso do 1076, é uma contagem de arestas * 2 (ida e volta), mas a lógica de “explorar e voltar” é a essência do backtracking (DFS).

Link Melhor (Rainhas): Embora não tenha o N-Queens “puro” padrão fácil no Beecrowd, o conceito é central. Vamos ver uma aplicação em Sudoku ou similar.

Problema Alternativo: Sudoku Link: Beecrowd 1383 (Este problema pede apenas a validação, o que é simples. Para resolver Sudoku, usamos backtracking).

Para treinar Backtracking clássico de “Gerar e Testar”: Problema: Senha Link: [Beecrowd 2140] (Troco) -> Não. Sugestão Forte: Beecrowd 1767 (Saco do Papai Noel - Mochila / Backtracking). Embora Mochila tenha DP, pode ser resolvida com Backtracking para \(N\) pequeno.

Variações e Exercícios

  1. [Permutações com Restrição - Problema das Rainhas]
    • Não há um link direto simples no Beecrowd para N-Queens introdutório. Recomenda-se implementar N-Queens localmente para \(N=8\).
  2. [O Cavalo no Xadrez]
    • Foco: Passeio do Cavalo (Knight’s Tour). Similar a encontrar caminho em labirinto.
    • Link: Tente implementar um algoritmo que visita todas as casas do tabuleiro sem repetir.
  3. [Sudoku (Resolver)]
    • Escreva um solver para o problema 1383 (mesmo que o juiz só peça validação, o solver é o exercício real de backtracking).
      1. Encontre célula vazia.
      1. Tente números 1-9.
      1. Se válido, chame recursão.
      1. Se recursão falhar, limpe célula (backtrack) e tente próximo número.
Back to top