Knight Dialer

Knight Dialer Problem

The Knight Dialer problem models a chess knight moving on a standard 3x3 phone keypad (digits 0-9, excluding * and #), where the knight follows its classic L-shaped moves (2 steps in one direction, 1 perpendicular). Given integer n (number length), calculate distinct n-digit sequences formable by knight jumps, starting from any digit, modulo 10^9 + 7. Digit 5 is isolated—no valid outgoing moves exist from it.[1][3][9]

Keypad Layout and Moves

Standard keypad:

1 2 3 4 5 6 7 8 9 0

Valid moves from each digit:[3][1]

| Digit | Possible Moves | |-------|----------------| | 0 | 4, 6 | | 1 | 6, 8 | | 2 | 7, 9 | | 3 | 4, 8 | | 4 | 0, 3, 9 | | 5 | (none) | | 6 | 0, 1, 7 | | 7 | 2, 6 | | 8 | 1, 3 | | 9 | 2, 4 |[3]

Input/Output Examples

• Input: n = 1 → Output: 10
  (Single digits: 0-9 all valid, including 5).[1][3]

• Input: n = 2 → Output: 20
  (Sums ways from each start: e.g., from 1 → 6,8; total pairs like 16,18).[3]

• Input: n = 3 → Output: 46
  (Example paths: 160, 340, 729, 043).[3]

• Input: n = 3131 → Output: 136006612
  (Large n requires efficient DP).[9]

Constraints

• 1 ≤ n ≤ 5000
  (n=5000 demands O(n) space/time optimization via DP/memoization on states (position, steps)).[5][9]

This LeetCode #935 problem matches Citadel interviews for DP/DFS/memo/graph skills, modeling as graph where nodes=digits, edges=knight moves.[9][1][3]