### January 20, 2012

Today’s exercise is an interview question that appeared on Stack Overflow a few years ago:

The numbers on a telephone keypad are arranged thus:

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

Starting from the digit 1, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.

A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.

Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from digit 1. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 25 Responses to “Knights On A Keypad”

1. Jussi Piitulainen said

If one takes “path” to mean a sequence of distinct nodes, the number of different paths is small and plain recursion is well fast enough. One keeps track of visited nodes in order to not step on them again.

```(define (next node)
(vector-ref '#((4 6  ) (6 8  ) (7 9  ) (4 8  ) (0 3 9)
(     ) (0 1 7) (2 6  ) (1 3  ) (2 4  )) node))

(define (count from many)
(let dive ((from from) (seen (list from)) (many many))
(if (zero? many) 1
(apply + (map (lambda (to)
(if (memv to seen) 0
(dive to (cons to seen) (- many 1))))
(next from))))))

(define (count-all from)
(apply + (map (lambda (many) (count from many))
'(0 1 2 3 4 5 6 7 8 9))))
```

The total numbers of paths of any length from each node are as follows.

```guile> (map count-all '(0 1 2 3 4 5 6 7 8 9))
(31 29 29 29 25 1 25 29 29 29)
```

There is no way out of (or in to) 5, and 0 stands out as its own kind, and 4 and 6 are symmetric to each other. Counting paths of length 8 or 9 is already overkill: there can be none.

2. programmingpraxis said

Jussi: A path may visit the same digit more than once. That’s explicitly stated in the last sentence of the problem.

3. Jussi Piitulainen said

Somehow I managed to miss that statement. I see it now. Sorry about the noise. (Though I like to think of variations.)

4. j2kun said

Construct an adjacency matrix that represents the possible destinations from each square on the keypad. This is a 10×10 matrix of ones and zeros, where the i,j entry contains a 1 if and only if there is a knight’s move from square i to square j (let’s index from zero just for fun). Taking powers of this matrix gives a matrix containing in each i,j entry the number of distinct paths (walks, if you want to use the graph-theoretic term) from the ith square to the jth square. Since we’re only multiplying 10×10 matrices, I’d expect this to be relatively fast, even for some large n. However, if you want to get fancy with the cheese-whiz, we could diagonalize the adjacency matrix (it is symmetric by construction, so by the spectral theorem it is diagonalizable), take powers of that, and then revert it to its original form using the change of basis we got from our diagonalization process. The fact that this works is simple matrix algebra. Taking powers of an nxn diagonal matrix is linear in n, so the speed of the algorithm boils down to the speed of the decomposition, which is essentially constant (it’s only a 10×10 matrix).

Unfortunately I don’t have the time to code this up right now, but it’d be a 5 minute affair in Mathematica or any language that has the diagonalization thing built in.

5. j2kun said

Here’s my mathematica solution, using the idea from my previous comment, and Mathematica’s JordanDecomposition routine (which anyone could implement as an exercise, I’m sure).

```matrix = {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 1,
0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 0, 0, 0, 1,
0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {1, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 1, 0, 0,
0}, {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 0,
0}} ;

numPaths[n_] :=
Module[{changeOfBasis, diagonalMatrix, diagonalPower, originalPower},
{changeOfBasis, diagonalMatrix} = JordanDecomposition[N[matrix, 20]];
diagonalPower = DiagonalMatrix[Diagonal[diagonalMatrix]^(n-1)];
originalPower = changeOfBasis.diagonalPower.Inverse[changeOfBasis];
Return[Map[Apply[Plus, #] &, Round[originalPower]][[2]]]
];
```

And running it on n=10 gives the 9th matrix power (to agree with your definition of path length), and provides the correct answer:

```Timing[numPaths[10]]
{0.044003, 1424}

Timing[numPaths[1000000]]
{0.076004, 411651680085467700452...}
```

So we can compute the right value for n=1,000,000, but the number has 359,503 digits, so it won’t fit in this comment. The nice thing is, while the dynamic approach is O(n^2), this approach is O(n)! The first result of the Timing call gives the CPU time spent on the function, which is a mere 0.076 seconds. Beat that :)

