Written in each square of an infinite chessboard is the minimum number of moves needed for a knight to reach that square from a given square O. A square is called singular if 100 is written in it and 101 is written in all four squares sharing a side with it. How many singular squares are there?
clc; clearvars
board=zeros(500);
currList=zeros(500,2); nextList=currList;
currCt=1; nextCt=0;
currList(1,1)=1; currList(1,2)=1;
for currVal=0:100
newVal=currVal+1;
for point=1:currCt
x= currList(point,1);
y= currList(point,2);
newPts=[x+2 y+1;x+1 y+2;x-2 y-1;x-1 y-2;x+2 y-1;x+1 y-2;x-2 y+1;x-1 y+2];
for i=1:8
xN=newPts(i,1); yN=newPts(i,2);
if xN<1
xN=reflect(xN);
end
if yN<1
yN=reflect(yN);
end
if board(xN,yN)==0
board(xN,yN)=newVal;
nextCt=nextCt+1;
nextList(nextCt,:)=[xN,yN];
end
end
end
currCt=nextCt;
currList=nextList;
end
% Now report the state that is constructed above:
for lower=3:100
d=repmat('.',204);
upper=lower+1;
ct=0; ct2=0;
for x=1:300
for y=1:300
if board(x,y)==lower
if x==1
if board(x+1,y)==upper && board(x,y-1)==upper && board(x,y+1)==upper
ct=ct+2;
% disp([x y])
d(x,y)='+';
end
else
if y==1
if board(x+1,y)==upper && board(x-1,y)==upper && board(x,y+1)==upper
ct=ct+2;
% disp([x y])
d(x,y)='+';
end
else
if board(x+1,y)==upper && board(x-1,y)==upper && board(x,y+1)==upper && board(x,y-1)==upper
ct=ct+4;
% disp([x y])
d(x,y)='+';
else
if x==1 || y==1
ct2=ct2+2;
else
ct2=ct2+4;
end
d(x,y)='-';
end
end
end
end
end
end
disp([lower upper ct ct2 ct+ct2])
if lower==50
d
end
end
function r=reflect(x)
r=2-x;
end
the reflect function takes into consideration that MATLAB arrays, being matrices, are numbered starting at 1,1; there is no row 0 or column 0.
To show the board was populated correctly, the portion near the origin is shown here (The upper left corner is the origin; only the lower right quatrant is shown, along with its bounding "axes"; the other quadrants are of course symmetric). The origin shows a 2 as an artifact of zero representing an empty square available for occupation as well as the zero step at which it was occupied originally, and after 1 move was eligible for re-occupation by the knight, even though it was occupied at round zero.
>> board(1:20,1:20)
ans =
2 3 2 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11
3 2 1 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10 9 10
2 1 4 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11
3 2 3 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10 9 10
2 3 2 3 4 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11
3 4 3 4 3 4 5 4 5 6 5 6 7 8 7 8 9 10 9 10
4 3 4 3 4 5 4 5 6 5 6 7 6 7 8 9 8 9 10 11
5 4 5 4 5 4 5 6 5 6 7 6 7 8 7 8 9 10 9 10
4 5 4 5 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10 11
5 6 5 6 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10
6 5 6 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11
7 6 7 6 7 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10
6 7 6 7 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10 11
7 8 7 8 7 8 7 8 7 8 9 8 9 10 9 10 11 10 11 12
8 7 8 7 8 7 8 7 8 9 8 9 10 9 10 11 10 11 12 11
9 8 9 8 9 8 9 8 9 8 9 10 9 10 11 10 11 12 11 12
8 9 8 9 8 9 8 9 8 9 10 9 10 11 10 11 12 11 12 13
9 10 9 10 9 10 9 10 9 10 9 10 11 10 11 12 11 12 13 12
10 9 10 9 10 9 10 9 10 9 10 11 10 11 12 11 12 13 12 13
11 10 11 10 11 10 11 10 11 10 11 10 11 12 11 12 13 12 13 14
For various number of moves, surrounded by the next higher required number of moves, the answer is always 8*n, so for n=100, the answer is 800.
# n # n total
among not n
n n+1 n+1 surrounded
3 4 24 32 56
4 5 32 60 92
5 6 40 72 112
6 7 48 96 144
7 8 56 112 168
8 9 64 136 200
9 10 72 152 224
10 11 80 176 256
11 12 88 192 280
12 13 96 216 312
13 14 104 232 336
14 15 112 256 368
15 16 120 272 392
16 17 128 296 424
17 18 136 312 448
18 19 144 336 480
19 20 152 352 504
20 21 160 376 536
21 22 168 392 560
22 23 176 416 592
23 24 184 432 616
24 25 192 456 648
25 26 200 472 672
26 27 208 496 704
27 28 216 512 728
28 29 224 536 760
29 30 232 552 784
30 31 240 576 816
31 32 248 592 840
32 33 256 616 872
33 34 264 632 896
34 35 272 656 928
35 36 280 672 952
36 37 288 696 984
37 38 296 712 1008
38 39 304 736 1040
39 40 312 752 1064
40 41 320 776 1096
41 42 328 792 1120
42 43 336 816 1152
43 44 344 832 1176
44 45 352 856 1208
45 46 360 872 1232
46 47 368 896 1264
47 48 376 912 1288
48 49 384 936 1320
49 50 392 952 1344
50 51 400 976 1376
51 52 408 992 1400
52 53 416 1016 1432
53 54 424 1032 1456
54 55 432 1056 1488
55 56 440 1072 1512
56 57 448 1096 1544
57 58 456 1112 1568
58 59 464 1136 1600
59 60 472 1152 1624
60 61 480 1176 1656
61 62 488 1192 1680
62 63 496 1216 1712
63 64 504 1232 1736
64 65 512 1256 1768
65 66 520 1272 1792
66 67 528 1296 1824
67 68 536 1312 1848
68 69 544 1336 1880
69 70 552 1352 1904
70 71 560 1376 1936
71 72 568 1392 1960
72 73 576 1416 1992
73 74 584 1432 2016
74 75 592 1456 2048
75 76 600 1472 2072
76 77 608 1496 2104
77 78 616 1512 2128
78 79 624 1536 2160
79 80 632 1552 2184
80 81 640 1576 2216
81 82 648 1592 2240
82 83 656 1616 2272
83 84 664 1632 2296
84 85 672 1656 2328
85 86 680 1672 2352
86 87 688 1696 2384
87 88 696 1712 2408
88 89 704 1736 2440
89 90 712 1752 2464
90 91 720 1776 2496
91 92 728 1792 2520
92 93 736 1816 2552
93 94 744 1832 2576
94 95 752 1856 2608
95 96 760 1872 2632
96 97 768 1896 2664
97 98 776 1912 2688
98 99 784 1936 2720
99 100 792 1952 2744
100 101 800 1976 2776
In order to fit easily on the perplexus frame, the case of 50 surrounded by 51's is shown:
+ represents 50 surrounded by 51's
- represents 50 not fully surrounded by 51's (perhaps partially so)
. neither 50 or 51
'....................................................................................................+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'..................................................................................................-.+...
'.................................................................................................-.-....
'................................................................................................-.-.+...
'...............................................................................................-.-.+....
'..............................................................................................-.-.+.....
'.............................................................................................-.-.+......
'............................................................................................-.-.+.......
'...........................................................................................-.-.+........
'..........................................................................................-.-.+.........
'.........................................................................................-.-.+..........
'........................................................................................-.-.+...........
'.......................................................................................-.-.+............
'......................................................................................-.-.+.............
'.....................................................................................-.-.+..............
'....................................................................................-.-.+...............
'...................................................................................-.-.+................
'..................................................................................-.-.+.................
'.................................................................................-.-.+..................
'................................................................................-.-.+...................
'...............................................................................-.-.+....................
'..............................................................................-.-.+.....................
'.............................................................................-.-.+......................
'............................................................................-.-.+.......................
'...........................................................................-.-.+........................
'..........................................................................-.-.+.........................
'.........................................................................-.-.+..........................
'........................................................................-.-.+...........................
'.......................................................................-.-.+............................
'......................................................................-.-.+.............................
'.....................................................................-.-.+..............................
'....................................................................-.-.+...............................
'...................................................................-.-.+................................
'..................................................................-.-.+.................................
'.................................................................-.-.+..................................
'................................................................-.-.+...................................
'...............................................................-.-.+....................................
'..............................................................-.-.+.....................................
'.............................................................-.-.+......................................
'............................................................-.-.+.......................................
'...........................................................-.-.+........................................
'..........................................................-.-.+.........................................
'.........................................................-.-.+..........................................
'........................................................-.-.+...........................................
'.......................................................-.-.+............................................
'......................................................-.-.+.............................................
'.....................................................-.-.+..............................................
'....................................................-.-.+...............................................
'...................................................-.-.+................................................
'..................................................-.-.+.................................................
'.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.+..................................................
'..-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.+...................................................
'.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.+....................................................
'+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.....................................................
'........................................................................................................
'........................................................................................................
'........................................................................................................
In the case of n=100, the bottom edge looks like:
>> board(195:203,1:10)
ans =
98 97 98 97 98 97 98 97 98 97
99 98 99 98 99 98 99 98 99 98
98 99 98 99 98 99 98 99 98 99
99 100 99 100 99 100 99 100 99 100
100 99 100 99 100 99 100 99 100 99
101 100 101 100 101 100 101 100 101 100
100 101 100 101 100 101 100 101 100 101
101 0 101 0 101 0 101 0 101 0
0 101 0 101 0 101 0 101 0 101
where 0 represents a number higher than 101.
And the bottom right edge of the octagon looks like:
>> board(145:155,145:155)
ans =
96 97 98 97 98 99 98 99 100 99 100
97 98 97 98 99 98 99 100 99 100 101
98 97 98 99 98 99 100 99 100 101 100
97 98 99 98 99 100 99 100 101 100 101
98 99 98 99 100 99 100 101 100 101 0
99 98 99 100 99 100 101 100 101 0 101
98 99 100 99 100 101 100 101 0 101 0
99 100 99 100 101 100 101 0 101 0 0
100 99 100 101 100 101 0 101 0 0 0
99 100 101 100 101 0 101 0 0 0 0
100 101 100 101 0 101 0 0 0 0 0
and at the corner between those two:
>> board(195:205,95:105)
ans =
98 97 98 97 98 99 98 99 100 99 100
99 98 99 98 99 98 99 100 99 100 101
98 99 98 99 98 99 100 99 100 101 100
99 100 99 100 99 100 99 100 101 100 101
100 99 100 99 100 99 100 101 100 101 0
101 100 101 100 101 100 101 100 101 0 101
100 101 100 101 100 101 100 101 0 101 0
101 0 101 0 101 0 101 0 101 0 0
0 101 0 101 0 101 0 101 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
|
|
Posted by Charlie
on 2021-04-01 12:32:23 |
computer exploration and solution
