Günter Rote:

Crossing the bridge at night

EATCS Bulletin (Bulletin of the European Association for Theoretical Computer Science), No. 78, October 2002, 241-246.

Abstract

We solve the general case of the bridge-crossing puzzle, where n people with different walking speeds have to cross a bridge that can carry at most two people at a time. A flashlight is necessary to cross the bridge but they share only a single flashlight.

The solution is obtained through a graph-theoretic model.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: December 22, 2004.