Probability: Will the knight remain on chess board after K moves

[Shyam Prakash Velupula]

Scenario: One knight is placed randomly on a cell of empty chess board.
               The Knight dies, if any of it's (standard) move crosses the boundary of chess board

               Now, what's the probability that, Knight remains on board after K random moves (in any direction).

Thanks
Shyam Velupula


--
You are limited only by your imagination

[bhargava]

Does this require work with matrices ?

[Shyam Prakash Velupula]

I have no idea as I don't know the answer for this.

Thanks
Shyam Velupula

On Mon, Jul 11, 2011 at 12:41 PM, bhargava <bhargav...@gmail.com> wrote:

Does this require work with matrices ?

[SURI]

Yes Bhargav, As you said you need to come up with a matrix of
probabilities. Probability at each position says the chance of staying
the knight at this position after n moves.

If we consider standard chess board of size 8X8 then we can nail down
the number of cells to 10 due to the symmetry. we would get 10X10
matrix of probabilities and the go foreword.

Now I don't recall the exact process to solve this problem.. But this
is the big hint to go further..

-- SURI

[bhargava]

I thought upto that point, but wanted to confirm if i am going in the
right direction.

[bhargava]

I can't think of any direct way of getting into nth matrix.

Compute level 0 matrix which should contain all 1's

Apply 8 transformations to the matrix to represent the move from 8 different directions, and sum the matrices to get the first level matrix
Keep doing it till you get the nth level matrix