Difícil test japonés
Reglas:
Todo el mundo tiene que cruzar el río.
Sólo 2 personas pueden cruzar a la vez.
El padre no puede permanecer/estar con ninguna de sus hijas sin que esté presente la madre.
La madre no puede permanecer/estar con ninguno de sus hijos sin que esté el padre.
El ladrón (el del uniforme carcelario) no puede permanecer/estar con ningún miembro de la familia sin la presencia del policía.
Sólo saben manejar la balsa 3 personas: la madre, el padre y el policía, sin uno de ellos a bordo, la balsa no se mueve.
¿Listo?
Este es un típico ejercicio de Backtracking que aprendí en la facu en algo 2: Los problemas que deben satisfacer un determinado tipo de restricciones son problemas completos, donde el orden de los elementos de la solución no importa. Estos problemas consisten en un conjunto (o lista) de variables a la que a cada una se le debe asginar un valor sujeto a las restricciones del problema. La técnica va creando todas las posibles combinaciones de elementos para obtener una solución. Su principal virtud es que en la mayoría de las implementaciones se puede evitar combinaciones, estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución.