Problem Description

In this problem, you are given an n x n chessboard and a knight piece located at a starting cell (row, column). You're asked to calculate the probability that after making exactly k moves, the knight remains within the borders of the chessboard, assuming it moves randomly across its legitimate move set.

A knight in chess moves in an L-shape: two squares in a cardinal direction (north, south, east, or west) followed by one square in an orthogonal direction (90-degree turn from the cardinal direction), or vice versa. The challenge here is that at each move, the knight could potentially step off the board, and the task is to compute how likely the knight is to still be on the board after it has made all k moves.

The moves the knight makes are direction-agnostic, meaning it doesn't favor any direction and choses its move uniformly at random from the eight possible options at each step, unless the move would take it off the board, in which case the move isn't made.

Intuition

To tackle this problem, we use a technique called Dynamic Programming (DP), which is frequently used to solve problems where you're asked to figure out several outcomes related to different scenarios — in this case, the probability of the knight being on different cells after different numbers of moves.

The key insight in applying Dynamic Programming is the idea that the solution to our problem can be composed of solutions to subproblems. With this problem, we notice that the probability of the knight being on a certain cell after h moves depends only on the probabilities of it being on the adjacent cells that can reach the current cell in one move, after h-1 moves.

Thus, we can build out a three-dimensional table f, where f[h][i][j] represents the probability of the knight being on cell (i, j) after h moves. Initially, when h=0, the knight hasn't made any moves so it's certainly on its starting cell, hence probabilities across the board are set to 1.

For subsequent moves (h > 0), we calculate the probability for each cell based on probabilities of the previous step, averaging over all the knight moves since each move is equally likely. If a move would go off the board, it doesn't contribute to the probabilities because it's an invalid move. This is repeated until we reach h = k, at which point f[k][row][column] will give us the desired probability.

The intuition behind this approach comes from breaking down the chaotic process of the knight hopping around into manageable pieces where each state (board configuration after a certain number of moves) is the result of smaller, easier-to-calculate probabilities (board configuration after one fewer move).

Learn more about Dynamic Programming patterns.

Solution Approach

The solution employs a Dynamic Programming (DP) algorithm to iteratively compute the probabilities of the knight being on different cells of the chessboard after a certain number of moves. The main data structure used in this solution is a three-dimensional array f, where f[h][i][j] holds the probability of the knight landing on cell (i, j) after making h moves.

Let's break down the steps of the algorithm based on the Reference Solution Approach provided:

1. Initialization:

   • We initialize a three-dimensional list f with dimensions (k + 1) x n x n with zeros.
   • For every cell (i, j) on the chessboard, we set f[0][i][j] = 1 because before making any move, the probability that the knight is on any cell it starts from is 100%.

2. DP Transition:

   • We iterate through each possible number of moves h from 1 to k.
   • For each number of moves h, we iterate over all cells (i, j) of the chessboard looking to fill f[h][i][j] with the updated probabilities.
   • For each cell (i, j), we iterate over all the possible moves the knight could make from this cell. This results in potentially 8 adjacent cells (a, b) from where the knight could have come.
   • For each potential move, we check if the target cell (a, b) is within the boundaries of the chessboard.
   • If the move is valid (the cell is on the board), we update f[h][i][j] by adding to it the probability f[h - 1][a][b] / 8. The division by 8 accounts for the knight's uniform probability of choosing any of its 8 moves.

3. Result:

   • Once we have processed k moves, our DP table contains the probabilities of the knight being on each cell for every number of moves up to k.
   • We retrieve f[k][row][column], which is the probability of the knight being on its starting cell (row, column) after making k moves.

The efficiency of this approach comes from the fact that each subproblem (computing f[h][i][j]) is solved once and reused to solve other subproblems that depend on it, following the principle of optimal substructure in dynamic programming. This reduces the number of computations from exponentially many naive simulations to a polynomial amount related to the size of the DP table (k x n x n).

Example Walkthrough

Let's illustrate the solution approach using an example. Consider a 3x3 chessboard and a knight starting at the cell (1,1) (with both dimensions 0-indexed), and we want to compute the probability of the knight being on the chessboard after exactly 2 moves.

1. Initialization:

   • We create a three-dimensional list f of size (3 = k + 1) x 3 x 3 and initialize all values to zero.
   • We set f[0][1][1] = 1 because initially, the knight is at (1,1) with a probability of 100%.

2. First Move Calculations (h = 1):

   • We look to calculate the probabilities for h = 1 for all cells.
   • Starting from (1,1), the knight can move to (0,2), (2,2), (2,0), and (0,0), assuming we're considering a 3x3 board where these are still within bounds. Let's account for each valid move from (1,1):
     • For the move to (0,2), we update f[1][0][2] = f[0][1][1] / 8 = 1/8 because from step 0 to step 1, the knight has a 1/8 chance of making this move (1 out of 8 possible moves).
     • Repeat for the other three valid moves.
   • At the end of this step, the DP list f at h=1 would show 1/8 at the positions (0,2), (2,2), (2,0), and (0,0), and 0 elsewhere.

3. Second Move Calculations (h = 2):

   • Now we calculate the probabilities for h = 2.
   • For each of the cells that the knight could have moved to in the first move, we consider all possible moves the knight could take from there.
   • Take the cell (0,2):
     • From (0,2), the knight could move to (2,1) and (1,0). We update f[2][2][1] += f[1][0][2] / 8 = 1/8 / 8 = 1/64 and similarly for (1,0).
     • Notice how this time, several moves could contribute to the probability of ending up on the same cell, so we sum up the probabilities from all potential previous positions.
   • We perform this for all cells that were reachable from (1,1) in the first step, updating their reachable cells' probabilities.

4. Result:

   • Having completed calculations for h = 2 moves, our DP table f now contains the probabilities of the knight being on each cell after 2 moves.
   • We look at f[2][1][1] to find the final probability of the knight being on its starting cell after the second move. In this case, our simplified example may result in f[2][1][1] = 0 as the knight cannot return to (1,1) in exactly 2 moves on a 3x3 board.

The result of the DP table would likely show non-zero probabilities around the edges or center of the 3x3 board, depending on the initial position and the number of moves. This example with k=2 is small-scale; in a real scenario with a large n x n board and a higher number of moves, the probabilities would be spread out more and would require careful computation for each step to accumulate the probabilities correctly.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(k * n^2). This is because there are k + 1 layers, each having an n x n grid representing the chessboard. Each cell in the grid is visited once for each of the k steps. For each cell, we consider all 8 possible moves of a knight, but this constant factor does not affect the overall time complexity.

The space complexity of the code is O(k * n^2) as well. This is due to the three-dimensional list f that is used to store the probabilities. The size of this list is determined by the number of steps k + 1 and the size of the chessboard n x n.

Learn more about how to find time and space complexity quickly using problem constraints.