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.

Each horizontal/vertical line: 12 palindromes.
A diagonal N squares long: N(N+1)/2 palindromes.

Now, it's counting: 16 lines, plus two 8-squares diagonales, plus 4 each of 7-, 6-, 5-, 4-, 3-, and 2- squares diagonals.

Did I miss anything?

Posted by e.g. on 2006-06-10 16:24:54