## 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.

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.

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

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.

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

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

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.

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).

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

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 :)

J2kun: Well, why don’t

youimplement 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), notO(n^{2}); the matrix isnalong one dimension but 9 on the other dimension. Your matrix algorithm does require much less space, however,O(1) compared toO(n).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.

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

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).

I took the brute force matrix approach:

it appears to run relatively quickly:

My solution that requires constant memory although it does not seem to be as fast as the others above.

or here:

http://codepad.org/VY2TvQjU

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

Simple, with memoization.

P!

In CL, more idiomatic.

A solution in Haskell:

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

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

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?

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.

@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!

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)`

}

Solution in Clojure: http://georgepabst.com/106505810

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?

please help me awaiting for your reply

by sathish

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

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;

}

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));

}

}

— 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

— https://sqlite.org/lang_with.html

.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 () as cntselect lvl, moves, count(

from

walker

group by lvl, moves

having max(length(moves))

) A

group by lvl

;

C++ recursive version