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
let N = 8 ; let dx = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] ; let dy = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ] ; function inside ( x , y ) { return ( x >= 0 && x < N && y >= 0 && y < N ) ; } function findProb ( start_x , start_y , steps ) { let dp1 = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { dp1 [ i ] = new Array ( N ) ; for ( let j = 0 ; j < N ; j ++ ) { dp1 [ i ] [ j ] = new Array ( steps + 1 ) ; for ( let k = 0 ; k < steps + 1 ; k ++ ) { dp1 [ i ] [ j ] [ k ] = 0 ; } } } for ( let i = 0 ; i < N ; ++ i ) for ( let j = 0 ; j < N ; ++ j ) dp1 [ i ] [ j ] [ 0 ] = 1 ; for ( let s = 1 ; s <= steps ; ++ s ) { for ( let x = 0 ; x < N ; ++ x ) { for ( let y = 0 ; y < N ; ++ y ) { let prob = 0.0 ; for ( let i = 0 ; i < 8 ; ++ i ) { let nx = x + dx [ i ] ; let ny = y + dy [ i ] ; if ( inside ( nx , ny ) ) prob += dp1 [ nx ] [ ny ] [ s - 1 ] / 8.0 ; } dp1 [ x ] [ y ] [ s ] = prob ; } } } return dp1 [ start_x ] [ start_y ] [ steps ] ; } let K = 3 ; document . write ( findProb ( 0 , 0 , K ) ) ;