# Knight on a Phone

Given a phone keypad as shown below:

``````0 1 2
3 4 5
6 7 8
9``````

How many different 10-digit numbers can be formed starting from 1? The constraint is that the movement from 1 digit to the next is similar to the movement of the Knight in a chess game.

For eg. if we are at 1 then the next digit can be either 6 or 8 if we are at 6 then the next digit can be 1, 7 or 0.

Repetition of digits are allowed - 1616161616 is a valid number.

Generalize this problem to find the number of unique numbers of length n that can be form starting from any number.

This question was taken from: https://stackoverflow.com/questions/2893470/generate-10-digit-number-using-a-phone-keypad/

Complexity: BF: O(2*n + 3*m) time where n + m = length number, DP: O(Length) time

``````import queue

def chess_numbers_bf(start, length):
if length <= 0:
return 0
phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
total = 0
q = queue.Queue()
q.put((start, 1))

while not q.empty():
front = q.get()
val = front[0]
len_ = front[1]
if len_ < length:
for elm in phone[val]:
q.put((elm, len_ + 1))
else:
total += 1

def chess_numbers_dp(start, length):
if length <= 0:
return 0

phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
memory = {}

def __chess_numbers_dp(s, l):
if (s, l) in memory:
return memory[(s, l)]
elif l == length - 1:
memory[(s, l)] = 1
return 1
else:
total_n_ways = 0
for number in phone[s]:
total_n_ways += __chess_numbers_dp(number, l+1)
memory[(s, l)] = total_n_ways
return __chess_numbers_dp(start, 0)

# bf
for i in range(0, 10):
print(i, chess_numbers_bf(3, i))
print('\n')

for i in range(0, 10):
print(i, chess_numbers_bf(9, i))
print('\n')

# dp
for i in range(0, 10):
print(i, chess_numbers_dp(3, i))
print('\n')

# dp
for i in range(0, 10):
print(i, chess_numbers_dp(9, i))
print('\n')``````

Last updated