Databases
StackOverflow2013
Postsdbo
POAttempting to find a formula for tessellating rectangles onto a board, where middle square can't be used
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAttempting to find a formula for tessellating rectangles onto a board, where middle square can't be used
    text
    copied!<p>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.</p> <p>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.</p> <p>So far I've got this..</p> <pre><code>total number of rectangles = ((n^2 + n)^2 ) / 4 </code></pre> <p>..also the total number of squares = (n (n+1) (2n+1)) / 6 </p> <p>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.</p> <p>So for example:</p> <p>[] [] []</p> <p>[] [x] []</p> <p>[] [] []</p> <p>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...</p> <p>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.</p> <p>By hand I can see that these are impossible options:</p> <p>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</p> <p>Therefore the solution I'm after is 36-16 = 20 possible rectangular stacking locations on a 3x3 board.</p> <p>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.</p> <p>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!</p> <p>Thanks!</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload