Técnicas II: Backtracking

Metáfora e Motivação

Imagine que você está tentando sair de um labirinto: anda até uma bifurcação, escolhe um caminho e segue. Se chegar a um beco sem saída, você volta até a bifurcação e tenta outro caminho. Essa é exatamente a ideia de 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.

Implementações em Código (Esboço)

Como exemplo, considere o clássico problema das N Rainhas: colocar \(N\) rainhas em um tabuleiro \(N \times N\) sem que se ataquem.

Em pseudocódigo, a ideia é:

  1. Colocar rainhas linha a linha.
  2. Em cada linha, tentar todas as colunas.
  3. Se uma posição for inválida (ataca outra rainha), pular.
  4. Se chegarmos à linha \(N\), encontramos uma solução.

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.

Exercício Prático Guiado

  1. Implemente uma função recursiva que tente resolver o problema das N Rainhas para \(N=8\).
  2. Modele o estado como “linha atual” + um array indicando em que coluna está a rainha de cada linha.
  3. Implemente uma função valido(linha, coluna) que verifica se colocar uma rainha ali conflita com alguma anterior.
  4. Conte quantas soluções diferentes existem para \(N=8\).

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