Размещение здания в дискретной 2D-игре

Я работаю в сетке-вселенной - объекты существуют только в целочисленных точках в двумерной матрице.

Некоторые термины:

Квадрат - дискретное расположение. Каждый квадрат имеет координаты int x и int y, и никакие два квадрата не имеют одинаковой пары x и y.

Смежный: квадрат X соседствует с другим квадратом Y, если величина разницы в их координатах x или y не больше 1. Проще говоря, все квадраты в направлениях N, NE, E, SE, S, SW, W и NW являются смежными.

Legend:
'?' - Unknown Traversibility
'X' - Non Traversable Square
'O' - Building (Non Traversable)
' ' - Traversable Square

Проблема:

Учитывая следующую общую ситуацию:

? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? O O ? ? ?
? ? ? O O ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

, когда строитель находится рядом с одним из четырех зданий, я хочу построить два здания так, чтобы они оба имели общий смежный квадрат, который также примыкает к по крайней мере одно из четырех существующих зданий, и эта общая смежная площадь не заблокирована.

Основные Допустимые решения:

X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X O O X X X          X X X O O X X X          X X X O O X X X
X X X O O X X X          X X X O O X X X          X X O O O X X X
                         X X X O   X X X                O X X X X
      O O                X X X O   X X X                X X X X X
                         X X X     X X X                X X X X X 

В настоящее время я перебираю все проходимые квадраты, прилегающие к четырем зданиям, и ищу квадраты, в которых есть 3 смежные проходимые квадраты, но иногда возникают такие ситуации, как:

X X X X X X X X          X X X X X X X X          X X X X X X X X
X X X X X X X X          X X X X X X X X          X X X X X   X X
X X X X X X X X          X X   O     X X          X     X X   O X
X X X O O X X X          X X   O O O X X          X     O O O X X
X X X O O X X X          X X   O O   X X          X X   O O   X X
X X X     X X X          X X         X X          X X         X X
X X X O O X X X          X X X     X X X          X X X     X X X
X X X     X X X          X X X     X X X          X X X     X X X 

Есть мысли о том, как я могу улучшить свой алгоритм?

РЕДАКТИРОВАТЬ: Добавлен еще один неудачный случай.

РЕДАКТИРОВАТЬ: Я бы также хотелось бы знать, нет ли возможной конфигурации, в которой могут быть выполнены эти условия. Мне не гарантировано жизнеспособное решение, и хотел бы не пытаться, если нет способа сделать это успешно.