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.

If n is odd, does it matter if the corners are black or white?  It would seem that would be the case, as different subsets on the main diagonals, etc. would be disqualified for leading zeroes.  Or is there some peculiar reason that this factor cancels out somewhere?

Posted by Charlie on 2006-06-10 18:34:59