6. programmingpraxis said

J2kun: Well, why don’t you implement JordanDecomposition as an exercise. If you like, email me privately, and I’ll help you write it as a guest author for a future exercise.

By the way, the dynamic programming solution is O(n), not O(n2); the matrix is n along one dimension but 9 on the other dimension. Your matrix algorithm does require much less space, however, O(1) compared to O(n).

7. j2kun said

Yes of course, it’s O(n). I just saw a big table in your solution and had that knee-jerk, witch-hunting reaction, but I was mistaken.

At the risk of sounding pretentious, here are a few more notes on why my algorithm is neat: First, it counts all paths between all pairs of squares on the keypad, so it gives us much more information; and second, the same algorithm applies to counting paths in any graph. All we need to do to generalize the algorithm is change the input matrix, and we still have the lightning-fast implementation.

I’ll get back to you about writing JordanDecomposition. It’s significantly less interesting than what you can use it for, and if I remember correctly it basically reduces to row-reduction. Plus, for a general matrix, JordanDecomposition is frowned upon because it’s numerically unstable. So people usually avoid it.

8. Jan Van lent said

You can use the matrix approach to get a closed-form expression (Maple code below).
This formula involves the golden ratio (just as for the Fibonacci numbers).

phi := (sqrt(5)+1)/2; # golden ratio
q := ;
H := ;
Phi := ;
c := 2^(n/2)/40 * q^+ . H . Phi;
simplify(eval(c, n=9)); # => 1424

9. Jan Van lent said

You can use the matrix approach to get a closed-form expression (Maple code below).
This formula involves the golden ratio (just as for the Fibonacci numbers).

```phi := (sqrt(5)+1)/2; # golden ratio
q := < 10, 4*sqrt(5), 5*sqrt(2), 3*sqrt(2)*sqrt(5) >;
H := < 1,  1,  1,  1;
1,  1, -1, -1;
1, -1, -1,  1;
1, -1,  1, -1 >;
Phi := < phi^n, (-phi)^n, phi^(-n), (-phi)^(-n) >;
c := 2^(n/2)/40 * q^+ . H . Phi;
simplify(eval(c, n=9)); # => 1424
```
10. ardnew said

I took the brute force matrix approach:

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_KEYS 10
#define POWER     9

typedef unsigned short key;

key map[NUM_KEYS] = {
40, // 0000101000
10, // 0000001010
5, // 0000000101
34, // 0000100010
577, // 1001000001
0, // 0000000000
772, // 1100000100
136, // 0010001000
320, // 0101000000
160  // 0010100000
};

int adj(key i, key j, int n)
{
return map[i] >> (n - j - 1) & 1;
}

// dot product
int dot(int **p, key i, key j, int n)
{
int m, s = 0;

for (m = 0; m < n; ++m)
s += adj(m, i, n) * p[j][m];

return s;
}

// multiplies matrix p by map
void matmult(int **p, int **q, int n)
{
int i, j;

for (i = n; i--;)
for (j = n; j--;)
q[i][j] = dot(p, i, j, n);

for (i = n; i--;)
for (j = n; j--;)
p[i][j] = q[i][j];
}

int main(void)
{
// result matrix
int **p = malloc(NUM_KEYS * sizeof(p));

// scratch matrix for storing inner products
int **q = malloc(NUM_KEYS * sizeof(p));

int i, j, k = 0;

// initialize the matrices
for (i = 0; i < NUM_KEYS; ++i)
{
p[i] = malloc(NUM_KEYS * sizeof(*p));
q[i] = malloc(NUM_KEYS * sizeof(*p));

// scratch matrix
memset(q[i], 0, NUM_KEYS);

// result matrix
for (j = NUM_KEYS; j--;)
}

// perform matrix multiplication
for (i = POWER; --i;)
matmult(p, q, NUM_KEYS);

// sum the 1 key's components
for (i = NUM_KEYS; --i;)
k += p[1][i];

printf("num paths = %d\n", k);

return 0;
}
```

it appears to run relatively quickly:

```\$ time r
num paths = 1424

