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
< ? php $ N = 8 ; $ dx = array ( 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 ) ; $ dy = array ( 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 ) ; function inside ( $ x , $ y ) { global $ N ; return ( $ x >= 0 and $ x < $ N and $ y >= 0 and $ y < $ N ) ; } function findProb ( $ start_x , $ start_y , $ steps ) { global $ N , $ dx , $ dy ; $ dp1 = array_fill ( 0 , $ N , array_fill ( 0 , $ N , array_fill ( 0 , $ steps + 1 , NULL ) ) ) ; for ( $ i = 0 ; $ i < $ N ; ++ $ i ) for ( $ j = 0 ; $ j < $ N ; ++ $ j ) $ dp1 [ $ i ] [ $ j ] [ 0 ] = 1 ; for ( $ s = 1 ; $ s <= $ steps ; ++ $ s ) { for ( $ x = 0 ; $ x < $ N ; ++ $ x ) { for ( $ y = 0 ; $ y < $ N ; ++ $ y ) { $ prob = 0.0 ; for ( $ i = 0 ; $ i < 8 ; ++ $ i ) { $ nx = $ x + $ dx [ $ i ] ; $ 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 ] ; } $ K = 3 ; echo findProb ( 0 , 0 , $ K ) . " STRNEWLINE " ; ? >