Knights On A Keypad
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
0Starting 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.
Programming Praxis 
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.
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).
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 :)
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).
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).
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)); # => 1424I 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:
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:
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.
(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!
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)))A solution in Haskell:
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]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.3139920234680176Am 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:
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"; }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 (
select lvl, moves, count() as cnt
from
walker
group by lvl, moves
having max(length(moves))
) A
group by lvl
;
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));