This is classical problem of dynamic programming. step-1: For each cell, calculate the possibility of knight (horse) staying inside chess board after 1 step. For example: corner cells will have possibility of 2/8. Now, for each cell maintain valid steps (i.e. where all it can step..)
step-2: Now we know probability and valid steps for each cell where N = 1 Reuse this data to calculate probability for N = 2 This can be done as below: for prob of knight inside board for (cell XY and N =2) = cell's prob (like 2/8 ) x each valid possible 1 step cell's prob Example: prob for (corner cell for N =2 ) = 2/8 * 6/8 * 6/8 For Nth move, repeat step-2 N times and reuse data at each step. On Sun, Jun 20, 2010 at 4:21 PM, sharad <[email protected]> wrote: > On a empty chessboard, a horse starts from a point( say location x,y) > and it starts moving randomly, but once it moves out of board, it cant > come inside. So what is the total probability that it stays within the > board after N steps. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
