All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 1 Palindrome 1 (Posted on 2006-06-10)
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.

 See The Solution Submitted by Jer Rating: 3.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 some numbers by actual count Comment 8 of 8 |

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

 Search: Search body:
Forums (0)