Tentando encontrar uma fórmula para tesellating retângulos em uma prancha, onde o quadrado do meio não pode ser usado

Question

Estou trabalhando em um problema de empilhamento espacial ... no momento estou tentando resolver em 2D, mas acabará por fazer esse trabalho em 3D.

Eu divido o espaço em quadrados NXN em torno de um bloco central, portanto n é sempre estranho ... e estou tentando encontrar o número de locais que um retângulo de qualquer dimensão menor que NXN (por exemplo, 1x1, 1x2, 2x2 etc) pode ser colocado, onde o quadrado do meio não está disponível.

Até agora eu tenho isso ..

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

.. também o número total de quadrados = (n (n+1) (2n+1)) / 6

No entanto, estou preso ao elaborar uma fórmula para descobrir quantos desses locais são impossíveis, pois a praça do meio seria ocupada.

Por exemplo:

[] [] []

] [x] [

[] [] []

3 x 3 placa ... com 8 locais possíveis para armazenar coisas como o quadrado médio está em uso. Eu posso usar formas 1x1, formas 1x2, 2x1, 3x1, etc ...

A fórmula me dá o número de retângulos como: (9+3)^2/4 = 144/4 = 36 Locais de empilhamento No entanto, como o quadrado do meio é desocupável, eles nem todos podem ser realizados.

À mão, posso ver que essas são opções impossíveis:

1x1 formas = 1 impossível (quadrado médio) 2x1 formas = 4 impossível (qualquer coisa que use o quadrado médio) 3x1 = 2 impossível 2x2 = 4 impossível etc.

Portanto, a solução que estou depois é 36-16 = 20 possíveis locais de empilhamento retangular em uma placa 3x3.

Codifiquei isso em C# para resolvê -lo por tentativa e erro, mas estou realmente depois de uma fórmula, pois quero resolver valores maciços de n e também para fazer esse 3D.

Alguém pode me indicar alguma fórmula para esse tipo de problema espacial / de tesellation? Além disso, qualquer idéia sobre como levar a fórmula de retângulo total para 3D muito bem -vinda!

Obrigado!

Answer 1

Ok .. então eu tenho uma resposta agora que é .. os casos totais impossíveis são definidos por:

n^4 onde n é a ordem do tamanho da grade usando apenas grades ímpares

2^4 = 16 (grade é 3 por 3) 3^4 = 81 (grade é 5 por 5) 4^4 = 256 (a grade é 7 por 7) etc.