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.
De onde sai o 362.880
Vale desmontar esse número antes de seguir, porque ele é mais simples do que parece. Imagine montar o tabuleiro do zero, casa por casa. Na primeira casa você pode pôr qualquer uma das nove peças — contando o espaço vazio como se fosse uma delas. Escolhida essa, restam oito candidatas para a segunda casa; depois sete para a terceira, seis para a quarta, e assim por diante, até sobrar uma única peça para a última casa. O total de tabuleiros diferentes é o produto de todas essas escolhas: 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362.880. Matemáticos abreviam essa multiplicação como 9! e leem "nove fatorial".
Uma aposta desonesta
Agora a parte estranha. Pegue um tabuleiro resolvido e troque de lugar apenas duas peças, a 7 e a 8. Devolva a ele. À vista, falta um passo para o fim. E eu faço uma aposta desonesta: você pode passar o resto da vida deslizando peças e não vai resolver.
Não é difícil. É impossível. E a prova cabe em três minutos, sem uma única fórmula.
Antes do tabuleiro, três xícaras
Comece por um brinquedo menor. Três xícaras sobre a mesa, todas viradas para baixo. Sua missão é deixar as três viradas para cima. A regra é uma só: você vira exatamente duas por vez.
Tente. Sério — leva vinte segundos, e o resto deste texto depende de você ter tentado.
Não sai. E não é falta de jeito. Conte quantas estão viradas para baixo: três. Virar duas muda esse número em −2, 0 ou +2. Três é ímpar, e somar ou subtrair números pares mantém um total ímpar para sempre. O alvo, zero, é par. Nenhuma sequência de jogadas atravessa essa fronteira.
Três, um, três, um. O contador nunca visita um número par — e o alvo é par.
Isso tem nome. Uma invariante é uma grandeza que as regras do jogo não conseguem mexer. Quando existe uma, ela não deixa o problema difícil: ela parte o mundo em duas metades que não se falam. O tabuleiro de 8 peças esconde uma dessas. Vamos achá-la.
A virada de chave: deslizar é trocar
Repare no que uma jogada de fato faz. Você empurra a peça 5 para o buraco ao lado. Existe outra descrição da mesmíssima coisa: você trocou o conteúdo de duas casas vizinhas — uma tinha o 5, a outra não tinha nada.
Deslizar é trocar. O jogo inteiro passa a ser: arrume o tabuleiro usando só trocas, com a regra de que uma das duas casas trocadas é sempre o buraco. Essa mudança de vocabulário é tudo. Ela converte um problema de geometria — o que encosta em quê — num problema de contagem.
Primeiro fato: toda bagunça nasce com uma etiqueta
Esqueça o buraco por um instante e faça uma pergunta mais folgada: quantas trocas livres — pegar duas peças quaisquer e permutar — bastam para arrumar um tabuleiro?
Parece depender do jeito de cada um. Não depende. Desenhe uma seta de cada peça até a cadeira onde ela deveria estar. As setas nunca se perdem no caminho: elas se fecham em laços. Um laço de 2 peças custa 1 troca. Um laço de 3 peças custa 2. Um laço de L peças custa L − 1 — cada troca senta uma peça no lugar definitivo e encurta o laço em um.
O desenho dos laços não é escolha do jogador: é uma propriedade do tabuleiro. E é ele que dita a conta.
Não há liberdade aqui — o número mínimo de trocas está escrito nos laços. E se você quiser enrolar, fazendo trocas inúteis, cada bobagem terá de ser desfeita depois, o que custa mais uma. As trocas desperdiçadas vêm sempre de duas em duas.
Conclusão: o total pode variar, mas par continua par e ímpar continua ímpar. Todo tabuleiro carrega essa etiqueta de nascença, e nenhuma esperteza a arranca.
Segundo fato: o buraco anda num tabuleiro de xadrez
Agora o buraco. Pinte as nove casas como um tabuleiro de xadrez. A cada jogada o buraco anda uma casa — e casa vizinha é sempre da cor oposta. Escuro, claro, escuro, claro.
Para o quebra-cabeça estar resolvido, o buraco precisa terminar exatamente onde começou. Mesma casa, mesma cor. E só se volta à cor de partida depois de um número par de passos. Ou seja: toda solução tem um número par de jogadas.
Não importa o caminho, nem se ele passeia pelo tabuleiro inteiro: voltar para casa custa um número par de passos.
A colisão
Agora junte os dois fatos e a resposta cai sozinha.
Cada jogada é uma troca. Toda solução tem um número par de jogadas. Logo, toda solução usa um número par de trocas. E o tabuleiro resolvido custa zero trocas — zero é par.
Então só existe caminho até o fim para as bagunças de etiqueta par. As de etiqueta ímpar ficam do outro lado, e nenhuma jogada atravessa uma fronteira de paridade — exatamente como as três xícaras. Metade das bagunças é par, metade é ímpar: são as duas ilhas de 181.440.
De volta à aposta
Volte agora ao tabuleiro do começo. Trocar o 7 com o 8 é, literalmente, uma troca. Uma é ímpar. Com um único gesto você pegou um tabuleiro da metade par e o empurrou para a metade ímpar, de onde nenhuma sequência de jogadas traz de volta.
Não falta um passo. Falta um universo.
Uma troca só. É tudo o que separa um quebra-cabeça de um beco sem saída.
A ponte para quem for adiante
Na literatura técnica você vai encontrar essa mesma história contada de outro jeito: lê-se o tabuleiro como um texto, contam-se os pares de números que aparecem fora de ordem — as inversões — e verifica-se se o total é par ou ímpar. É a mesma etiqueta, calculada por outro caminho: o número de inversões e o número de trocas têm sempre a mesma paridade. Quem prefere a conta, tem a conta; quem prefere o desenho, tem os laços.
O nome formal do que encontramos é invariante de paridade, e 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, em grade 4 × 4, que fazia furor à época (JOHNSON; STORY, 1879). Naquela grade a regra fica um pouco mais elaborada, porque a largura par muda o passeio do buraco; a ideia, porém, é exatamente a mesma — e a moral também.
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 regra de paridade enunciada no texto é a das grades de largura ímpar, como a 3 × 3 do jogo de 8 peças, em que a paridade das inversões se conserva sozinha e a linha do espaço vazio é irrelevante; o critério clássico de Johnson e Story (1879), formulado para a grade 4 × 4 de largura par, combina a paridade das inversões com a linha do vazio e não se aplica diretamente ao tabuleiro menor. O autor conferiu ambas as afirmações por enumeração exaustiva dos 181.440 estados alcançáveis. 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