강 건너기 퍼즐

강 건너기 퍼즐(River crossing puzzle)은 전송 퍼즐(transport puzzle)의 일종으로서 강의 반대편으로 물체를 이동시키는 것을 목적으로 한다. 퍼즐의 난이도는 제한 조건이나, 동시에 이동할 수 있는 품목의 개수 및 동시에 놓였을 때 안전한 조합의 종류로 정해진다. 설정은 매우 다양할 수 있다.

퍼즐의 시초

알려진 가장 오래된 강건너기 퍼즐은 중세의 학자 알퀸의 저서 Propositiones ad Acuendos Juvenes(영재를 위한 문제)에 남아있다.또, 상인들이 사막을 건너면서 이 비슷한 문제를 많이 내기도 했다. 이 필사본은 9세기까지 거슬러 올라가는데, 여기에는 여우, 거위, 콩자루 문제(Fox, goose and bag of beans puzzle)와 선교사와 식인종 문제(Missionaries and cannibals problem)가 들어있다.

퍼즐들의 예

• 여우, 거위, 콩자루 문제 : 농부가 여우, 거위, 콩자루를 가지고 강을 건너려고 한다. 농부가 없을 때, 여우와 거위가 같이 있으면 여우는 거위를 잡아먹고, 거위와 콩자루가 같이 있으면 거위는 콩자루를 먹어 치운다. 노를 저을 수 있는 것은 농부 뿐이며, 한 번에 한 품목만 옮길 수 있다고 할 때, 아무 피해없이 세 품목을 모두 강 건너로 옮겨야 한다.

• 선교사와 식인종 문제 : 선교사 세 명과 식인종 세 명이 강을 건너려고 한다. 강의 어느 쪽이든 선교사보다 식인종의 수가 많게 되면 식인종은 선교사를 해친다. 그러나 선교사와 식인종의 수가 같거나 선교사가 많으면 아무도 해치지 않는다. 한 번에 두 사람만 보트에 탈 수 있다고 할 때, 여섯 사람이 무사히 강을 건너도록 해야 한다.