Um monge do século VIII escreveu um enigma sobre um lobo, uma cabra e um repolho. Doze séculos depois, o mesmo enigma virou o exemplo canôni...
Estado 01
Um problema com mil e duzentos anos
Diante de um rio, um barqueiro tem um lobo, uma cabra e um pé de repolho. O bote leva o barqueiro e mais um passageiro por vez. Se o lobo ficar sozinho com a cabra, a cabra vira jantar. Se a cabra ficar sozinha com o repolho, o repolho vira jantar. Como levar os três para a outra margem?
O enigma aparece nas Propositiones ad acuendos juvenes — "proposições para aguçar os jovens" —, coletânea de 53 problemas atribuída a Alcuíno de York, monge e conselheiro de Carlos Magno, compilada por volta do ano 800. É o problema de número 18, De lupo et capra et fasciculo cauli (HADLEY; SINGMASTER, 1992). Alcuíno o usava para treinar o raciocínio de jovens monges. Doze séculos depois, ele abre praticamente todo curso de inteligência artificial do planeta — e não por nostalgia.
O mesmo problema em duas linguagens: a do mundo, em cima; a da máquina, embaixo. A segunda não é mais "verdadeira" que a primeira — é apenas manipulável por um algoritmo.
A razão da sobrevivência é o que Alcuíno não tinha: um vocabulário formal para descrevê-lo. Em 1959, Allen Newell, John Clifford Shaw e Herbert Simon apresentaram o General Problem Solver com uma aposta ambiciosa — se qualquer problema pudesse ser descrito como um conjunto de estados e de operadores que levam de um estado a outro, então um único programa, genérico, poderia atacar todos eles (NEWELL; SHAW; SIMON, 1959). A aposta se mostrou grande demais para o GPS, mas o vocabulário ficou. E é dele que estamos falando: formular o problema é metade de resolvê-lo.
Estado 02
Os cinco componentes de um problema
Quando um agente de IA "resolve um problema", ele não está lidando com um rio, com peças de madeira ou com o trânsito de Brasília. Está lidando com uma estrutura de cinco partes (RUSSELL; NORVIG, 2021). Tudo o que se faz depois depende de acertar essas cinco:
Os cinco componentes de uma formulação. Faltando qualquer um deles, não existe problema — existe só uma reclamação.
Repare no que está fora da lista. Não há nada sobre como encontrar a resposta. A formulação descreve o terreno; o algoritmo de busca é quem caminha por ele. São duas decisões independentes — e a primeira costuma pesar mais que a segunda.
Quadro 1 — Os cinco componentes aplicados a três problemas de busca, 2026
| Componente | Travessia do rio | Quebra-cabeça de 8 peças | Rota urbana |
|---|---|---|---|
| Estado inicial | Barqueiro, lobo, cabra e repolho na margem esquerda | Uma configuração embaralhada das peças | O cruzamento onde o veículo está |
| Ações | Atravessar sozinho ou com um dos três | Deslizar uma peça vizinha para o vazio | Seguir por uma das vias que saem do cruzamento |
| Modelo de transição | Troca de margem do barqueiro e da carga | Nova configuração da grade 3 × 3 | O cruzamento na outra ponta da via |
| Teste de objetivo | Os quatro na margem direita | Peças em ordem, com o vazio no canto | Chegar ao endereço de destino |
| Custo | Uma unidade por travessia | Uma unidade por movimento | Tempo, distância ou consumo |
Fonte: elaborado pelo autor com base em Russell e Norvig (2021) e Luger (2013).Nota: quadro comparativo de natureza qualitativa; não se trata de dados estatísticos.
Estado 03
Dez estados, sete travessias
Descrever o enigma de Alcuíno com os cinco componentes tem uma consequência imediata e um pouco brutal: o problema encolhe. Cada personagem está em uma de duas margens, o que dá 2⁴ = 16 configurações possíveis. Seis delas são proibidas pelas regras — são aquelas em que alguém almoça alguém. Sobram dez estados, e é dentro desses dez que a resposta inteira mora.
Explore o espaço de estados
Clique em qualquer estado do grafo abaixo para ver quem está em cada margem. As linhas são as travessias possíveis — e, por serem reversíveis, valem nos dois sentidos.
Clique em um estado
Os números não são a ordem da solução: são apenas rótulos. O caminho é você — ou o algoritmo — quem descobre.
São dez estados e dez travessias possíveis entre eles. A solução mínima tem sete travessias, e existem exatamente duas — simétricas entre si, dependendo de o barqueiro levar o lobo ou o repolho na terceira viagem. Nenhum ser humano precisa de um computador para resolver isso. O ponto é outro: uma vez formulado assim, o problema deixou de exigir esperteza e passou a exigir apenas percorrer um grafo — e percorrer grafos é exatamente aquilo que máquinas fazem melhor que nós.
Estado 04
Anatomia de um espaço de estados
Vale fixar o vocabulário, porque ele reaparece em tudo o que se faz com busca — do algoritmo mais simples até o A* e as heurísticas admissíveis.
O espaço de estados é um grafo. O algoritmo de busca constrói, sobre ele, uma árvore de caminhos explorados.
O espaço de estados é o conjunto de todos os estados alcançáveis a partir do estado inicial, com as ações ligando uns aos outros. Um caminho é uma sequência de estados conectados por ações; uma solução é um caminho que termina em um estado que passa no teste de objetivo; e uma solução ótima é a de menor custo entre todas as soluções (LUGER, 2013).
Duas distinções costumam derrubar gente em prova. A primeira: estado não é o mesmo que nó. O estado é uma configuração do mundo; o nó é uma entrada na estrutura de dados do algoritmo, que carrega o estado mais a contabilidade da busca — quem foi o pai, qual ação me trouxe aqui, qual o custo acumulado. Dois nós diferentes podem guardar o mesmo estado, alcançado por caminhos distintos.
A segunda: o espaço de estados é um grafo, mas a busca constrói uma árvore sobre ele. E, o mais importante, o espaço de estados quase nunca é desenhado: ele é gerado sob demanda. Ninguém guarda na memória todas as posições possíveis de um tabuleiro de xadrez. O programa guarda o estado atual e sabe como produzir os vizinhos quando precisar. O grafo existe implicitamente, definido pelas regras — não explicitamente, em uma tabela.
Estado 05
Abstrair é escolher o que ignorar
Aqui mora a parte que nenhum livro consegue transformar em receita. Formular um problema é decidir o que não entra na descrição.
A abstração é um funil: entra o mundo com todos os seus detalhes, sai um grafo pequeno o suficiente para ser percorrido.
Pense em um aplicativo de rotas. O estado poderia incluir a posição exata do carro em centímetros, a marcha engatada, o nível do tanque, a chuva, o humor do motorista, a marca do pneu. Nada disso é falso. Tudo isso é irrelevante para a pergunta "por onde eu vou". A formulação útil reduz o estado a um cruzamento e as ações a "seguir por uma via" — e o mapa da cidade inteira cabe em um grafo com algumas dezenas de milhares de nós.
Existe um critério para saber se a abstração é legítima: ela precisa ser válida, no sentido de que todo caminho encontrado no mundo abstrato possa ser expandido em uma sequência de ações executáveis no mundo real (RUSSELL; NORVIG, 2021). Se o grafo diz "vire à esquerda na próxima" e a rua é mão única no outro sentido, a abstração jogou fora algo que não podia. Abstrair é escolher o que ignorar — e escolher errado não gera um erro de sintaxe, gera uma resposta confiante e inútil.
Um exercício honesto para levar à sala: peça que cada equipe formule um problema da própria área nos cinco componentes. A dificuldade quase nunca está nas ações. Está no teste de objetivo — "quando exatamente esse problema está resolvido?" é uma pergunta que muita gente descobre não saber responder.
Estado 06
Metade do universo é inatingível
Outro problema clássico da área é o quebra-cabeça de 8 peças: uma grade 3 × 3 com peças numeradas de 1 a 8 e um espaço vazio; move-se uma peça vizinha para o vazio, até que tudo fique em ordem.
Uma grade com nove posições e nove conteúdos distintos admite 9! = 362.880 arranjos. Só que — e este é um dos fatos mais elegantes de toda a área — a partir de qualquer configuração dada, apenas metade deles é alcançável. São 9!/2 = 181.440 configurações resolvíveis (REINEFELD, 1993). As outras 181.440 formam um universo paralelo: perfeitamente desenháveis no papel, e a distância infinita de qualquer sequência de movimentos.
O espaço de estados do jogo de 8 peças é desconexo: duas metades do mesmo tamanho, sem nenhuma aresta entre elas.
A explicação é uma invariante de paridade: cada movimento troca o vazio de lugar com uma peça e altera a paridade das inversões da sequência de forma acoplada à paridade da linha do vazio. Como toda ação preserva essa combinação, ela nunca muda — e configurações com paridade diferente da inicial simplesmente não têm caminho. O resultado foi demonstrado por William Woolsey Johnson e William Edward Story em 1879, para o irmão mais velho do problema, o quebra-cabeça de 15 peças que fazia furor à época (JOHNSON; STORY, 1879).
Guarde a lição, porque ela vale muito além de brinquedos de madeira: a formulação não decide só o quanto o problema é difícil — decide o que é possível. Um algoritmo de busca perfeito, rodando em um computador infinito, jamais encontrará solução para uma instância do outro lado do abismo. Não é falha do algoritmo. É a estrutura do espaço.
Já do lado alcançável, o quebra-cabeça de 8 peças é pequeno o bastante para ter sido resolvido por completo. A solução ótima mais longa que existe tem 31 movimentos, e a média sobre todas as configurações resolvíveis é de 21,97 movimentos (REINEFELD, 1993).
Estado 07
A conta que assombra qualquer busca
Se o de 8 peças é dócil, seus irmãos não são. Basta aumentar a grade para que a mesma fórmula, n!/2, produza números que deixam de ter significado intuitivo.
Tabela 1 — Configurações alcançáveis em quebra-cabeças de peças deslizantes, segundo o tamanho da grade
| Quebra-cabeça | Grade | Arranjos possíveis (n!) | Configurações alcançáveis (n!/2) |
|---|---|---|---|
| 8 peças | 3 × 3 | 362 880 | 181 440 |
| 15 peças | 4 × 4 | 2,09 × 10¹³ | 1,05 × 10¹³ |
| 24 peças | 5 × 5 | 1,55 × 10²⁵ | 7,76 × 10²⁴ |
Fonte: elaborado pelo autor; valores do quebra-cabeça de 8 peças conferidos em Reinefeld (1993).Nota: n é o número de posições da grade, incluindo o espaço vazio. Valores das grades 4 × 4 e 5 × 5 calculados pelo autor a partir de n!/2 e arredondados para três algarismos significativos.
O nome disso é explosão combinatória, e ela tem uma forma canônica: se cada estado gera b sucessores em média e a solução está a d passos de distância, o número de estados a considerar cresce como b elevado a d. Aumentar a profundidade em um único nível não soma trabalho — multiplica.
Com ramificação 3, o décimo nível já tem 59.049 nós. Com ramificação 30 — a média do xadrez —, o quarto nível passa de 800 mil.
A explosão combinatória não é um detalhe de implementação: é o adversário. Outros conceitos que trataremos em outra postagem no futuro, como largura, profundidade, custo uniforme, aprofundamento iterativo e as buscas informadas, na verdade constituem um repertório de respostas a ela. As buscas cegas atacam o problema organizando a ordem em que os estados são visitados. As informadas atacam usando conhecimento sobre o domínio para não visitar a maioria deles. Mas nenhuma delas salva uma formulação ruim: se o espaço de estados foi mal desenhado, o melhor algoritmo do mundo apenas fracassa mais rápido.
Aplicação prática
Formule um problema em seis passos
Marque os itens conforme conseguir responder a cada um sobre um problema da sua própria área — logística, saúde, educação, engenharia, direito, o que for.
0 de 6 — comece pelo estado.
Estado-objetivo
O que fica antes do algoritmo
A tentação, em uma disciplina de IA, é correr para os algoritmos. Eles são a parte vistosa: dá para animar, cronometrar, comparar. Mas os algoritmos de busca cega são, todos eles, variações de uma mesma pergunta — em que ordem eu olho os vizinhos? A pergunta que os antecede é mais difícil e não tem pseudocódigo: o que, exatamente, é um vizinho aqui?
Alcuíno levou seus jovens monges a atravessar o rio sem escrever uma linha de matemática. Newell, Shaw e Simon tentaram construir uma máquina que atravessasse qualquer rio. Entre os dois está a ideia que sustenta toda a resolução de problemas por busca: descrever um problema como estados, ações e custos é o ato que o torna mecanizável — e, ao mesmo tempo, o ato que decide quanto do mundo real vai sobrar na descrição.
Pense no problema mais chato da sua rotina profissional. Se você tivesse que descrevê-lo em cinco componentes para um agente resolver, qual deles você não conseguiria escrever — e o que isso diz sobre o problema?
Nota do autor: os valores das grades 4 × 4 e 5 × 5 da Tabela 1 são cálculo direto do autor a partir de n!/2 e foram arredondados para três algarismos significativos; apenas os do quebra-cabeça de 8 peças aparecem explicitamente em Reinefeld (1993), que também é a fonte da solução ótima máxima de 31 movimentos e da média de 21,97. A datação das Propositiones ad acuendos juvenes por volta do ano 800 e sua atribuição a Alcuíno de York são as aceitas por Hadley e Singmaster (1992), que registram, contudo, que a autoria não é documentalmente certa. As traduções de trechos e a terminologia em português dos cinco componentes seguem o uso corrente em Luger (2013), com ajustes do autor para aproximar da formulação de Russell e Norvig (2021), cuja quarta edição não tem tradução brasileira publicada até a data deste texto.
Referências
- HADLEY, John; SINGMASTER, David. Problems to sharpen the young. The Mathematical Gazette, Leicester, v. 76, n. 475, p. 102-126, mar. 1992. Disponível em: https://www.jstor.org/stable/3620384. Acesso em: 22 ago. 2026.
- JOHNSON, William Woolsey; STORY, William Edward. Notes on the "15" puzzle. American Journal of Mathematics, Baltimore, v. 2, n. 4, p. 397-404, dez. 1879. Disponível em: https://www.jstor.org/stable/2369492. Acesso em: 22 ago. 2026.
- LUGER, George F. Inteligência artificial. 6. ed. São Paulo: Pearson Education do Brasil, 2013.
- NEWELL, Allen; SHAW, John Clifford; SIMON, Herbert Alexander. Report on a general problem-solving program. In: INTERNATIONAL CONFERENCE ON INFORMATION PROCESSING, 1959, Paris. Proceedings. Paris: UNESCO, 1960. p. 256-264.
- REINEFELD, Alexander. Complete solution of the eight-puzzle and the benefit of node ordering in IDA*. In: INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 13., 1993, Chambéry. Proceedings. San Francisco: Morgan Kaufmann, 1993. p. 248-253. Disponível em: https://www.ijcai.org/Proceedings/93-1/Papers/035.pdf. Acesso em: 22 ago. 2026.
- RUSSELL, Stuart; NORVIG, Peter. Artificial intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2021.
Comentários