O backtracking é o mecanismo fundamental que torna o Prolog uma linguagem
de busca e resolução de problemas. Quando uma consulta é feita, o Prolog tenta satisfazer os objetivos
na ordem em que aparecem. Se um objetivo falha, ele volta atrás (backtrack) e tenta
outra alternativa, até encontrar todas as soluções possíveis. Vamos entender esse processo com um exemplo
clássico: a geração de números binários de 3 bits.
O Programa 3.1 — Números Binários
% Fatos: dígitos binários válidos
d(0).
d(1).
% Regra: uma lista de 3 bits é formada por 3 dígitos binários
b([A, B, C]) :- d(A), d(B), d(C).
O predicado d/1 define os dois dígitos binários possíveis. A regra b/1
afirma que uma lista de três elementos [A, B, C] é um número binário se A,
B e C forem todos dígitos binários.
Objetivo da Consulta: ?- b(N).
Ao executar ?- b(N)., o Prolog deve gerar todas as combinações possíveis
de 3 bits: [0,0,0], [0,0,1], [0,1,0], e assim por diante, até
[1,1,1] — totalizando 8 soluções.
A Árvore de Busca Passo a Passo
O Prolog constrói uma árvore de busca onde cada nó representa um objetivo a ser provado.
Acompanhe a execução abaixo:
│
├─ N = [A, B, C] (unificação com a cabeça da regra)
│
├─ d(A)
│ ├─ A = 0 ✅ sucesso
│ └─ A = 1 (backtracking após esgotar B e C)
│
├─ d(B)
│ ├─ B = 0 ✅
│ └─ B = 1
│
├─ d(C)
│ ├─ C = 0 ✅ → [0,0,0] (1ª solução)
│ └─ C = 1 ✅ → [0,0,1] (2ª solução)
│
├─ ↩️ Backtracking em B (após C=1, falha ao tentar C=2)
│ └─ B = 1 ✅
│ ├─ C = 0 ✅ → [0,1,0] (3ª)
│ └─ C = 1 ✅ → [0,1,1] (4ª)
│
├─ ↩️ Backtracking em A (após esgotar B e C com A=0)
│ └─ A = 1 ✅
│ ├─ d(B) → B = 0
│ │ ├─ C = 0 ✅ → [1,0,0] (5ª)
│ │ └─ C = 1 ✅ → [1,0,1] (6ª)
│ └─ B = 1
│ ├─ C = 0 ✅ → [1,1,0] (7ª)
│ └─ C = 1 ✅ → [1,1,1] (8ª)
│
└─ ❌ Falha total — todas as combinações foram exploradas
• O Prolog tenta primeiro a solução mais à esquerda (A=0, B=0, C=0).
• Ao pressionar
; (ponto-e-vírgula) no terminal, ele retrocede no C e tenta C=1.• Quando C se esgota, retrocede no B e tenta B=1, depois C=0, C=1, e assim por diante.
• O processo continua até esgotar todas as combinações de A, B e C.
Resolução e Redução de Objetivos
O Prolog utiliza um mecanismo chamado resolução SLD (Selected Linear Definite).
A resolução é o processo de unificar a consulta com a cabeça de uma regra e substituir
a consulta pelo corpo da regra. A redução ocorre quando um objetivo é substituído por
subobjetivos (ex: b(N) é reduzido a d(A), d(B), d(C)). A árvore acima mostra
exatamente essa cadeia de reduções e tentativas de unificação.
Ordem das Cláusulas e Objetivos
A ordem dos fatos e das metas no corpo das regras afeta diretamente
a forma da árvore de busca. Por exemplo, se definíssemos d(1). d(0). (invertendo a ordem),
a primeira solução seria [1,1,1] em vez de [0,0,0]. A ordem dos objetivos
também importa: d(C), d(B), d(A) geraria a mesma lista de soluções, mas em ordem diferente.
para podar a árvore de busca cedo. Por exemplo, se você está buscando
d(A), A > 0,é mais eficiente testar
A > 0 antes de chamar d(A)? Na verdade, Aprecisa estar instanciado para a comparação, então a ordem ideal depende do caso — mas em geral,
metas que geram poucas soluções devem vir antes.
Exercício Proposto
Modifique a ordem dos objetivos na regra b/1 para:
b([A, B, C]) :- d(C), d(B), d(A).
Perguntas:
1. Qual será a primeira solução gerada?
2. Como a árvore de busca se altera?
3. O número total de soluções (8) continua o mesmo?
4. O que acontece se mudarmos a ordem dos fatos d(0). d(1). para d(1). d(0).?
Teste no seu interpretador Prolog e observe o comportamento. Essa prática ajuda a internalizar
como o backtracking e a ordem influenciam a execução.
✅ Conclusão
O backtracking é o motor que impulsiona a busca em Prolog.
Ele é automático e controlado pelo motor de inferência — o programador não precisa
gerenciar pilhas ou loops manualmente. Entender a árvore de busca é essencial para:
- Prever a ordem das soluções;
- Escrever regras eficientes (colocando metas restritivas primeiro);
- Controlar o fluxo com corte (
!) quando necessário; - Depurar programas que não terminam ou que geram soluções inesperadas.
Dominar o backtracking é dar um grande passo para se tornar um programador Prolog confiante e produtivo.