Knight Probability In Chessboard


@yunli We want the probability the knight remained on the board after K moves. The probability the knight remained and is on the square
(r, c)
isdp[r][c]
. So we want the sum of alldp[r][c]
.

This problem can be viewed as a timehomogeneous Markov chain with a finite state space. There are 65 states (
064
): being on the square at rowr
and columnc
(states164
) or being off the board (state0
).For
i > 0
statei
corresponds to the square in row and column (base zero) given by (in Ruby)(i1).divmod(8)
. For example,(11).divmod(8) #=> [0,0]; (261).divmod(8) #=> [3,1]; (651).divmod(8) #=> [7,7]
.Let
M
be the transition matrix, wherem(i,j)
is the probability of going from statei
to statej
in one move.m(0,0) = 1
andm(0,j) = 0
for allj > 0
, since the knight is not permitted to move from state0
to any other state (that is, state0
is an absorbing state). If statesi
andj
correspond to squares on the board,m(i,j) = 1.0/8
if statej
can be reached from statei
in one move. and equals zero otherwise.m(i,0)
is computed in the obvious way.Let
p
equal a discrete probability distribution of the initial state. Suppose the starting square is[r,c]
(zero based), which is states = 8*r+c1
. Thenp(s) = 1.0
andp(j) = 0
forj != s
. The probability distribution of the knight's location (state) after one move is thereforep*M
, after two moves isp*M*M
and aftern
moves isq(n) = p*M**n
.q(n)[0]
(1q(n)[0]
) is therefore the probability of being off (on) the board aftern
moves.q(n)
converges to a steadystate vectorq
asn
goes to infinity. We can computeq
from the observation that, at steadystate,q*M = q
andq*i = 1
, wherei
is ann
vector of1
's. We can then writeq*(MI) = 0
, whereI
is an identity matrix and0
is a vector of zeros. Now add another row of1
's toMI
to obtain the matrixQ
. We now haveq*Q = v
, wherev
is an+1
vector whose last element is1
and all other elements are0
. We now postmultiply both sides byT
, the transpose ofQ
, to obtainq*Q*T = v*T
(Q*T
being a square matrix), soq = v*T*Z
whereZ
is the inverse ofQ*T
.We don't have to go to the trouble of calculating
q
this way, however. When there is a single absorbing state which, as here, can be reached from any other state (after one or more moves) with a positive probability, we are bound to get to the absorbing state eventually, so we know thatq[0] = 1
andq[i] = 0
fori > 0
. I presented the general calculation for interest only.

@surikaks
There you godef knightProbability(self, N, K, r, c): directions = ((2,1),(2,1),(2,1),(2,1),(1,2),(1,2),(1,2),(1,2)) def search(row, col, k, cache={}): if (row, col, k) in cache: return cache[(row, col, k)] if k == 0: return 1. p = 0 for (i, j) in map(lambda (x, y): (x + row, y + col), directions): if 0 <= i < N and 0 <= j < N: p += 1/8. * search(i, j, k  1) return cache.setdefault((row, col, k), p) return search(r, c, K)