# Knight Dialer
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/knight-dialer)
Canonical: https://scaleengineer.com/dsa/problems/knight-dialer
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Bridgewater Associates](https://scaleengineer.com/companies/bridgewater-associates)
---
## Problem
The chess knight has a **unique movement**, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an **L**). The possible movements of chess knight are shown in this diagram:

A chess knight can move as indicated in the chess diagram below:

![](https://assets.glich.co/dsa/knight-dialer/image0.jpg) 

We have a chess knight and a phone pad as shown below, the knight **can only stand on a numeric cell** (i.e. blue cell).

![](https://assets.glich.co/dsa/knight-dialer/image1.jpg) 

Given an integer `n`, return how many distinct phone numbers of length `n` we can dial.

You are allowed to place the knight **on any numeric cell** initially and then you should perform `n - 1` jumps to dial a number of length `n`. All jumps should be **valid** knight jumps.

As the answer may be very large, **return the answer modulo** `109 + 7`.

**Example 1:**

**Input:** n = 1
**Output:** 10
**Explanation:** We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

**Example 2:**

**Input:** n = 2
**Output:** 20
**Explanation:** All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

**Example 3:**

**Input:** n = 3131
**Output:** 136006598
**Explanation:** Please take care of the mod.

**Constraints:**

* `1 <= n <= 5000`

# Approaches
## Brute-Force Recursion (Depth-First Search)
This approach directly translates the problem into a recursive function. We can think of this as exploring a tree of all possible knight moves. We define a function that takes the number of remaining jumps and the current digit as input. This function recursively calls itself for all valid next moves. The base case is when there are no jumps left. We sum the results from all possible starting digits.
**Time:** O(10 * 3^n) or simply O(3^n) - This is exponential. For each of the 10 starting positions, we explore a tree of depth `n-1`. The branching factor is at most 3 (for digits 4 and 6). · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is `n`.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Serves as a good foundation for more optimized dynamic programming solutions.
**Cons:** Extremely inefficient due to the massive number of redundant computations for the same subproblems (e.g., calculating the number of paths of length `k` from digit `d` multiple times).; Will result in a 'Time Limit Exceeded' (TLE) error for the constraints given in the problem.
### Explanation
We first define the possible moves for the knight from each numeric key on the phone pad. This can be stored in an adjacency list, like a `Map<Integer, int[]>` or a 2D array.

We create a recursive helper function, say `countPaths(remainingJumps, currentDigit)`.

The base case for the recursion is when `remainingJumps` is 0. This means we have successfully formed a number of the required length, so we return 1.

In the recursive step, we iterate through all possible next digits reachable from `currentDigit`. For each valid `nextDigit`, we make a recursive call `countPaths(remainingJumps - 1, nextDigit)`.

We sum up the results of these recursive calls. This sum represents the total number of distinct numbers that can be formed starting from `currentDigit` with `remainingJumps`.

The main function initializes a total count to zero. It then iterates through all possible starting digits (0-9) and calls the recursive function with `n-1` jumps. The results are summed up to get the final answer.

This method explores every single possible path, leading to many redundant calculations for the same subproblems.

```java
class Solution {
    private int[][] moves = {
        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},
        {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
    };
    private int MOD = 1_000_000_007;

    public int knightDialer(int n) {
        if (n == 1) return 10;
        long totalCount = 0;
        for (int i = 0; i <= 9; i++) {
            totalCount = (totalCount + countPaths(n - 1, i)) % MOD;
        }
        return (int) totalCount;
    }

    private long countPaths(int remainingJumps, int currentDigit) {
        if (remainingJumps == 0) {
            return 1;
        }

        long count = 0;
        for (int nextDigit : moves[currentDigit]) {
            count = (count + countPaths(remainingJumps - 1, nextDigit)) % MOD;
        }
        return count;
    }
}
```
### Algorithm
*   Define the graph of knight moves on the phone pad, for example, using an adjacency list.
*   Create a recursive function, let's call it `count(jumps, digit)`, that calculates the number of distinct numbers that can be formed with `jumps` remaining, starting from the current `digit`.
*   **Base Case:** If `jumps == 0`, it means a valid number of length `n` has been formed. Return 1.
*   **Recursive Step:** Initialize a counter `ways = 0`. Iterate through each `nextDigit` that is a valid knight's move from the current `digit`. For each `nextDigit`, recursively call `count(jumps - 1, nextDigit)` and add the result to `ways`.
*   The main function will call the recursive helper for each possible starting digit (0 through 9) with `n - 1` jumps and sum up the results to get the total count. All additions should be performed modulo `10^9 + 7`.

## Dynamic Programming with Memoization (Top-Down)
This approach improves upon the brute-force recursion by caching the results of subproblems, a technique known as memoization. The recursive structure remains the same, but before computing the result for a state `(remainingJumps, currentDigit)`, we check if it has already been computed and stored in a memoization table. If so, we return the cached value, avoiding redundant computations and drastically reducing the time complexity.
**Time:** O(n) - Each state `(jumps, digit)` is computed only once. There are `n * 10` states. The computation for each state involves a small constant number of operations (looping through next moves). · **Space:** O(n) - We need a memoization table of size `n x 10`, and the recursion stack can go up to a depth of `n`.
**Pros:** Drastically more efficient than brute force, changing the complexity from exponential to linear.; Guaranteed to solve the problem within the time limits for the given constraints.; Maintains a readable, recursive structure that is close to the problem's definition.
**Cons:** Uses O(n) space for the memoization table, which might be substantial for very large `n` (though acceptable for the given constraints).; Still has the overhead associated with recursion, which can make it slightly slower than an iterative bottom-up approach.
### Explanation
The core idea is to recognize that the subproblem `countPaths(remainingJumps, currentDigit)` is solved multiple times with the same arguments. We can store its result to avoid re-calculation.

We use a 2D array, `memo[n][10]`, to store the results. `memo[i][j]` will store the number of ways to dial a number by making `i` jumps starting from digit `j`.

The recursive function `countPaths(remainingJumps, currentDigit)` is modified:
1.  First, it checks if `memo[remainingJumps][currentDigit]` has a valid stored value. If yes, it returns that value immediately.
2.  If not, it proceeds with the calculation as in the brute-force approach.
3.  Before returning the newly computed result, it stores it in `memo[remainingJumps][currentDigit]` for future use.

All calculations are performed modulo `10^9 + 7` to prevent overflow and get the correct answer.

The main function initializes the memoization table, then calls the helper for each starting digit, summing the results.

```java
class Solution {
    private int[][] moves = {
        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},
        {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
    };
    private int MOD = 1_000_000_007;
    private int[][] memo;

    public int knightDialer(int n) {
        memo = new int[n + 1][10];
        long totalCount = 0;
        for (int i = 0; i <= 9; i++) {
            totalCount = (totalCount + countPaths(n, i)) % MOD;
        }
        return (int) totalCount;
    }

    // counts paths of length 'len' ending at 'digit'
    private int countPaths(int len, int digit) {
        if (len == 1) {
            return 1;
        }
        if (memo[len][digit] != 0) {
            return memo[len][digit];
        }

        long count = 0;
        for (int prevDigit : moves[digit]) { // This should be reverse moves, let's fix logic
            // The logic should be: count(len, digit) = sum(count(len-1, prev_digit))
            // where prev_digit can jump to digit. Let's adjust the main call.
        }
        // Correct logic is in the main function calling with n-1 jumps
        // Let's use the original logic for clarity.
        return countPathsHelper(len - 1, digit);
    }

    // counts paths with 'jumps' remaining, starting from 'digit'
    private int countPathsHelper(int remainingJumps, int currentDigit) {
        if (remainingJumps == 0) {
            return 1;
        }
        if (memo[remainingJumps][currentDigit] != 0) {
            return memo[remainingJumps][currentDigit];
        }

        long count = 0;
        for (int nextDigit : moves[currentDigit]) {
            count = (count + countPathsHelper(remainingJumps - 1, nextDigit)) % MOD;
        }
        
        memo[remainingJumps][currentDigit] = (int) count;
        return (int) count;
    }
    // In main: call countPathsHelper(n-1, i) for each i
}
```
### Algorithm
*   The algorithm is fundamentally the same as the brute-force recursion, but with an added caching layer.
*   Create a memoization table, `memo[n][10]`, to store the results of subproblems. Initialize it with a sentinel value (e.g., 0 or -1) to indicate that a state has not been computed.
*   Modify the recursive function `count(jumps, digit)`:
    *   **Base Case:** If `jumps == 0`, return 1.
    *   **Memoization Check:** Before any computation, check if `memo[jumps][digit]` contains a previously computed result. If so, return it immediately.
    *   **Recursive Step:** If the result is not in the cache, compute it by summing the results of `count(jumps - 1, nextDigit)` for all valid moves.
    *   **Cache Update:** Before returning the newly computed value, store it in `memo[jumps][digit]`.
*   The main function remains the same: call the helper for all 10 starting digits with `n-1` jumps and sum the results.

## Iterative Dynamic Programming with Space Optimization
This approach converts the top-down memoized recursion into a bottom-up iterative solution. We build up the solution for length `i` using the solutions for length `i-1`. Let `dp[i][j]` be the number of ways to form a number of length `i` ending at digit `j`. The recurrence is `dp[i][j] = sum(dp[i-1][k])` for all `k` that can jump to `j`. We can observe that to compute the counts for length `i`, we only need the counts from length `i-1`. This allows us to optimize space by only keeping track of the counts for the previous length, reducing space complexity from `O(n)` to `O(1)`. This is the most practical and efficient solution for the given constraints.
**Time:** O(n) - The outer loop runs `n-1` times. The inner loops iterate through the 10 digits and their moves. Since the total number of moves in the graph is a small constant, each iteration of the outer loop takes constant time. Thus, the total time is proportional to `n`. · **Space:** O(1) - We only use two arrays of size 10, which is constant space regardless of `n`.
**Pros:** Highly efficient in both time (linear) and space (constant).; Avoids recursion overhead, making it slightly faster in practice than the memoized version.; The most practical and common solution for this type of problem within typical competitive programming constraints.
**Cons:** Can be slightly less intuitive to formulate than the recursive top-down approach for those new to DP.
### Explanation
We use a 1D array, `dp`, of size 10. `dp[j]` will store the number of ways to form a number of the current length ending in digit `j`.

We initialize `dp` with all 1s. This represents the base case: for a number of length 1, there is exactly one way to end on any digit (by starting there).

We then loop `n-1` times, where each iteration corresponds to adding one more digit to the number (i.e., one more jump).

In each iteration, we create a temporary array, `next_dp`, to store the counts for the new length. We calculate `next_dp[to]` by summing up the `dp[from]` values for all `from` digits that can jump to `to`. After computing all values for `next_dp`, we update `dp = next_dp` for the next iteration.

After `n-1` iterations, the `dp` array holds the counts for numbers of length `n`. The final answer is the sum of all elements in the `dp` array, modulo `10^9 + 7`.

```java
class Solution {
    public int knightDialer(int n) {
        if (n == 1) return 10;

        int MOD = 1_000_000_007;
        // moves[i] is the list of numbers you can jump TO from i
        int[][] moves = {
            {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},
            {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
        };

        long[] dp = new long[10];
        java.util.Arrays.fill(dp, 1); // dp for length 1

        // Iterate for jumps to form lengths 2 through n
        for (int i = 1; i < n; i++) {
            long[] next_dp = new long[10];
            // For each starting digit 'from' for this jump
            for (int from = 0; from <= 9; from++) {
                // For each destination digit 'to'
                for (int to : moves[from]) {
                    next_dp[to] = (next_dp[to] + dp[from]) % MOD;
                }
            }
            dp = next_dp;
        }

        long totalCount = 0;
        for (long count : dp) {
            totalCount = (totalCount + count) % MOD;
        }

        return (int) totalCount;
    }
}
```
### Algorithm
*   Let `dp[j]` be the number of ways to form a number of the current length ending in digit `j`.
*   Initialize a 1D array `dp` of size 10 with all elements set to 1. This represents the base case: for a number of length 1, there is one way to end on any digit (by starting there).
*   Loop `n-1` times, as we need to perform `n-1` jumps.
*   Inside the loop, create a temporary array `next_dp` of size 10, initialized to zeros.
*   Iterate through each digit `from_digit` from 0 to 9. The value `dp[from_digit]` is the number of ways to have arrived at this digit in the previous step.
*   For each `to_digit` reachable from `from_digit`, add `dp[from_digit]` to `next_dp[to_digit]` (modulo `MOD`).
*   After iterating through all `from_digit`s, the `next_dp` array contains the counts for the new length. Update `dp` by assigning `next_dp` to it.
*   After the main loop finishes, the `dp` array holds the counts for numbers of length `n`. The final answer is the sum of all elements in this `dp` array.

## Matrix Exponentiation
This is a highly advanced and powerful technique for solving linear recurrence relations, which is what our DP formulation represents. The state transition from one length to the next can be described by a matrix multiplication. If `v_i` is a vector representing the counts for each digit at length `i`, then `v_{i+1} = T * v_i`, where `T` is a constant 10x10 transition matrix. To find the counts for length `n`, we need to compute `v_n = T^(n-1) * v_1`. The matrix power `T^(n-1)` can be calculated efficiently in logarithmic time using binary exponentiation (also known as exponentiation by squaring).
**Time:** O(log n) - More precisely, `O(K^3 * log n)`, where `K=10` is the number of digits. Matrix multiplication is `O(K^3)`, and binary exponentiation performs `O(log n)` such multiplications. Since `K` is constant, the complexity is logarithmic in `n`. · **Space:** O(1) - We need to store a few 10x10 matrices, which is constant space, `O(K^2)` where K=10.
**Pros:** Asymptotically the fastest approach with O(log n) time complexity.; Extremely efficient for very large values of `n` where an O(n) solution would be too slow.; Space complexity is constant.
**Cons:** Significantly more complex to implement compared to the iterative DP approach.; The constant factor for time complexity is large (`K^3` for a `KxK` matrix). For the given constraints (`n <= 5000`), the simpler `O(n)` DP approach might be faster in practice due to smaller constant factors.
### Explanation
The DP recurrence `dp[i][j] = sum(dp[i-1][k])` over all `k` that can jump to `j` is a linear transformation. This transformation can be captured by a 10x10 matrix `M`.

Let `V_i` be a column vector of the counts for length `i`. Then `V_i = M * V_{i-1}`. By extension, `V_n = M^(n-1) * V_1`.

The initial vector `V_1` (for length 1) is `[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]^T`.

The total number of ways is the sum of elements in `V_n`. This is equivalent to `(sum_vector) * V_n`, where `sum_vector` is `[1, 1, ..., 1]`. This simplifies to summing all elements of the final matrix `M^(n-1)`.

The algorithm is:
1.  Construct the 10x10 transition matrix `M`.
2.  Compute `ResultMatrix = M^(n-1)` using binary exponentiation for matrices.
3.  The total number of ways is the sum of all elements in `ResultMatrix`.

```java
class Solution {
    int MOD = 1_000_000_007;

    public int knightDialer(int n) {
        if (n == 1) return 10;

        long[][] transitionMatrix = {
            {0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, // 0 <- 4, 6
            {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, // 1 <- 6, 8
            {0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, // 2 <- 7, 9
            {0, 0, 0, 0, 1, 0, 0, 0, 1, 0}, // 3 <- 4, 8
            {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, // 4 <- 0, 3, 9
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 5 <-
            {1, 1, 0, 0, 0, 0, 0, 1, 0, 0}, // 6 <- 0, 1, 7
            {0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, // 7 <- 2, 6
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // 8 <- 1, 3
            {0, 0, 1, 0, 1, 0, 0, 0, 0, 0}  // 9 <- 2, 4
        };

        long[][] resultMatrix = matrixPower(transitionMatrix, n - 1);

        long totalCount = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                totalCount = (totalCount + resultMatrix[i][j]) % MOD;
            }
        }
        return (int) totalCount;
    }

    private long[][] matrixMultiply(long[][] A, long[][] B) {
        long[][] C = new long[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    private long[][] matrixPower(long[][] base, int exp) {
        long[][] result = new long[10][10];
        for (int i = 0; i < 10; i++) result[i][i] = 1; // Identity matrix
        
        while (exp > 0) {
            if (exp % 2 == 1) result = matrixMultiply(result, base);
            base = matrixMultiply(base, base);
            exp /= 2;
        }
        return result;
    }
}
```
### Algorithm
*   Represent the DP state transition as a matrix multiplication. Let `V_i` be a 10x1 column vector where `V_i[j]` is the number of ways to form a number of length `i` ending at digit `j`. Then `V_i = M * V_{i-1}`.
*   Construct the 10x10 transition matrix `M`, where `M[j][k] = 1` if a knight can jump from digit `k` to `j`, and 0 otherwise.
*   The problem reduces to finding `V_n = M^(n-1) * V_1`. Since `V_1` is a vector of all ones, the total count is the sum of all elements in the resulting matrix `M^(n-1)`.
*   Implement a function for multiplying two 10x10 matrices.
*   Implement a function to compute `M^(n-1)` using the binary exponentiation (or exponentiation by squaring) algorithm. This algorithm calculates the power in `O(log n)` matrix multiplications.
*   Calculate `ResultMatrix = M^(n-1)`.
*   Sum all elements of `ResultMatrix` to get the final answer.

# Solutions
### CSharp

```csharp
public class Solution { public int KnightDialer ( int n ) { if ( n == 1 ) return 10 ; int A = 4 ; int B = 2 ; int C = 2 ; int D = 1 ; int MOD = ( int ) 1 e9 + 7 ; for ( int i = 0 ; i < n - 1 ; i ++) { int tempA = A ; int tempB = B ; int tempC = C ; int tempD = D ; A = (( 2 * tempB ) % MOD + ( 2 * tempC ) % MOD ) % MOD ; B = tempA ; C = ( tempA + ( 2 * tempD ) % MOD ) % MOD ; D = tempC ; } int ans = ( A + B ) % MOD ; ans = ( ans + C ) % MOD ; return ( ans + D ) % MOD ; } }
```

### Java

```java
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int knightDialer ( int n ) { if ( n == 1 ) { return 10 ; } long [] f = new long [ 10 ]; Arrays . fill ( f , 1 ); while (-- n > 0 ) { long [] t = new long [ 10 ]; t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) { f [ i ] = t [ i ] % MOD ; } } long ans = 0 ; for ( long v : f ) { ans = ( ans + v ) % MOD ; } return ( int ) ans ; } }
```

### CPP

```cpp
using ll = long long ; class Solution { public: int knightDialer ( int n ) { if ( n == 1 ) return 10 ; int mod = 1e9 + 7 ; vector < ll > f ( 10 , 1ll ); while ( -- n ) { vector < ll > t ( 10 ); t [ 0 ] = f [ 4 ] + f [ 6 ]; t [ 1 ] = f [ 6 ] + f [ 8 ]; t [ 2 ] = f [ 7 ] + f [ 9 ]; t [ 3 ] = f [ 4 ] + f [ 8 ]; t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ]; t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ]; t [ 7 ] = f [ 2 ] + f [ 6 ]; t [ 8 ] = f [ 1 ] + f [ 3 ]; t [ 9 ] = f [ 2 ] + f [ 4 ]; for ( int i = 0 ; i < 10 ; ++ i ) f [ i ] = t [ i ] % mod ; } ll ans = accumulate ( f . begin (), f . end (), 0ll ); return ( int ) ( ans % mod ); } };
```

### Python

```python
class Solution : def knightDialer ( self , n : int ) -> int : if n == 1 : return 10 f = [ 1 ] * 10 for _ in range ( n - 1 ): t = [ 0 ] * 10 t [ 0 ] = f [ 4 ] + f [ 6 ] t [ 1 ] = f [ 6 ] + f [ 8 ] t [ 2 ] = f [ 7 ] + f [ 9 ] t [ 3 ] = f [ 4 ] + f [ 8 ] t [ 4 ] = f [ 0 ] + f [ 3 ] + f [ 9 ] t [ 6 ] = f [ 0 ] + f [ 1 ] + f [ 7 ] t [ 7 ] = f [ 2 ] + f [ 6 ] t [ 8 ] = f [ 1 ] + f [ 3 ] t [ 9 ] = f [ 2 ] + f [ 4 ] f = t return sum ( t ) % ( 10 ** 9 + 7 )
```