Rompecabezas de cruce de río
Un rompecabezas de cruce de río es un tipo de rompecabezas en el que el objetivo es transportar elementos de una orilla a otra, generalmente en la menor cantidad de viajes. La dificultad del rompecabezas puede deberse a restricciones sobre qué o cuántos elementos se pueden transportar al mismo tiempo, o cuáles o cuántos elementos se pueden dejar juntos de forma segura. [1] El entorno puede variar cosméticamente, por ejemplo, al reemplazar el río por un puente. [1] Los primeros problemas conocidos de cruce de ríos se encuentran en el manuscrito Propositiones ad Acuendos Juvenes (en inglés: Problemas para agudizar a los jóvenes ), que tradicionalmente se dice que fue escrito por Alcuin. Las primeras copias de este manuscrito datan del siglo IX; contiene tres problemas de cruce de ríos, incluido el rompecabezas del zorro, el ganso y la bolsa de frijoles y el problema de los maridos celosos . [2]
Estos problemas pueden analizarse utilizando métodos de teoría de gráficos , [4] [5] mediante programación dinámica , [6] o mediante programación de enteros . [3]