real  0m0.029s
user  0m0.030s
sys   0m0.015s
```
11. My solution that requires constant memory although it does not seem to be as fast as the others above.

```from collections import defaultdict

def count_knight_paths(maxlevel):
jump = {0: [6, 4], 1: [6, 8], 2: [9, 7],
3: [4, 8], 4: [9, 3, 0], 6: [7, 1, 0],
7: [6, 2], 8: [3, 1], 9: [4, 2]}
c = { 1 : 1 }
for level in range(maxlevel):
cprim = defaultdict(int)
for key in c:
for jumped in jump[key]:
cprim[jumped] += c[key]
c = cprim
return sum(c.values())

if __name__ == "__main__":
for i in range(10):
print(i + 1, count_knight_paths(i))
```

or here:

12. […] a perfect brain teaser for a Friday night. Let’s find how many paths of a certain length a chess knight on a phone […]

13. Axio said

Simple, with memoization.

```(define (nexts n)
(case n ((0) '(4 6)) ((1) '(6 8)) ((2) '(7 9))
((3) '(4 8)) ((4) '(3 9 0)) ((6) '(1 7 0)) ((7) '(2 6))
((8) '(1 3)) ((9) '(2 4)) (else (error "impossiburu!"))))

(define (count-memo from len memo)
(let ((r (table-ref memo (cons from len) #f)))
(or r (let ((r (if (zero? len)
1
(fold-left
+ 0 (map
(lambda (new-from) (count-memo new-from (1- len) memo))
(nexts from))))))
(table-set! memo (cons from len) r)
r))))

(define (test-memo n) (count-memo 1 n (make-table test: equal?)))
```

P!

14. Axio said

In CL, more idiomatic.

```(defvar nexts '#((4 6) (6 8) (7 9) (4 8) (3 9 0) () (1 7 0) (2 6) (1 3) (2 4)))
(defun nexts (n) (aref nexts n))

(defun count-memo (from len memo)
(or (and (zerop len) 1)
(gethash (cons from len) memo)
(setf (gethash (cons from len) memo)
(apply #'+ (mapcar
(lambda (new-from) (count-memo new-from (1- len) memo))
(nexts from))))))

(defun test-memo (n) (count-memo 1 n (make-hash-table :test #'equal)))
```
15. Tante Hedwig said
``import Data.Map as Mknights      = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]knightsTable = M.fromList \$ zip [0..] knightsnextMove     = concatMap ((\x -> case x of (Just x) -> x) . flip M.lookup knightsTable)count n s    = length \$ foldl (\acc f -> f acc) s (replicate (n-1) nextMove)``
16. Tante Hedwig said

```> import Data.Map as M
> knights      = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]
> knightsTable = M.fromList \$ zip [0..] knights
> nextMove     = concatMap ((\x -> case x of (Just x) -> x) . flip M.lookup knightsTable)
> count n s    = length \$ foldl (\acc f -> f acc) s (replicate (n-1) nextMove)
```
17. dmitru said

Here is my DP solution. It uses constant memory and takes linear time:

```moves = [[4, 6], [8, 6], [7, 9],
[4, 8], [3, 0, 9], [],
[1, 7, 0], [2, 6], [1, 3],
[2, 4]]

def solve(n, pos):
row = [1 for p in range(10)]
for l in range(n - 1):
for p in range(10):
new_row = [0 for p in range(10)]
for np in moves[p]:
new_row[p] += row[np]
row = new_row
return row[pos]
```
18. dmitru said

Here is my DP solution. It uses constant memory and is pretty fast:

```def solve(n, pos):
table = [[0 for p in range(10)] for l in range(n + 1)]
for p in range(10):
table[1][p] = 1
for l in range(2, n + 1):
for p in range(10):
table[l][p] = 0
for np in moves[p]:
table[l][p] += table[l - 1][np]
return table[n][pos]

for length in (1000, 5000, 10000):
print(runtime(solve, length, 1))

0.015690088272094727
0.1218729019165039
0.3139920234680176
```
19. Jeff said

Am I missing something or is the solution posted at the top of page 2 really counting the number of unique digits of length n starting at 1? I’m just going by the ‘graph’ data structure. I’d imagine that a path of length=1 would include two digits and so there should be 4 unique paths of length=1 from the number 1 (1 to 6 via 2, 1 to 6 via 4, 1 to 8 via 2, 1 to 8 via 4).

If I’m reading it correctly, to solve the problem as written I’d imagine the graph array would need to look more like this:

``` \$movesA = array( 0=>array(4,6), 1=>array(6,6,8,8), 2=>array(7,7,9,9), 3=>array(4,4,8,8), 4=>array(3,3,9,0), 5=>NULL, 6=>array(1,1,7,7,0), 7=>array(2,2,6,6), 8=>array(1,1,3,3), 9=>array(4,4,2,2), ); ```

Then, instead of returning 1 if n==1 it should be modified to return 1 if n==0. Counting this way the number of unique 10-segment paths that can be drawn starting from the 1 key is 1267976.

Does that seem right?

20. programmingpraxis said

Jeff: No, that’s not right.

First, a path with two digits has length 2, not length 1.

Second, there are two paths of length 2 starting from digit 1: 16 and 18.

Third, your successor array is incorrect. There are only two successors of 1 — 6 and 8 — not four successors. Your successor lists for 2, 3, 4, 6, 7, 8 and 9 are similarly incorrect.

21. Jeff said

@programmingpraxis And that’s certainly the problem that most of the solutions are solving, and where I would have gone if the problem had been stated something like, “determine how many different numbers can be formed of length n.”

Either way, they’re both great puzzles. Thanks for the fun excercise!

22. Raphael Fuchs said

My solution in Scala, time and space in O(n):
``` val neighbours = Map(   0 -> List(4,6),   1 -> List(6,8),   2 -> List(7,9),   3 -> List(4,8),   4 -> List(0,3,9),   5 -> List(),   6 -> List(0,1,7),   7 -> List(2,6),   8 -> List(1,3),   9 -> List(2,4) )```

``` def count(n: Int): Int = {   // memoization table (DP)   val T = Array.ofDim[Int](n+1, 10)   // initialize first row   for (key <- 0 to 9)     T(0)(key) = 1   // fill in other rows   for (n <- 1 to n; k <- 0 to 9) {     T(n)(k) = neighbours(k) map { T(n-1)(_) } sum   } ```

```  T(n)(1) } ```

23. sathish said

Am a M.C.A Student i cant understand the problem will you please help me to understand the problem?
My doubt is how to find length and the value 1424 is been calculated?
by sathish

24. A did one for a couple other pieces as well just to see what it looked like:

```my %pieces_moves = (
knight => [
[4, 6],
[8, 6],
[7, 9],
[4, 8],
[3, 0, 9],
[],
[1, 7, 0],
[2, 6],
[1, 3],
[2, 4]
],
pawn => [
[8],
[2, 4],
[1, 3, 5],
[2, 6],
[1, 5, 7],
[2, 4, 6, 8],
[3, 5, 9],
[4, 8],
[0, 5, 7, 9],
[6, 8]
],
queen => [
[2, 5, 7, 8, 9],
[2, 3, 4, 5, 7],
[0, 1, 3, 4, 5, 6, 8],
[1, 2, 5, 6, 9],
[1, 2, 5, 6, 7, 8],
[0, 1, 2, 3, 4, 6, 7, 8, 9],
[2, 3, 4, 5, 8, 9],
[0, 1, 4, 5, 8, 9],
[0, 2, 4, 5, 6, 7, 9],
[0, 3, 5, 6, 7, 8]
],
);

memoize 'count_ways';
sub count_ways {
my (\$piece, \$n, \$pos) = @_;
\$pos //= 0;

return 1
if \$n == 1;

my \$sum = 0;
foreach my \$move ( @{\$pieces_moves{\$piece}->[\$pos]} ) {
\$sum += count_ways(\$piece, \$n - 1, \$move);
}

return \$sum;
}

foreach my \$piece ( qw(knight queen pawn) ) {
print "\$piece\n";
print "----------\n";
print 'Memoized solution: ' . count_ways(\$piece, 10, 1)    . "\n";
print "\n";
}
```