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 these kind of spatial / tessellation problem? Also any idea on how to take the total rectangle formula into 3D very welcome!
Thanks!