title: Generate 10-digit number using a phone keypad
body: <p>Given a phone keypad as shown below:</p>
  
  <pre><code>1 2 3
  4 5 6
  7 8 9
    0
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Repetition of digits are allowed - 1616161616 is a valid number.</p>
  
  <p>Is there a polynomial time algorithm which solves this problem? The problem requires us to just give the count of 10-digit numbers and not necessarily list the numbers.</p>
  
  <p>EDIT: I tried modeling this as a graph with each digit having 2 or 3 digits as its neighbors. Then I used DFS to navigate upto the depth of 10 nodes and then increment the count of numbers each time I reached the depth of 10. This obviously is not polynomial time. Assuming each digit had just 2 neighbors, this would have required at least 2^10 iterations. </p>
  
  <p>The variable here is the number of digits. I have taken the eg. of 10 digit numbers. It could as well be n-digits.</p>