Resolviendo el Clásico Cruce de Río: Zorro, Gallina, Grano

El “Smart Kit River Crossing Game” es una versión digital del clásico rompecabezas lobo-cabra-col (o zorro-gallina-grano) —un problema de satisfacción de restricciones que data al menos del siglo IX en Europa. El reto: transportar tres objetos a través de un río con una barca que solo cabe un objeto más el operador, sin dejar pares conflictivos solos.

Secuencia de Solución

Estado inicial: Zorro, Gallina, Grano | Barca | (orilla lejana vacía)

1. Llevar Gallina al otro lado. (Zorro y Grano seguros juntos —zorro no come grano)
2. Regresar solo.
3. Llevar Zorro al otro lado.
4. Traer Gallina DE VUELTA. (Paso crítico —no se puede dejar Zorro y Gallina juntos)
5. Llevar Grano al otro lado. (Zorro y Grano seguros juntos)
6. Regresar solo.
7. Llevar Gallina al otro lado.

Estado final: (orilla cercana vacía) | Barca | Zorro, Gallina, Grano

Por Qué Funciona: Análisis de Restricciones

Pares prohibidos (sin supervisión): Zorro+Gallina (depredación), Gallina+Grano (consumo).
Pares seguros: Zorro+Grano (sin interacción).
Clave: La Gallina entra en conflicto con AMBOS otros —es el “nodo central” en el grafo de conflictos. Por tanto, la Gallina debe ser el elemento shuttle: movida primero, traída de vuelta, movida al final. El Zorro y el Grano nunca interactúan directamente.

Enfoque Generalizable de Resolución de Problemas

1. Modelar restricciones explícitamente —listar todos los estados prohibidos.
2. Identificar el elemento más restringido —aquí, la Gallina.
3. Trabajar hacia atrás desde la meta —el movimiento final debe traer el último elemento.
4. Usar búsqueda en espacio de estados —BFS/DFS encuentra solución óptima (7 movimientos mínimo).
5. Verificar que no ocurran estados prohibidos —incluyendo durante el tránsito en barca.

Variaciones y Extensiones

Misioneros y caníbales (3 cada uno, barca cabe 2). Maridos celosos (3 parejas, barca cabe 2, ninguna esposa con otro marido salvo que el suyo esté presente). Versiones modernas añaden límites de tiempo, múltiples barcas, o restricciones dinámicas. La lógica central permanece: satisfacción de restricciones mediante búsqueda en espacio de estados.