2

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.

Community
  • 1
Anonymous
  • 473
  • 2
  • 12
  • The rules are here now. – Anonymous Apr 05 '16 at 05:15
  • 2
    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. – Deusovi Apr 05 '16 at 05:18
  • 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. – ffao Apr 05 '16 at 06:27
  • @ffao Brute forcing requires examining 2^64 possible boards, I guess? – justhalf Apr 05 '16 at 06:57
  • @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. – ffao Apr 05 '16 at 07:03
  • What, exactly, does "Up & down" mean? – Jonathan Allan Apr 06 '16 at 03:35
  • Oh, by the way, Paul Evans, I meant only up and down. – Anonymous Apr 06 '16 at 11:40
  • @Jonathan Allan "Up & down" meant that it can't go directly up or directly down. You can still move all diagonal and horizontal. Just not vertical. – Anonymous Apr 06 '16 at 11:41
  • I don't know if there's an elegant solution, so I threw together a simple, inefficient Python program (http://pastebin.com/UjqYg5TH) to attempt a Monte Carlo solution. For one million trials, the king made it across 60.7% of the time. – Ninety-Three Apr 06 '16 at 17:02
  • @Ninety-Three Thanks for the confirming Monte Carlo, I don't think I would ever completely trust my own implementation otherwise! – ffao Apr 06 '16 at 20:12

1 Answers1

3

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.

ffao
  • 21,733
  • 4
  • 68
  • 109
  • 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? – Marius Apr 06 '16 at 20:21
  • 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% – ffao Apr 06 '16 at 20:23
  • Never mind. I understood something wrong. And thanks for the explanation. – Marius Apr 06 '16 at 20:24
  • I expect the ugly numerator could probably be expressed by some summation of binomial coefficients. – Jonathan Allan Apr 06 '16 at 21:31
  • Hmm, that is a possibility. But I wouldn't even know where to start with that... – ffao Apr 06 '16 at 22:01