Um quebra-cabeça de travessia do rio é um tipo de quebra-cabeça de transporte, no qual o objetivo é levar itens de uma margem para outra. A dificuldade do quebra-cabeça surge a partir de restrições sobre quais ou quantos itens podem ser transportados ao mesmo tempo, ou a partir de quais ou quantos itens podem seguramente ser deixados juntos em uma margem. As definições podem variar cosmeticamente, por exemplo, substituindo o rio por uma ponte. Os primeiros problemas conhecidos de travessia do rio ocorrem no manuscrito Propositiones ad Acuendos Juvenes, tradicionalmente atribuídos a Alcuíno. Os primeiros exemplares deste manuscrito datam do século IX; Ele contém três problemas de travessia do rio, incluindo o problema do fazendeiro, o lobo, o carneiro e a alface e o problema dos maridos ciumentos.
Quebra-cabeças de travessia do rio bem conhecidos incluem:
O problema do fazendeiro, o lobo, o carneiro e a alface em que um fazendeiro deve transportar um lobo, um carneiro e uma alface de um lado para o outro do rio usando um barco que só pode conter um item para além do fazendeiro, sujeito às restrições de que o lobo não pode ser deixado sozinho com o carneiro, e o carneiro e não pode ser deixado sozinho com a alface. O problema dos maridos ciumentos, em que três casais devem atravessar um rio com um barco que pode conter no máximo duas pessoas, sujeito a restrição de que nenhuma mulher pode estar na presença de outro homem a não ser que seu marido também esteja presente. Este problema é equivalente ao problema dos canibais e missionários, em que três missionários e três canibais precisam atravessar um rio, com a restrição de que a qualquer momento quando tanto missionários quanto canibais estão em pé em uma das margens, o número de canibais não pode ultrapassar os missionários. O problema da ponte e da tocha. Propositio de viro et muliere ponderantibus plaustrum. Neste problema, ocorrendo também nas Propositiones ad Acuendos Juvenes, um homem e uma mulher de igual peso, juntamente com dois filhos, cada um com metade de seu peso, querem atravessar um rio com um barco que só pode carregar o peso de um adulto.
Esses problemas podem ser analisados usando métodos da teoria dos grafos,.. por programação dinâmica,. ou por programação inteira..
Categoria:Quebra-cabeças