Probability of Knight to remain in the chessboard | size of the chessboard ; Direction vector for the Knight ; returns true if the knight is inside the chessboard ; Bottom up approach for finding the probability to go out of chessboard . ; dp array ; For 0 number of steps , each position will have probability 1 ; for every number of steps s ; for every position ( x , y ) after s number of steps ; For every position reachable from ( x , y ) ; if this position lie inside the board ; store the result ; return the result ; number of steps ; Function Call
N = 8 NEW_LINE dx = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] NEW_LINE dy = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ] NEW_LINE def inside ( x , y ) : NEW_LINE INDENT return ( x >= 0 and x < N and y >= 0 and y < N ) NEW_LINE DEDENT def findProb ( start_x , start_y , steps ) : NEW_LINE INDENT dp1 = [ [ [ 0 for i in range ( N + 5 ) ] for j in range ( N + 5 ) ] for k in range ( steps + 5 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT dp1 [ i ] [ j ] [ 0 ] = 1 NEW_LINE DEDENT DEDENT for s in range ( 1 , steps + 1 ) : NEW_LINE INDENT for x in range ( N ) : NEW_LINE INDENT for y in range ( N ) : NEW_LINE INDENT prob = 0.0 NEW_LINE for i in range ( 8 ) : NEW_LINE INDENT nx = x + dx [ i ] NEW_LINE ny = y + dy [ i ] NEW_LINE if ( inside ( nx , ny ) ) : NEW_LINE INDENT prob += dp1 [ nx ] [ ny ] [ s - 1 ] / 8.0 NEW_LINE DEDENT DEDENT dp1 [ x ] [ y ] [ s ] = prob NEW_LINE DEDENT DEDENT DEDENT return dp1 [ start_x ] [ start_y ] [ steps ] NEW_LINE DEDENT K = 3 NEW_LINE print ( findProb ( 0 , 0 , K ) ) NEW_LINE