688. Knight Probability in Chessboard


On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

Example:

Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Note:

  • N will be between 1 and 25.
  • K will be between 0 and 100.
  • The knight always initially starts on the board.


    • Approach #1: Dynamic Programming [Accepted]

    Intuition and Algorithm

    Let f[r][c][steps] be the probability of being on square (r, c) after steps steps. Based on how a knight moves, we have the following recursion:

    where the sum is taken over the eight pairs .

    Instead of using a three-dimensional array f, we will use two two-dimensional ones dp and dp2, storing the result of the two most recent layers we are working on. dp2 will represent f[][][steps], and dp will represent f[][][steps-1].

    Complexity Analysis

    • Time Complexity: where are defined as in the problem. We do work on each layer dp of elements, and there are layers considered.

    • Space Complexity: , the size of dp and dp2.

    Approach #2: Matrix Exponentiation [Accepted]

    Intuition

    The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the -th power of this matrix represents the transition of moves, and thus we can reduce the problem to a problem of matrix exponentiation.

    Algorithm

    First, there is a lot of symmetry on the board that we can exploit. Naively, there are possible states the knight can be in (assuming it is on the board). Because of symmetry through the horizontal, vertical, and diagonal axes, we can assume that the knight is in the top-left quadrant of the board, and that the column number is equal to or larger than the row number. For any square, the square that is found by reflecting about these axes to satisfy these conditions will be the canonical index of that square.

    This will reduce the number of states from to approximately , which makes the following (cubic) matrix exponentiation on this matrix approximately times faster.

    Now, if we know that every state becomes some linear combination of states after one move, then let's write a transition matrix of them, where the -th row of represents the linear combination of states that the -th state goes to. Then, represents a transition of moves, for which we want the sum of the -th row, where is the index of the starting square.

    Complexity Analysis

    • Time Complexity: where are defined as in the problem. There are approximately canonical states, which makes our matrix multiplication . To find the -th power of this matrix, we make matrix multiplications.

    • Space Complexity: . The matrix has approximately elements.

    Analysis written by: @awice

    Submit Solution