Knight Dialer: Dynamic Programming on a Keypad

A chess knight is placed on a phone dial pad. It can make n - 1 hops, and each hop follows standard chess knight moves (two squares in one direction, one square perpendicular). Given an integer n, return how many distinct phone numbers of length n the knight can dial, starting from any numeric key. Since the answer can be huge, return it modulo 10^9 + 7.

This is LeetCode 935: Knight Dialer, and it is a great example of modeling a problem as a graph and then solving it with dynamic programming. The phone pad is small and fixed, which means the entire DP fits in a constant-size table.

The phone pad as a graph

The keypad layout is:

1 2 3
4 5 6
7 8 9
* 0 #

A chess knight placed on any numeric key can jump to a specific set of other keys. The keys * and # are off limits. If you map out every valid knight move, you get this adjacency list:

moves = {
    0: [4, 6],
    1: [6, 8],
    2: [7, 9],
    3: [4, 8],
    4: [0, 3, 9],
    5: [],
    6: [0, 1, 7],
    7: [2, 6],
    8: [1, 3],
    9: [2, 4],
}

Notice that digit 5 has no outgoing knight moves. A knight on the center key is stuck. Also notice that digits 4 and 6 each have three neighbors while all other digits have two (or zero). This asymmetry is what makes the counts interesting.

Setting up the DP

Once you have the adjacency list, the problem becomes a classic state machine DP.

Define dp[d] as the number of distinct phone numbers that end on digit d at the current length. For length 1, every digit is a valid starting point, so dp[d] = 1 for all digits 0 through 9.

To go from length i to length i + 1, you propagate counts along knight moves. If a knight is on digit d, it can jump to any neighbor of d. So each neighbor receives the current count of d.

The transition is:

new_dp[neighbor] += dp[digit]   (for each neighbor of digit)

After n - 1 rounds of transitions, the answer is the sum of all dp[d] values.

This is the same structure as computing reachability counts in a graph, except you do it for a fixed number of steps. The adjacency list has only 10 entries with at most 3 neighbors each, so every transition step does constant work.

The solution

def knightDialer(n):
    MOD = 10 ** 9 + 7
    moves = {
        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8],
        4: [0, 3, 9], 5: [], 6: [0, 1, 7],
        7: [2, 6], 8: [1, 3], 9: [2, 4],
    }
    dp = [1] * 10
    for _ in range(n - 1):
        new_dp = [0] * 10
        for digit in range(10):
            for neighbor in moves[digit]:
                new_dp[neighbor] = (new_dp[neighbor] + dp[digit]) % MOD
        dp = new_dp
    return sum(dp) % MOD

Let's walk through how the counts evolve for n = 3:

Why this works

The key insight is that the adjacency list is fixed and tiny. There are only 10 digits, and each has at most 3 neighbors. That means every transition from one length to the next does at most 10 * 3 = 30 additions. No matter how large n gets, each step takes the same constant amount of work.

You are essentially running a breadth-first-style count propagation on a 10-node graph, repeated n - 1 times. The graph structure never changes, so there is nothing to recompute or memoize beyond the DP table itself.

Complexity analysis

Time: O(n). You run n - 1 transition steps. Each step iterates over 10 digits and at most 3 neighbors per digit, which is O(1) per step. Total: O(n).

Space: O(1). The DP table always has exactly 10 entries. You use two arrays of size 10 (current and next), which is constant regardless of n.

This is about as efficient as it gets. There are matrix exponentiation approaches that achieve O(log n) time by raising the 10x10 adjacency matrix to the (n-1)th power, but for interview purposes the linear solution is clean and easy to explain.

Edge cases to watch for

• n = 1: Every digit is a valid one-digit number. Return 10.
• Digit 5: It has no outgoing moves. For n = 1 it contributes 1. For any n > 1, the count at digit 5 drops to 0 and stays there.
• Large n: The modular arithmetic % (10^9 + 7) must be applied at every addition, not just at the end. Failing to do so causes integer overflow in languages with fixed-size integers (though Python handles big integers natively).
• The * and # keys: These are never valid. The adjacency list simply does not include them. If you model the problem correctly from the start, they never enter the picture.

The building blocks

This problem is built on state machine DP on a fixed graph. You have a small set of states (the 10 digits), a fixed transition function (the knight move adjacency list), and you want to count the number of paths of length n through the graph.

The structure:

• State: which digit the knight is currently on
• Transition: for each digit, distribute its count to all of its knight-move neighbors
• Answer: sum of all states after n - 1 transitions

This same building block shows up in:

• Knight Probability in Chessboard (LeetCode 688): same knight-move DP, but on a grid with probabilities instead of counts
• Domino and Tromino Tiling (LeetCode 790): fixed transition between a small number of states, iterated for n columns
• Paint House type problems: fixed set of choices at each step with transition constraints between adjacent steps

Once you recognize the "small fixed graph, count paths of length n" pattern, these problems all reduce to the same loop: initialize, transition, sum.

From understanding to recall

You have just read through the full solution, and the state machine DP pattern probably clicks right now. But can you write the adjacency list from scratch next week? Can you remember whether digit 5 has zero neighbors or two? Will you set up the transition in the right direction (propagating from dp[digit] to new_dp[neighbor], not the other way around)?

Spaced repetition makes these details stick. You revisit the knight dialer adjacency list and the transition loop at increasing intervals, writing them from memory each time. After a few reps, the pattern becomes automatic. No more second-guessing which digits the knight can reach from 4 (it is 0, 3, and 9).

The state machine DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - The simplest DP problem, same "count paths" idea with a trivial transition
• Knight Probability in Chessboard - Same knight-move DP pattern on a grid, computing probabilities instead of counts
• Decode Ways - Linear DP with conditional transitions, another great drill for the DP pipeline