The Bridge and Torch Problem is a classic logic puzzle made famous by tech job interviews at companies like Microsoft and Google.
The intuitive trap of the puzzle lies in assuming that the fastest person should always act as the group’s “shuttle driver”, escorting others across and returning with the torch. However, when the speed differences among group members are large, this strategy is sub-optimal.
Imagine four people (A, B, C, and D) standing on the left bank of a river at night, needing to cross to the other side via a narrow, dangerous bridge. The rules for crossing are:
Individual Speeds: Each person takes a different amount of time to cross the entire bridge:
Person A: 1 minute.
Person B: 2 minutes.
Person C: 5 minutes.
Person D: 10 minutes.
Bridge Capacity: The bridge can hold at most two people at a time.
Torch Requirement: It is dark, and they have only one shared torch. To cross safely in either direction, the group crossing must carry the torch at all times.
Walking Pace: When two people cross together, they walk at the pace of the slower person.
The key question to answer is: What is the minimum total time required for all four people to reach the other side?
Solution to the challenge
Solving riddle yields the following optimal trip plan:
Trip
Direction
People Crossing
Trip Duration
Cumulative Time
Trip 1
Outbound (Left $\rightarrow$ Right)
People A and B
2 min
2 min
Trip 2
Return (Right $\rightarrow$ Left)
Person A
1 min
3 min
Trip 3
Outbound (Left $\rightarrow$ Right)
People C and D
10 min
13 min
Trip 4
Return (Right $\rightarrow$ Left)
Person B
2 min
15 min
Trip 5
Outbound (Left $\rightarrow$ Right)
People A and B
2 min
17 min
Result: The minimum total time required for all 4 people to cross the bridge is 17 minutes.
The strategic key lies in Trip 3: by sending the two slowest people (C and D) together, we absorb C’s time (5 min) within D’s 10-minute trip, saving valuable time.
This puzzle can be formulated systematically as a Mixed Integer Linear Optimization model. Care to give it a try?
To solve the bridge crossing problem systematically, we first determine the required number of trips. For $N=4$ people, $T = 2N - 3 = 5$ trips are needed (3 forward trips to cross and 2 return trips to bring the torch back).
Sets of indices
\(\mathcal{P} = \{\text{A}, \text{B}, \text{C}, \text{D}\}\): Set of people.
\(\mathcal{T} = \{1, 2, 3, 4, 5\}\): Set of trips. Odd trips ($t \in {1, 3, 5}$) are outbound (left to right), and even trips ($t \in {2, 4}$) are return trips (right to left).
Parameters
\(c_p\): Time required for person $p \in \mathcal{P}$ to cross the bridge ($c_A=1$, $c_B=2$, $c_C=5$, $c_D=10$).
Decision Variables
\(x_{pt} = 1\) if person $p \in \mathcal{P}$ crosses the bridge on trip $t \in \mathcal{T}$, and $0$ otherwise.
\(y_{pt} = 1\) if person $p \in \mathcal{P}$ is located on the destination side (right) after trip $t \in \mathcal{T}$, and $0$ otherwise (with $y_{p0} = 0 \; \forall p \in \mathcal{P}$).
\(w_t \geqslant 0\): Duration of trip $t \in \mathcal{T}$.
The objective is to minimize the total accumulated time across all trips:
Objective Function
\[\min z = \sum_{t \in \mathcal{T}} w_t\]
We define the movement logic using linear constraints:
Bridge Capacity and Torch Return:
On outbound trips (\(t \in \{1, 3, 5\}\)), between 1 and 2 people must cross:
Want to keep exploring the world of Operations Research? Discover more posts on the topic here.
If you found this useful, please cite this as:
Martín-Campo, F. Javier (May 2026). Crossing the Bridge at Night. https://www.fjmartincampo.com/blog/2026/bridgecrossing/.
or as a BibTeX entry:
@misc{martín-campo2026crossing-the-bridge-at-night,title={Crossing the Bridge at Night},author={Martín-Campo, F. Javier},year={2026},month={May},url={https://www.fjmartincampo.com/blog/2026/bridgecrossing/}}
Enjoy Reading This Article?
Here are some more articles you might like to read next:
