Cruzar el río

River Crossing es una familia de rompecabezas lógicos clásicos donde el jugador debe transportar un grupo de personajes o objetos a través de un río utilizando un barco con capacidad limitada, sujeto a limitaciones específicas. Ciertas combinaciones de pasajeros no pueden dejarse solos en cualquier banco, por ejemplo, un lobo comería una cabra, o una cabra comería repollo. El jugador debe encontrar una secuencia de viajes en barco que mueve a todo el mundo sin violar ninguna restricción.

Reglas (lobo, cabra y col clásicos)

1. Un agricultor debe transportar un lobo, una cabra y un repollo a través de un río.
2. El barco sólo puede llevar el agricultor y otro artículo a la vez.
3. El agricultor debe estar en el barco para cada cruce (el barco no puede cruzar por su cuenta).
4. El lobo y la cabra no pueden dejarse solos juntos (el lobo comería la cabra).
5. La cabra y el repollo no pueden dejarse solos juntos (la cabra comería el repollo).
6. El lobo y el repollo se pueden dejar solos de forma segura.
7. El objetivo es llevar los cuatro (farma, lobo, cabra, repollo) al otro lado.

Solución (puzzle clásico)

1. El agricultor cruza la cabra.
2. Farmer vuelve solo.
3. El agricultor cruza el lobo.
4. El agricultor trae la cabra de vuelta.
5. El agricultor cruza el repollo.
6. El agricultor vuelve solo.
7. El agricultor cruza la cabra.

Total: 7 cruces.

Variantes comunes

• Misioneros y Caníbals: 3 misioneros y 3 caníbales deben cruzar; los caníbales nunca pueden superar a los misioneros en ninguno de los dos bancos.
• Maridos celosos: 3 parejas deben cruzar; ninguna mujer puede estar en un banco con otro hombre a menos que su marido esté presente.
• Bridge and Torch: 4 personas cruzan un puente por la noche con una linterna; sólo dos pueden cruzar a la vez; cada persona camina a una velocidad diferente; el par se mueve al ritmo de la persona más lenta.
• Grupos Larger**: Versiones ampliadas con más caracteres y gráficos de limitación más complejos.

Estrategias

• Identificar el Constraint Crítico* Determinar qué carácter o elemento causa más conflictos. En el rompecabezas clásico, la cabra conflictos con el lobo y el repollo, lo que lo convierte en la pieza clave para manejar.
• The Shuttle Technique: A veces debe traer un artículo de vuelta al lado inicial para resolver un conflicto. Este movimiento "backward" contraintuitivo es a menudo la visión clave.
• Piensa en Estados: Representar cada posible configuración de elementos en ambos bancos como un "estado". El rompecabezas se convierte en encontrar un camino a través de estados válidos desde el principio hasta el objetivo.
• Minimize Crossings: La solución óptima utiliza los mínimos cruces posibles. Para el rompecabezas clásico, 7 cruces es óptimo.
• Conflicto Gráfico: Dibujar un gráfico de los cuales ítems conflicto. El artículo con la mayoría de los conflictos generalmente necesita el manejo más cuidadoso, a menudo debe viajar primero y puede ser necesario ser transferido de vuelta.
• *Trabaja atrás* A veces ayuda a pensar en lo que los últimos pasos deben parecer y trabajar hacia atrás para determinar movimientos anteriores.

Los rompecabezas de cruce de ríos se encuentran entre los rompecabezas lógicos más antiguos conocidos, con la primera versión grabada que aparece en el manuscrito medieval "Proposiciones ad Acuendos Juvenes" (Problemas a Sharpen the Young), atribuido a Alcuin de York alrededor de 800 CE. Alcuin era un académico inglés y asesor del emperador Charlemagne, y su colección incluía el problema de lobo, cabra y repollo junto con varios otros rompecabezas matemáticos. Esto hace que los puzzles de cruce de ríos de más de 1.200 años.

La variante "Misioneros y Caníbals" surgió en el siglo XIX y se convirtió en un problema estándar en la investigación de inteligencia artificial en el siglo XX. Fue uno de los primeros problemas utilizados para demostrar algoritmos de búsqueda del espacio-estado. En 1968, Amarel lo utilizó como estudio de caso para la representación de problemas en AI, mostrando cómo la elección de representación afecta dramáticamente la dificultad de encontrar una solución. El problema ha aparecido desde entonces en innumerables libros de texto AI.

El problema "Bridge and Torch" ganó fama popular cuando se convirtió en una conocida pregunta de entrevista en las empresas tecnológicas a finales de los años 1990 y 2000, particularmente en Microsoft. Desafía a los candidatos a optimizar el tiempo total de cruce cuando los individuos tienen diferentes velocidades, un desafío fundamentalmente diferente de la naturaleza de restricción-satisfacción del clásico cruce de ríos.

Los rompecabezas del cruce de ríos han sufrido durante más de un milenio porque enseñan habilidades fundamentales para resolver problemas: romper una situación compleja en los estados, identificar limitaciones, considerar movimientos contraintuitivos (traer algo atrás), y explorar sistemáticamente posibilidades. Ellos aparecen en libros de matemáticas recreativas, programas de informática y colecciones de rompecabezas en todo el mundo. Su encuadre narrativo —un granjero, un río, animales hambrientos— hace que la lógica abstracta se sienta concreta e inolvidable.