A075855 Maximum number of black squares on an n X n chessboard (with a black square in at least one corner) that can be covered by a single path, traveling only to adjacent black squares.

1, 2, 3, 7, 9, 16, 19, 29, 33

Offset

1,2

Links

Table of n, a(n) for n=1..9.

Formula

For n odd, a(n)=(n-1)^2/2+1. For n even, it is conjectured that a(n)=(n^2-n+2)/2 (it is easy to show this is a lower bound).

Empirical G.f.: x*(1+x-x^2+2*x^3+x^4)/((1-x)^3*(1+x)^2). [Colin Barker, Apr 12 2012]

Example

For n=4, here is a path with 7 squares; the "x" is not visited:
1.3.
.2.4
7.5.
.6.x

Crossrefs

Sequence in context: A109660 A236544 A343198 * A347268 A360251 A140189

Adjacent sequences: A075852 A075853 A075854 * A075856 A075857 A075858

Keyword

nonn

Author

Jon Perry, Oct 15 2002

Extensions

Edited by Dean Hickerson, Oct 25 2002

Status

approved