Knight Probability in Chessboard - Complete Solution Guide

Knight Probability in Chessboard is LeetCode problem 688, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed , so the top-left cell is (0, 0) , and the bottom-right cell is (n - 1, n - 1) . A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell 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 woul

Detailed Explanation

The problem describes a knight moving on an n x n chessboard. The knight starts at a given cell (row, column) and makes exactly k moves. At each move, the knight chooses one of eight possible moves uniformly at random. The goal is to calculate the probability that the knight remains on the board after k moves. The chessboard is 0-indexed.

Solution Approach

The solution uses dynamic programming to calculate the probability of the knight being at each cell after each move. A 2D array `dp` stores the probabilities. The algorithm iterates `k` times, each time updating the `dp` array based on the possible knight moves from the previous `dp` array. Specifically, for each cell (r, c) in the current `dp` array, and for each of the 8 possible moves, it checks if the resulting new cell (nr, nc) is within the board. If it is, it adds `dp[r][c] / 8.0` to `next_dp[nr][nc]`. After iterating through all cells and moves for a given number of steps, the `dp` array is updated with the `next_dp` array. Finally, the algorithm sums the probabilities in the final `dp` array to get the total probability of the knight staying on the board.

Step-by-Step Algorithm

1. Step 1: Initialize a 2D array `dp` of size n x n with all values set to 0.0. Set `dp[row][column]` to 1.0, representing the initial probability of the knight being at the starting cell.
2. Step 2: Define the 8 possible knight moves as (dr, dc) pairs.
3. Step 3: Iterate `k` times (for each move):
4. Step 4: Inside the loop, create a new 2D array `next_dp` of size n x n and initialize it with 0.0.
5. Step 5: Iterate through each cell (r, c) of the current `dp` array:
6. Step 6: If `dp[r][c]` is greater than 0 (meaning the knight could be at this cell with some probability), iterate through the 8 possible knight moves.
7. Step 7: For each move (dr, dc), calculate the new row and column indices (nr, nc) as `r + dr` and `c + dc` respectively.
8. Step 8: Check if (nr, nc) is within the bounds of the board (0 <= nr < n and 0 <= nc < n).
9. Step 9: If (nr, nc) is within bounds, update `next_dp[nr][nc]` by adding `dp[r][c] / 8.0`.
10. Step 10: After iterating through all cells (r, c) and moves, update `dp` with `next_dp`.
11. Step 11: After completing the `k` iterations, calculate the sum of all values in the final `dp` array. This sum represents the total probability of the knight staying on the board.
12. Step 12: Return the calculated total probability.

Key Insights

• Insight 1: Dynamic programming is suitable because the probability of being at a cell after i moves depends only on the probabilities of being at neighboring cells after i-1 moves.
• Insight 2: We can use a 2D array to store the probabilities of the knight being at each cell after each move.
• Insight 3: The probability update for each cell is the sum of the probabilities from its 8 possible knight moves, each divided by 8 (because each move is equally likely).

Complexity Analysis

Time Complexity: O(k*n*n)

Space Complexity: O(n*n)

Topics

This problem involves: Dynamic Programming.

Companies

Asked at: Citadel.