Problem 688

Abstract / Summary

A knight starts at a given square on a chessboard and moves randomly; find the chance it stays on the board after a certain number of moves.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0688.py

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        board = []
        for _ in range(n):
            board.append([0] * n)

        # initial position
        board[row][column] = 1

        # helper function
        def add(b, x, y, what):
            if 0 <= x < n and 0 <= y < n:
                b[y][x] += what

        for _ in range(k):
            next = []
            for _ in range(n):
                next.append([0] * n)

            for y in range(n):
                for x in range(n):
                    have = board[y][x]
                    add(next, x - 2, y - 1, have)
                    add(next, x + 2, y - 1, have)
                    add(next, x - 2, y + 1, have)
                    add(next, x + 2, y + 1, have)
                    add(next, x - 1, y - 2, have)
                    add(next, x + 1, y - 2, have)
                    add(next, x - 1, y + 2, have)
                    add(next, x + 1, y + 2, have)
            board = next

        total = sum(sum(r) for r in board)
        return total / 8 ** k
34 lines | 1126 bytes | submitted December 29, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 57% (300k+ submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the probability that a knight, placed on an n × n chessboard at a given starting cell, remains on the board after making exactly k moves. It models the process as a discrete dynamic programming problem where each cell stores the number of ways the knight can arrive there after a certain number of moves. The final probability is obtained by normalizing the total count of surviving paths by the total number of possible move sequences, which is 8^k because a knight has up to eight legal moves at each step.

Board Initialization

The algorithm begins by constructing a two-dimensional list named board that represents the current distribution of the knight’s presence. Each row is created by appending a list of zeros of length n. The starting cell is then set to 1, indicating a single way to be at that position before any moves are taken.

board = []
for _ in range(n):
    board.append([0] * n)

board[row][column] = 1

This explicit construction ensures that the board is a mutable grid of integers, ready for in-place updates during the simulation.

Helper Function for Safe Updates

A nested function add is defined to encapsulate the boundary check and the accumulation of ways into a target board. By checking that both coordinates lie within [0, n) before performing the addition, the function automatically discards moves that would land the knight off the board. This eliminates the need for separate conditional logic scattered throughout the main loop.

def add(b, x, y, what):
    if 0 <= x < n and 0 <= y < n:
        b[y][x] += what

The use of a local function reduces attribute lookups and keeps the inner loop concise.

Iterative Transition Over Moves

The core of the algorithm iterates k times, each iteration representing one knight move. For each step a fresh board called next is allocated, mirroring the dimensions of the original board and filled with zeros. This board will accumulate the number of ways to reach each cell after the current move.

for _ in range(k):
    next = []
    for _ in range(n):
        next.append([0] * n)

The double nested loops over y and x traverse every cell of the current board. The variable have stores the number of ways the knight can be at the current cell before the move. The eight possible knight jumps are then applied by invoking add with the appropriate coordinate offsets. Because add silently ignores out-of-bounds coordinates, only legal destinations receive the accumulated count.

for y in range(n):
    for x in range(n):
        have = board[y][x]
        add(next, x - 2, y - 1, have)
        add(next, x + 2, y - 1, have)
        add(next, x - 2, y + 1, have)
        add(next, x + 2, y + 1, have)
        add(next, x - 1, y - 2, have)
        add(next, x + 1, y - 2, have)
        add(next, x - 1, y + 2, have)
        add(next, x + 1, y + 2, have)

After processing all cells, the reference board is updated to point to next, preparing for the next iteration. This swapping avoids the need to copy data between structures.

board = next

Final Probability Computation

When all k moves have been simulated, the algorithm aggregates the total number of surviving paths by summing every entry in the final board. The result is divided by 8 ** k, the total number of possible move sequences without regard to board boundaries, yielding the desired probability.

total = sum(sum(r) for r in board)
return total / 8 ** k

Edge Cases Handled

The implementation gracefully handles several boundary conditions:

  • When k is zero, the outer loop does not execute, leaving the board unchanged with a single 1 at the starting cell. The final sum equals 1, and the division by 8 ** 0 (which is 1) returns a probability of 1.0, correctly reflecting that the knight has not moved.
  • For a board size of 1, any move would necessarily leave the board. The add function prevents any accumulation outside the single cell, resulting in a total of 0 after the first iteration and a probability of 0.0 for any k > 0.
  • Starting positions on the edge or corner of the board are accommodated because each potential jump is individually validated by add. Moves that would fall off the board are ignored, while legal moves contribute to the next state.
  • The code tolerates large values of k without overflow concerns in Python, as integers have arbitrary precision and the division is performed using floating-point arithmetic only at the final step.

Performance Optimizations Observed

Several design choices contribute to efficient execution:

  • Pre-allocation of the board and next grids avoids repeated resizing or dynamic list growth during the simulation.
  • The helper add function centralizes the boundary check, reducing duplicated conditional statements and keeping the inner loop tight.
  • By storing the count of ways as integers and only converting to a floating-point value at the end, the algorithm minimizes the overhead associated with floating-point arithmetic during the iterative process.
  • The use of local variables (have, next, board) within the loops leverages Python’s fast local name resolution, which is faster than accessing attributes or globals.
  • The algorithm reuses the same variable name next for each iteration, allowing the previous board to be garbage-collected promptly, which helps keep memory usage bounded by two n × n grids regardless of k.
written by openai gpt

ELI5 - Simplified Explanation

Imagine a big square game board filled with grass. There is a little horse piece called a knight standing on one of the squares. This code helps figure out where the horse might jump if it keeps hopping around for a while.

First, the computer creates the board and places the horse on its starting square. It shows this by putting a number one there to remember exactly where the horse begins.

Then, there is a special instruction called a helper function. This is like a game rule that checks if a jump lands inside the board or if it accidentally goes off the edge into the clouds. It makes sure the horse stays on the game board where it belongs.

Next, the computer starts a loop to help the horse make several jumps one after another. Since a horse can move in eight different ways shaped like an L, the code looks at every square on the board to see if the horse is there. For every place the horse could be, it calculates all the new squares where it can land next.

After it calculates all the possible places the horse can jump, it creates a brand new board for the next turn and clears the old one. It keeps repeating this move-calculation process until all the jumps allowed are finished.

At the very end, the computer adds up all the pieces left on the board to see how many paths the horse took, and it shares the final information about those jumps.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.44 | σ = 1.20

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Rust Python Go TS
LeetcodeHelp C++ Java Python
MemoryLimitExceeded C++ Python
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
everthis JS
fengvyi C++
gouthampradhan Java
JoshCrozier JS
lkwq007 Python
MacJim C++
ruoru Rust
suxrobGM C#
varunu28 Java
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fengvyi C++
gouthampradhan Java
JoshCrozier JavaScript
lkwq007 Python
MacJim C++
ruoru Rust
suxrobGM C#
varunu28 Java
zfang399 C++
33 links | 18 authors | 8 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

5 solutions   December 29, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality