Hmm … "best way" is ever a fruitless question, because what is the measure for "best"?

Let a tile index be [x ; y]. Let the tiles covered by building n be from [x_{l,n }; y_{b,n}] to [ x_{r,n}; y_{t,n} ], e.g. read it as from left / bottom corner to right / up corner. Then the separate distances between 2 buildings 1 and 2 for the both dimensions are

d_{x} = min( | x_{l,1} - x_{r,2} | , | x_{r,1} - x_{l,2} | )

d_{y} = min( | y_{b,1} - y_{t,2} | , | y_{t,1} - y_{b,2} | )

Both of the separate distances need to be 1 for directly adjacent buildings. A value of 2 means that 1 free tile is in-between them. Hence, if no more than 2 free tiles is allowed, both separate distances must be less than 4. (Notice that you may need to use a slightly more complex condition if diagonal distances need to be considered.)

Above solution requires AFAIS that the building do not overlap, or else false positives may occur if one building is really big compared to the other, so checking whether the tiles under the placeable building are free should be done already simply by checking each tile in [x_{l,2 }; y_{b,2}] to [ x_{r,2}; y_{t,2} ] for coverage.

You can restrict the search over all already placed buildings (if needed) by e.g. using a spatial partitioning scheme.

**Edited by haegarr, 13 February 2014 - 08:39 AM.**