Knight on a Chess Board

962.0K Views

Given the size of the chess board and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board.

Note:-
1) The knight makes its all 8 possible moves with equal probability.
2) Once the knight is outside the chess board it cannot come back inside.

Puzzlefry added Info-
This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence.

Share
Add Comment

  • 2 Answer(s)

    After removing mirror images, there are six unique positions on the board: (1,1), (1,2), (1,3), (2,2), (2,3), (3,3).  The knight starts at (3,3).

    From each position, there is a fixed probability of moving to each of the other five positions.  The probability of moving off the board is 1 minus the sum of the probabilities of moving to other board positions.

     .      -------- starting position --------
     .      (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)
     (1,1)                          .250
     (1,2)              .250  .250        1.000
     (1,3)        .125              .250
     (2,2)        .125              .250
     (2,3)  .250        .250  .250
     (3,3)        .125
     

    A quick examination reveals that positions (1,3) and (2,2) are equivalent–they each have the same probability for the following square.  So we can collapse them into a single state we’ll label as (*,*), giving the following five position table.

     .      ----- starting position -----
     .      (1,1) (1,2) (*,*) (2,3) (3,3)
     (1,1)                    .250
     (1,2)              .250        1.000
     (*.*)        .250        .500
     (2,3)  .250        .250
     (3,3)        .125
     

    The probability for the knight to be in each of the five positions at the end of k moves is the sum of the product of probability of the knight moving to that position from another position and the probability of having been in that position at the end of k-1 moves.  At zero moves, the probability of being in position (3,3) is 1 and the probability of being elsewhere on the board is 0.  After each move, the probability of the knight having moved off the board is 1 minus the sum of the probabilities of it being in each position.

     k  (1,1)  (1,2)  (*,*)  (2,3)  (3,3)   Off board
     0                              1.00000
     1         1.00000
     2                0.25000       0.12500  0.62500
     3         0.18750       0.06250         0.75000
     4  0.01563       0.07813       0.02344  0.88281
     5         0.04297       0.02344         0.93359
     6  0.00586       0.02246       0.00537  0.96631
     7         0.01099       0.00708         0.98193
     8  0.00177       0.00629       0.00137  0.99057
     9         0.00294       0.00201         0.99504
     10 0.00050       0.00174       0.00037  0.99739
     
    dougbell Genius Answered on 15th September 2015.
    Add Comment

    ALGORITHM:
    Start with the initial coordinates of the knight.
    Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.

    As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.

    For better understanding and Computer program of the algo – crazyforcode.com

    SherlockHolmes Expert Answered on 23rd August 2015.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-