Resolvendo o Clássico Quebra-Cabeça da Travessia do Rio: Raposa, Galinha, Grão

O "Smart Kit River Crossing Game" é versão digital do clássico quebra-cabeça lobo-cabra-repolho (ou raposa-galinha-grão) — problema de satisfação de restrições datando de pelo menos século IX na Europa. Desafio: transportar três itens através de rio com barco que comporta apenas um item mais o operador, sem deixar pares conflitantes sozinhos.

Sequência da Solução

Estado inicial: Raposa, Galinha, Grão | Barco | (margem oposta vazia)

1. Leve Galinha para outra margem. (Raposa e Grão seguros juntos — raposa não come grão)
2. Volte sozinho.
3. Leve Raposa para outra margem.
4. Traga Galinha DE VOLTA. (Passo crítico — não pode deixar Raposa e Galinha juntas)
5. Leve Grão para outra margem. (Raposa e Grão seguros juntos)
6. Volte sozinho.
7. Leve Galinha para outra margem.

Estado final: (margem inicial vazia) | Barco | Raposa, Galinha, Grão

Por Que Funciona: Análise de Restrições

Pares proibidos (sem supervisão): Raposa+Galinha (predação), Galinha+Grão (consumo).
Pares seguros: Raposa+Grão (sem interação).
Insight-chave: Galinha conflita com AMBOS outros — é "nó central" no grafo de conflitos. Portanto, Galinha deve ser item shuttle: movida primeiro, trazida de volta, movida por último. Raposa e Grão nunca interagem diretamente.

Abordagem Generalizável de Resolução de Problemas

1. Modele restrições explicitamente — liste todos estados proibidos.
2. Identifique elemento mais restrito — aqui, a Galinha.
3. Trabalhe de trás para frente do objetivo — movimento final deve trazer último item.
4. Use busca em espaço de estados — BFS/DFS encontra solução ótima (7 movimentos mínimo).
5. Verifique nenhum estado proibido ocorra — inclusive durante travessia do barco.

Variações e Extensões

Missionários e canibais (3 cada, barco comporta 2). Maridos ciumentos (3 casais, barco comporta 2, nenhuma esposa com outro marido a menos que seu marido presente). Versões modernas adicionam limites de tempo, múltiplos barcos, restrições dinâmicas. Lógica central permanece: satisfação de restrições através de busca em espaço de estados.