Knights On A Keypad

January 20, 2012

The obvious solution is recursive: the number of paths of length n that the knight can trace from digit d is the sum of the number of paths of length n−1 that the knight can trace from the successors of digit d:

```(define (count n from) ; recursive solution   (let ((graph '((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) (0 4 6))))     (if (= n 1) 1       (sum (map (lambda (x) (count (- n 1) x))                 (cdr (assoc from graph)))))))```

For instance,

```> (count 10 1) 1424```

That works, but with exponential time complexity; it is inconvenient to calculate `(count 25 1)` and painful to calculate `(count 50 1)`. The dynamic programming solution stores n rows by 9 columns of counts in a matrix, building up the matrix starting from row 1:

```(define (count n) ; memoized solution   (let ((counts (make-matrix n 9 1))         (graph (vector '(4 6) '(5 7) '(3 6) '(2 7 8)                  '(0 5 8) '(1 4) '(0 2) '(1 3) '(3 4))))     (do ((r 1 (+ r 1))) ((= n r) (matrix-ref counts (- n 1) 0))       (do ((c 0 (+ c 1))) ((= c 9))         (matrix-set! counts r c           (sum (map (lambda (c) (matrix-ref counts (- r 1) c))                     (vector-ref graph c))))))))```

Note that the `graph` data structure changes from a list to a vector, and instead of storing digits it stores the columns of the matrix in which the digit is found. Here are the first ten rows of the dynamic programming matrix:

```   1 2 3 4 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 2 2 2 2 3 5 4 5 6 6 5 4 5 6 4 10 10 10 16 16 10 10 10 12 5 26 20 26 32 32 26 20 26 32 6 52 52 52 84 84 52 52 52 64 7 136 104 136 168 168 136 104 136 168 8 272 272 272 440 440 272 272 272 336 9 712 544 712 880 880 712 544 712 880 10 1424 1424 1424 2304 2304 1424 1424 1424 1760 ```

The dynamic programming version of the function is very fast:

```> (count 10) 1424 > (time (count 1000)) 1 collection 15 ms elapsed cpu time, including 0 ms collecting 0 ms elapsed real time, including 0 ms collecting 1797296 bytes allocated, including 3138152 bytes reclaimed 11510938255822675957815810378777791896570323950771838174021217085101456431508619 76139657395678668773773326341813271631411424403184193325316575958808100160391628 81799601851712976918057797975890692565692814769008372525555560482873241331236262 66988127396088232507832827291811704979886473421821866430689013979724773702240081 4924823939354135385894667021349644402688```

That poor knight will have to gallop hard to trace all those paths!

We used sum and matrices from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/k8lxMxUC.

Pages: 1 2

29 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--;)
p[i][j] = adj(i, j, NUM_KEYS);
}

// 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

A solution in Haskell:

```> 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";
}
```
25. Hanno said

In the spirit of beating a dead horse, let me point out you can get a further speed improvement over the memoized solution by taking the transition matrix approach and exploiting the keypad symmetry to reduce the number of states. Follow this line of thought and you can reduce the problem to 2×2 matrix multiplication, which makes the code heap-access free and tiny, hence roughly 100x faster on my laptop. I timed the C# code below at 10 nanoseconds.

static long knights(int digits)
{
long V6;
long V8;
int start;

if (digits == 1)
return 1;

if( 0 == digits % 2 )
{ //even case; start with second move
V6= 1;
V8= 1;
start = 2;
}
else
{ //odd case; start with third move
V6= 3;
V8= 2;
start = 3;
}

//multiply 2×2 transition matrix
for (int i = start; i < digits; i += 2)
{
long newV6 = 2 * V8 + 4 * V6;
long newV8 = 2 * V8 + 2 * V6;

V6 = newV6;
V8 = newV8;
}

return V6 + V8;
}

26. Akshay said

package com.main;

import java.io.*;
import java.util.*;

public class UniqueKnights {
/**
* How many unique, 7-digit phone numbers can a knight dial on a standard
* 1-9+0 phone pad, starting from the 1. 1 2 3 4 5 6 7 8 9 0 1616161 1604381
* => ??? 161 167 160 181 183 => 5
*/
public static void main(String[] args) {
map.put(0, Arrays.asList(4, 6));
map.put(1, Arrays.asList(6, 8));
map.put(2, Arrays.asList(7,9));
map.put(3, Arrays.asList(4,8));
map.put(4, Arrays.asList(3,9,0));
map.put(5, Arrays.asList());
map.put(6, Arrays.asList(1,7,0));
map.put(7, Arrays.asList(2,6));
map.put(8, Arrays.asList(1,3));
map.put(9, Arrays.asList(2,4));
System.out.println(getUniqueDigits(1, 3));
}

``````static HashMap<Integer, List<Integer>> map = new HashMap<>();
// array / data structure of mappings.
// until steps < stepSize we create numbers and add it to list
// check in the list
// count the size of list
public static int getUniqueDigits(int digit, int steps) {
int curStep = 1;
uniqueDigitsHelper(digit, curStep, steps);
return uniqueDigitsHelper(digit, curStep, steps);
}

public static int uniqueDigitsHelper(int digit, int curStep, int step) {
if (curStep == step) {
return 1;
}
List<Integer> letterCombination = map.get(digit);
int count = 0;
for (int i : letterCombination) {
digit = i;
//System.out.println(count);
count += uniqueDigitsHelper(digit, curStep + 1, step);
}
return count;
}
``````

}

27. lindsay said

— This has been tested in SQLite only.

— It uses CTEs to do a depth first traversal.

— Other DBs, may not have CTEs, or do concat and group_concat differently

.timer on
with recursive
depth (n) as (
values (16) — How deep to go
),
moves (node, child) as (
values
(0, 4), (0, 6),
(1, 6), (1, 8),
(2, 7), (2, 9),
(3, 4), (3, 8),
(4, 3), (4, 9), (4, 0),
(5, null),
(6, 1), (6, 7), (6, 0),
(7, 2), (7, 6),
(8, 1), (8, 3),
(9, 2), (9, 4)

),

— Recursive CTE to traverse The Tree

walker (lvl, node, child, moves) AS (
select
0, node, child, ”
from
moves
where node in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
UNION ALL
SELECT
lvl+1,
a.node,
b.child,
cast(a.moves as text)||cast(a.child as text)
FROM
walker a, moves b
where
(a.child is null or a.child=b.node)
and lvl < (select n from depth)
order by 2 desc
)
select lvl, count() as cnt from (
select lvl, moves, count(
) as cnt
from
walker
group by lvl, moves
having max(length(moves))
) A
group by lvl
;

28. greg said

C++ recursive version

```using int_array = std::array<uint64_t, 10>;

int_array count_paths(const int_array &cur, uint64_t len) {
static std::vector<std::vector<uint64_t>> dest = { {6, 4}, {6, 8}, {9, 7}, {4, 8}, {9, 3, 0}, {}, {7, 1, 0}, {6, 2}, {3, 1}, {4, 2} };
int_array res { 0 };
for (size_t i=0; i<10; ++i) {
if (cur[i])
for (auto j : dest[i])
res[j] += cur[i];
}
if (len == 1)
return res;
return count_paths(res, len - 1);
}

auto a = count_paths(int_array{0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 9); // 9 moves for a path of length 10
auto count = std::accumulate(a.begin(), a.end(), uint64_t(0));

```