Take a standard 8x8 chessboard, number the black squares 1 and the white squares 0. How many palindromes does this board contain in 'word-search' fashion?
Now generalize and find a formula for any n*n board.
Notes: A palindrome and its reversal should not be counted twice. A palindrome must be at least two digits long and leading zeroes are not allowed. Numbers can be read in any single vertical, horizontal or diagonal direction.
Using the program from my previous post, here are some numbers by actual count:
With white corners for odd n:
n palindromes diagonal orthogonal
2 1 1 0
3 6 4 2
4 22 14 8
5 46 28 18
6 91 55 36
7 148 88 60
8 236 140 96
9 340 200 140
10 485 285 200
11 650 380 270
12 866 506 360
13 1106 644 462
14 1407 819 588
15 1736 1008 728
16 2136 1240 896
17 2568 1488 1080
18 3081 1785 1296
19 3630 2100 1530
20 4270 2470 1800
21 4950 2860 2090
22 5731 3311 2420
23 6556 3784 2772
24 7492 4324 3168
25 8476 4888 3588
26 9581 5525 4056
27 10738 6188 4550
28 12026 6930 5096
29 13370 7700 5670
30 14855 8555 6300
31 16400 9440 6960
32 18096 10416 7680
33 19856 11424 8432
34 21777 12529 9248
35 23766 13668 10098
36 25926 14910 11016
37 28158 16188 11970
38 30571 17575 12996
39 33060 19000 14060
40 35740 20540 15200
With black corners for odd n:
n palindromes diagonal orthogonal
2 1 1 0
3 10 6 4
4 22 14 8
5 54 32 22
6 91 55 36
7 160 94 66
8 236 140 96
9 356 208 148
10 485 285 200
11 670 390 280
12 866 506 360
13 1130 656 474
14 1407 819 588
15 1764 1022 742
16 2136 1240 896
17 2600 1504 1096
18 3081 1785 1296
19 3666 2118 1548
20 4270 2470 1800
21 4990 2880 2110
22 5731 3311 2420
23 6600 3806 2794
24 7492 4324 3168
25 8524 4912 3612
26 9581 5525 4056
27 10790 6214 4576
28 12026 6930 5096
29 13426 7728 5698
30 14855 8555 6300
31 16460 9470 6990
32 18096 10416 7680
33 19920 11456 8464
34 21777 12529 9248
35 23834 13702 10132
36 25926 14910 11016
37 28230 16224 12006
38 30571 17575 12996
39 33136 19038 14098
40 35740 20540 15200
|
|
Posted by Charlie
on 2006-06-11 10:08:42 |
some numbers by actual count
