Solved
Posts: 1,318

# Knights of the Dialing Pad (Math Puzzle)

Hi,

It has been quite some time since the last post I made like this so I hope people will enjoy it.

The numbers on a typical phone pad are arranged as follows

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

Accepted Solutions
Solution
‎03-11-2012 10:28 AM
Posts: 5,526

## Re: Knights of the Dialing Pad (Math Puzzle)

I took me a while to figure out how simple it was, but here it is :

%let n=50;

array Ns{6} n13 n2 n46 n79 n8 n0 (6*1);
array Ts{6} t13 t2 t46 t79 t8 t0;
format n13 best32.;
n=1;
output;
do n=2 to &n;
do j=1 to 6; Ts{j} = Ns{j}; end;
n13 = t46 + t8;
n2 = t79 + t79;
n46 = t13 + t79 + t0;
n79 = t2 + t46;
n8 = t13 + t13;
n0 = t46 + t46;
output;
end;

proc print; run;

PG

PG

All Replies
Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

If I understood what is your mean .

```data temp;
infile datalines dlm=' ' ;
input _start \$ _end \$;
flag+1;
datalines;
1 6
1 8
2 7
2 9
2 0
3 4
3 8
4 3
4 9
4 0
6 1
6 7
6 0
7 2
7 6
8 1
8 3
9 2
9 4
0 4
0 6
;
run;
%let start=1;
%let length=8;
proc sort data=temp nodupkey;
by _start _end;
run;
data _null_;
if 0 then set temp;
declare hash ha(hashexp:10,dataset:'temp');
declare hiter hi('ha');
ha.definekey('flag');
ha.definedata('_start','_end');
ha.definedone();
length path  _path \$ 800;
declare hash pa(ordered:'Y');
declare hiter h_p('pa');
pa.definekey('count');
pa.definedata('count','path');
pa.definedone();
do until(last);
set temp(where=(_start="&start")) end=last;
_count+1; count=_count;
path=cats(_start,_end);
end;
do while(h_p.next()=0 and length(path) le &length);
_path=path; if length(path) eq &length then n+1;
do while(hi.next()=0);
if substr(path,length(path),1) eq strip(_start) then do;
end;
end;
end;
putlog 'How many paths '  n ;
run;

```

Ksharp

Frequent Contributor
Posts: 139

## Knights of the Dialing Pad (Math Puzzle)

Hi,

Can you please explain how it would from 4 to 0.

Thanks  & Regards,

Manoj Bansal

Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

A knight moves two steps either horizontally or vertically followed by one step .

So first move two steps 4 -> . then followed by one step . -> 0

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

Frequent Contributor
Posts: 139

## Knights of the Dialing Pad (Math Puzzle)

So We Can consider the . to traverse the path but . cannot be destination. am i right?

Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

I think so. But this need to ask FriedEgg. Maybe He can clarify it more.

Posts: 1,318

## Knights of the Dialing Pad (Math Puzzle)

KSharp,

As always I can count on you for a solution.  The assumption for traversing from 4 -> 0 or 6-> 0 and visa-versa is fine.  There is a issue with your proposed solution however.  You have traversal 2 -> 0, this is not possible and causes an inaccurate solution.  Once this is removed your code will provide accurate solutions, very quickly, for short paths.  Finding the solution to a longer path however is very painful with this method.  Say a length of 50, for example.  Can you come up with a way to calculate longer paths?

`Ksharp wrote:data temp;infile datalines dlm=' ' ;input _start \$ _end \$;flag+1;datalines;1 61 82 72 92 0`
Super User
Posts: 10,770

## Re: Knights of the Dialing Pad (Math Puzzle)

Now I want to know where this Math Puzzle come from ?

And It is fastest method I can think.

```data temp;
infile datalines dlm=' ' ;
input _start : \$1. _end : \$1.;
datalines;
1 6
1 8
2 7
2 9
3 4
3 8
4 3
4 9
4 0
6 1
6 7
6 0
7 2
7 6
8 1
8 3
9 2
9 4
0 4
0 6
;
run;
%let start=1;
%let length=16;
data _null_;
if _n_ eq 1 then do;
length path  _path \$ 51;
if 0 then set temp;
declare hash ha(hashexp:10,dataset:'temp',multidata:'Y');
declare hiter hi('ha');
ha.definekey('_start');
ha.definedata('_end');
ha.definedone();
end;
declare hash pa(ordered:'Y');
declare hiter h_p('pa');
pa.definekey('count');
pa.definedata('path');
pa.definedone();

set temp(where=(_start="&start")) end=last ;
count=0;count+1;
call missing(path);path=cats(_start,_end);
do while(h_p.next()=0 and length(path) lt &length+1);
_path=path;
if length(path) eq &length then n+1;
_start=substr(path,length(path),1);
if (ha.find()=0) then do;
count+1;
path=cats(path,_end);
path=_path;
rc=ha.find_next();
do while(rc=0);
count+1;
path=cats(path,_end);
path=_path;
rc=ha.find_next();
end;
end;
end;
if last then putlog 'How many paths '  n ;
run;
```

