Attempting to find a formula for tessellating rectangles onto a board, where middle square can't be used

I'm working on a spatial stacking problem... at the moment I'm trying to solve in 2D but will eventually have to make this work in 3D.

I divide up space into n x n squares around a central block, therefore n is always odd... and I'm trying to find the number of locations that a rectangle of any dimension less than n x n (eg 1x1, 1x2, 2x2 etc) can be placed, where the middle square is not available.

So far I've got this..

total number of rectangles = ((n^2 + n)^2 ) / 4

..also the total number of squares = (n (n+1) (2n+1)) / 6

However I'm stuck in working out a formula to find how many of those locations are impossible as the middle square would be occupied.

So for example:

[] [] []

[] [x] []

[] [] []

3 x 3 board... with 8 possible locations for storing stuff as mid square is in use. I can use 1x1 shapes, 1x2 shapes, 2x1, 3x1, etc...

Formula gives me the number of rectangles as: (9+3)^2 / 4 = 144/4 = 36 stacking locations However as the middle square is unoccupiable these can not all be realized.

By hand I can see that these are impossible options:

1x1 shapes = 1 impossible (mid square) 2x1 shapes = 4 impossible (anything which uses mid square) 3x1 = 2 impossible 2x2 = 4 impossible etc Total impossible combinations = 16

Therefore the solution I'm after is 36-16 = 20 possible rectangular stacking locations on a 3x3 board.

I've coded this in C# to solve it through trial and error, but I'm really after a formula as I want to solve for massive values of n, and also to eventually make this 3D.

Can anyone point me to any formulas for th开发者_高级运维ese kind of spatial / tessellation problem? Also any idea on how to take the total rectangle formula into 3D very welcome!

Thanks!

Ok.. so I've got an answer now which is.. the total impossible cases is defined by:

n^4 where n is the order of grid size using only odd grids

2^4 = 16 (grid is 3 by 3) 3^4= 81 (grid is 5 by 5) 4^4 = 256 (grid is 7 by 7) etc