2
$\begingroup$

Please don't flag me. I am not a duplicate of Crippled King Crossing a Canyon. What are the chances now, if the crippled king only can't walk up and down? The rest of the rules are the same as Crippled King Crossing a Canyon:

A chess king has been injured in battle against an evil wizard, and can no longer move North-East or South-West North or South.

This king is on the North rim of a canyon, and must flee to safety on the South rim. The only way to cross is a bridge, which is a shaped like a standard chessboard.

However, as the king is about to cross, the evil wizard casts a fire spell on all 64 squares of the bridge. Each square is destroyed with a probability of 50%, independently of the others.

What is the probability that the king can cross the canyon via the undestroyed squares?

To be clear, the king is allowed to start on any undestroyed square on the top row of the chessboard, and succeeds as long as he reaches any undestroyed square on the bottom row.

Improve this question
$\endgroup$
10
  • $\begingroup$ The rules are here now. $\endgroup$
    – Anonymous
    Apr 5, 2016 at 5:15
  • 2
    $\begingroup$ Are you sure this one has a 'nice' solution? If not, I feel like this is going to be incredibly difficult without massive amounts of brute force or Monte Carlo. $\endgroup$
    – Deusovi ♦
    Apr 5, 2016 at 5:18
  • $\begingroup$ Brute forcing this doesn't look that massive at all for a modern computer, but I'd also be more pleased with a nicer solution. $\endgroup$
    – ffao
    Apr 5, 2016 at 6:27
  • $\begingroup$ @ffao Brute forcing requires examining 2^64 possible boards, I guess? $\endgroup$
    – justhalf
    Apr 5, 2016 at 6:57
  • $\begingroup$ @justhalf If you do it the straightforward way, yes; but notice that after you fill a certain number of rows, you are only interested in whether the squares in the bottom row are connected to the top row and to each other. This should reduce the search space by a sizable amount. $\endgroup$
    – ffao
    Apr 5, 2016 at 7:03

1 Answer 1

Reset to default
3
$\begingroup$

The probability of the king crossing is exactly

$\frac{11199945737846016929}{2^{64}} \approx 60.715\%$

Given how ugly the answer is, I highly doubt this could be calculated by any way other than brute force. Here is my brute-forcer in C++, which calculates the answer in about 2 seconds.

As a sanity check, you can switch the lines indicated in the code to get the answer to the original Crippled King puzzle.

Improve this answer
$\endgroup$
5
  • $\begingroup$ wait...in the original Crippled King he has a 50% chance of crossing, and now with more restrictions (not allowed up or down) the chance is higher? How can this be? $\endgroup$
    – Marius
    Apr 6, 2016 at 20:21
  • $\begingroup$ This one doesn't restrict any of the diagonals. If you restrict both a diagonal and north-south (by uncommenting both of the lines in the code), his chance dwindles to a mere 7.38% $\endgroup$
    – ffao
    Apr 6, 2016 at 20:23
  • $\begingroup$ Never mind. I understood something wrong. And thanks for the explanation. $\endgroup$
    – Marius
    Apr 6, 2016 at 20:24
  • $\begingroup$ I expect the ugly numerator could probably be expressed by some summation of binomial coefficients. $\endgroup$
    – Jonathan Allan
    Apr 6, 2016 at 21:31
  • $\begingroup$ Hmm, that is a possibility. But I wouldn't even know where to start with that... $\endgroup$
    – ffao
    Apr 6, 2016 at 22:01

Your Answer

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

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