0
$\begingroup$

I am working on a Prolog university assignment, where we have to determine what the shortest time is for 4 wounded soldiers to cross a bridge to safety. This seems to be a variation of the more common '4 people are crossing a bridge at night' puzzle.

The rules are that 2 soldiers can cross at a time, and they have to use a torch. After each crossing, 1 soldier returns with the torch. This process continues until all soldiers have crossed the bridge.

The crossing times for the soldiers are as follows:

  • Soldier 1: 25 minutes
  • Soldier 2: 10 minutes
  • Soldier 3: 20 minutes
  • Soldier 4: 5 minutes

I have written a Prolog program that does this calculation (using depth-first search). I just want to confirm whether my results are correct.

The shortest time is 60 minutes, with 2 possible combinations:

  • Soldiers 2 and 4 cross, taking 10 minutes (total time 10 minutes)
  • Soldier 2 returns with the torch, taking 10 minutes (total time 20 minutes)
  • Soldiers 1 and 3 cross, taking 25 minutes (total time 45 minutes)
  • Soldier 4 returns with the torch, taking 5 minutes (total time 50 minutes)
  • Soldiers 2 and 4 cross, taking 10 minutes (total time 60 minutes)

  • Soldiers 2 and 4 cross, taking 10 minutes (total time 10 minutes)
  • Soldier 4 returns with the torch, taking 5 minutes (total time 15 minutes)
  • Soldiers 1 and 3 cross, taking 25 minutes (total time 40 minutes)
  • Soldier 2 returns with the torch, taking 10 minutes (total time 50 minutes)
  • Soldiers 2 and 4 cross, taking 10 minutes (total time 60 minutes)

My program is giving me 108 total solutions. Is this correct?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

I confirm that 60 is the minimum, and there are exactly 2 such optimal solutions. I solved this as a shortest path problem, as described here: https://math.stackexchange.com/a/3389988/683666

$\endgroup$
1
$\begingroup$

In addition to RobPratt's answer about the minimum time, here's the answer to the number of solutions:

108 solutions does seem correct. It's a simple combinations problem where you need to find how many combinations of soldiers are possible to send over the bridge(nCr) and then multiply all results of the steps with each other.

At first we have 4 soldiers on one side and 0 on the side. 2 of them cross, leaving 2 on one side and 2 on the other. There are $4C2 = 6$ different ways to choose the first 2 soldiers:

1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

Then, 1 of the 2 should go back($2C1$), there are only 2 combinations. Then we have 3 soldiers on the first side, and 2 of them should cross, which is $3C2 = 3$. Next step is to send one of the three soldiers back to get the last soldier($3C1 = 3$) and as the last step both remaining soldiers cross the bridge(2C2 = 1).

If we then multiple all possible combinations with each other, we do indeed get 108:

$6*2*3*3=108$

Note, that this number is a minimum as long as you follow your rule of "2 soldiers can cross at a time, and they have to use a torch. After each crossing, 1 soldier returns with the torch". If at some point you decide to only send one soldier to the other side or send two of them back to the beginning, the number of "solutions" will approach infinity

$\endgroup$
1
  • 1
    $\begingroup$ I also confirm that there are 108 paths of length 5 from source to sink. $\endgroup$
    – RobPratt
    Commented Aug 11, 2023 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.