Well, I approached this problem in this way. I found out the bridges of the graph, and since the graph is given to be a connected one, I calculated the number of failed combinations of placing the soldiers and then calculated the probability.
Here is a link to my code
Can anyone point out where am I going wrong!
Here is the link for the problem