Travessia do rio

1. Personagens

🐺 Lobo, 🐐 Cabra, 🥬 Alface e o 🚣 fazendeiro com barco. Todos começam à esquerda.

2. Objetivo

Levar todos à margem direita com o fazendeiro no barco. Estado objetivo: (1, 1, 1, 1) — lobo, cabra, alface e barco valendo 1.

3. Estado

(lobo, cabra, alface, barco) — cada um em margem 0 (esquerda) ou 1 (direita). Início: (0, 0, 0, 0).

4. Quem não pode ficar com quem

Sem o fazendeiro numa margem, valem as regras:

Exemplo: se o 🚣 atravessa para a direita, quem ficou à esquerda não pode ser só 🐺+🐐 nem só 🐐+🥬. O mesmo vale para a margem direita quando o barco está à esquerda. Violar isso encerra a partida.

5. Ações

O 🚣 sempre viaja no barco. Você pode atravessar sozinho ou levando um personagem que esteja na mesma margem.

6. Poda na busca

Movimentos que violam essas regras nem geram sucessores — o algoritmo nunca expande estados inválidos.