> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Knight Dialer Python Solution with Tests

> Tested Python solution for LeetCode 935 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 935, [Medium](/catalog/medium). Topics: [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/knight-dialer/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 935   # by problem number
lcpy gen -s knight_dialer   # by problem name
```

## Problem

\<p>The chess knight has a \<strong>unique movement\</strong> ,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 \<strong>L\</strong>). The possible movements of chess knight are shown in this diagram:\</p>

\<p>A chess knight can move as indicated in the chess diagram below:\</p>

\<p>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).\</p>

\<p>\<img alt="" src="[https://assets.leetcode.com/uploads/2020/08/18/chess.jpg](https://assets.leetcode.com/uploads/2020/08/18/chess.jpg)" style="width: 402px; height: 402px;" />\</p>

\<p>\<img alt="" src="[https://assets.leetcode.com/uploads/2020/08/18/phone.jpg](https://assets.leetcode.com/uploads/2020/08/18/phone.jpg)" style="width: 282px; height: 302px;" />\</p>

\<p>Given an integer \<code>n\</code>, return how many distinct phone numbers of length \<code>n\</code> we can dial.\</p>

\<p>You are allowed to place the knight on any numeric cell initially and then you should perform \<code>n - 1\</code> jumps to dial a number of length \<code>n\</code>. All jumps should be valid knight jumps.\</p>

\<p>As the answer may be very large, return the answer modulo \<code>10\<sup>9\</sup> + 7\</code>.\</p>

### Examples

```
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.
```

```
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]
```

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

### Constraints

* 1 \<= n \<= 5000

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/knight_dialer/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/knight_dialer/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n * 10)
    # Space: O(1)
    def knight_dialer(self, n: int) -> int:
        mod = 1_000_000_007
        moves: dict[int, tuple[int, ...]] = {
            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[digit] = number of distinct numbers of current length ending here
        dp = [1] * 10
        for _ in range(n - 1):
            new_dp = [0] * 10
            for digit in range(10):
                for nxt in moves[digit]:
                    new_dp[nxt] = (new_dp[nxt] + dp[digit]) % mod
            dp = new_dp
        return sum(dp) % mod
```

## Complexity

| Time | Space |
| - | - |
| O(n \* 10) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.