Ksharp

Posts: 1,318

## Knights of the Dialing Pad (Math Puzzle)

This puzzle was presented to me by a friend (who is a math professor at the University of Colorado) via email, I'm not sure where he got it from or if he made it up.

Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

Haha.

I find a faster way.

```data temp;
infile datalines dlm=' ' ;
input _start : \$1. _end : \$1.;
datalines;
1 6
1 8
2 7
2 9
3 4
3 8
4 3
4 9
4 0
6 1
6 7
6 0
7 2
7 6
8 1
8 3
9 2
9 4
0 4
0 6
;
run;
%let start=1;
%let length=16;

%let len=%eval(&length+1);
data _null_;
if _n_ eq 1 then do;
length end temp_end \$ 1;
length length temp_len 4 ;
if 0 then set temp;
declare hash ha(hashexp:10,dataset:'temp',multidata:'Y');
declare hiter hi('ha');
ha.definekey('_start');
ha.definedata('_end');
ha.definedone();
end;
declare hash pa(ordered:'Y');
declare hiter h_p('pa');
pa.definekey('count');
pa.definedata('end','length');
pa.definedone();

set temp(where=(_start="&start")) end=last ;
count=0;count+1; end=_end; length=2;
do while(h_p.next()=0 and length lt &len );
temp_end=end; temp_len=length;
if length eq &length then n+1;
if (ha.find(key:end)=0) then do;
count+1;
end=_end ;
length+1;
end=temp_end; length=temp_len;
rc=ha.find_next();
do while(rc=0);
count+1;
end=_end ;
length+1;
end=temp_end; length=temp_len;
rc=ha.find_next();
end;
end;
end;
if last then putlog 'How many paths '  n ;
run;

```

Ksharp

Posts: 1,318

## Knights of the Dialing Pad (Math Puzzle)

Nice work on improving the brute force method.  It can still be taken a step further to calculate nearly any given length extremely fast.  The answer of n paths of x length follows a sequence that can be exploited.  If you want more clues send me a email.

Super Contributor
Posts: 713

## Knights of the Dialing Pad (Math Puzzle)

Kudos for the attempt.Unfortunately this could not be run on SAS 9.1.3

Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

Yes. Because I used a new method find_next().

I can modify my code to run under SAS9.1.3, If you were interested.

Ksharp

Super Contributor
Posts: 713

## Knights of the Dialing Pad (Math Puzzle)

That would be great!

Super User
Posts: 10,770

## Knights of the Dialing Pad (Math Puzzle)

FriedEgg.

Under your implication, It is a faster code. I am thinking a better algorithm.

```data temp;
infile datalines dlm=' ' ;
input _start : \$1. _end : \$1. ;
datalines;
1 6
1 8
2 7
2 9
3 4
3 8
4 3
4 9
4 0
6 1
6 7
6 0
7 2
7 6
8 1
8 3
9 2
9 4
0 4
0 6
;
run;
%let start=1;
%let length=16;

%let len=%eval(&length+1);
data _null_;
length end \$ 1;
length temp_len length 4;
declare hash pa(ordered:'Y',hashexp:16);
declare hiter h_p('pa');
pa.definekey('count');
pa.definedata('end','length');
pa.definedone();

set temp(where=(_start="&start")) end=last ;
do while(h_p.next()=0 and length lt &len );
temp_len=length;
if length eq &length then sum+1 ;
else do;
select(end);
when('0') do;
end;
when('1') do;
end;
when('2') do;
end;
when('3') do;
end;
when('4') do;
end;
when('6') do;
end;
when('7') do;
end;
when('8') do;
end;
when('9') do;
end;
otherwise;
end;
end;
end;
if last then putlog 'How many paths : '  sum ;
run;
```

Ksharp

🔒 This topic is solved and locked.

Discussion stats
• 24 replies
• 2014 views
• 6 likes
• 5 in conversation