Попытка найти формулу для мозаики прямоугольников на доске, где средний квадрат не может быть использован

Question

Я работаю над проблемой пространственного укладки...на данный момент я пытаюсь решить проблему в 2D, но в конечном итоге мне придется заставить это работать в 3D.

Я делю пространство на n x n квадратов вокруг центрального блока, поэтому n всегда нечетно...и я пытаюсь найти количество мест, в которых может быть размещен прямоугольник любого размера, меньшего n x n (например, 1x1, 1x2, 2x2 и т.д.), где средний квадрат недоступен.

Пока у меня есть это..

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

..также общее количество квадратов = (n (n+ 1) (2n+ 1)) / 6

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

Так, например:

[] [] []

[] [x] []

[] [] []

доска 3 х 3...с 8 возможными местами для хранения вещей, так как используется mid square.Я могу использовать фигуры 1x1, 1x2, 2x1, 3x1 и т.д...

Формула дает мне количество прямоугольников в виде:(9+3)^2 / 4 = 144/4 = 36 места укладки Однако, поскольку средний квадрат не занят, не все они могут быть реализованы.

Вручную я вижу, что это невозможные варианты:

фигуры 1x1 = 1 невозможная (средний квадрат) фигуры 2x1 = 4 невозможных (все, что использует средний квадрат) 3x1 = 2 невозможных 2x2 = 4 невозможных и т.д. Всего невозможных комбинаций = 16

Следовательно, решение, которое я ищу, - это 36-16 = 20 возможных прямоугольных мест укладки на доске 3x3.

Я закодировал это на C #, чтобы решить методом проб и ошибок, но на самом деле мне нужна формула, поскольку я хочу решить для больших значений n, а также в конечном итоге сделать это 3D.

Кто-нибудь может указать мне на какие-либо формулы для такого рода задач пространственной тесселяции?Также любая идея о том, как перевести общую формулу прямоугольника в 3D, очень приветствуется!

Спасибо!

Answer 1

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

n ^ 4 где n - порядок размера сетки с использованием только нечетных сеток

2 ^ 4 = 16 (сетка 3 на 3) 3 ^ 4 = 81 (сетка 5 на 5) 4 ^ 4 = 256 (сетка 7 на 7) и т.д.