Knight Dialer - Leetcode Solution

Problem Statement:

The Knight's Tour is a chess problem in which the knight moves through all the squares of the board exactly once. Now, you are given a 10^9 phone dialer in the form of an array of integers, where each integer represents a digit from 0-9. The knight is initially placed on the digit at index 0 of the dialer. The knight moves to the neighboring digit with a L shape move, as it does in a chessboard. Each move, the knight can move to any of the 8 different positions on the keypad. You must find out the number of distinct numbers that can be made after n hops of the knight on the dialer.

Solution:

To solve this problem, we need to find all the possible sequences that can be generated by the knight starting at the digit at index 0 of the dialer and moving for n hops. We can achieve this through depth-first search (DFS). Our DFS function takes the current index of the dialer, the current length of the sequence, and the maximum length (n) as its parameters.

Algorithm:

1. Define a counter variable to keep track of the number of distinct numbers found.
2. Define the DFS function taking three arguments: idx represents the current index of the dialer, length represents the current length of the sequence, and maxlen represents the maximum allowed length.
3. If the length of the sequence is equal to the maximum allowed length, that means we have found a valid sequence. So increment the counter by 1.
4. For each reachable digit from the current index, if the length of the sequence is less than the maximum allowed length, then make a recursive call to the DFS function with the new index and increased length.
5. Return the counter at the end of the function

Consider the below implementation:

def knightDialer(n):
    moves = [[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3], [2, 4]]
    mod = 10 ** 9 + 7
    dp = [1] * 10
    for i in range(1, n):
        tmp = [0] * 10
        for j in range(10):
            for mv in moves[j]:
                tmp[j] = (tmp[j] + dp[mv]) % mod
        dp = tmp
    return sum(dp) % mod

Explanation:

We create a 2D list called moves containing all the possible moves from each digit on the dialer. We also define a counter variable mod to take care of modulo division for large numbers. We create an array "dp" of size 10 initialized with ones for the first iteration to store the number of sequences possible from each digit, using dynamic programming. For each subsequent iteration, we create a temporary array "tmp" to store the updated sequences possible for each digit in the current iteration and update the original dp array after each pass for the final result. We use the moves list to move the knight and add up the possible sequences we can create. In the end, we take the sum of all the values in the dp array and return the answer modulo mod as defined.

The time complexity of the above solution is O(n), and the space complexity is O(1).

In the end, we will find all the possible sequences that can be generated by the knight starting at the digit at index 0 of the dialer and moving for n hops. The number of distinct numbers that can be made after n hops of the knight on the dialer will be the value returned by our DFS function.

1