Dividing a field into smaller squares | Mathematics | Page 1

long shard Dec 10, 2022, 4:39 PM

#

Hello Everyone,

First of all, english is not my main language, so apologies :P

So, I've been facing the following problem:

Imagine I had a field of size nxm and want to see how many different ways I can divide it in various smaller squares (that can have different sizes). I got to find an algorithm to solve this problem and code it :).

In a 3x4 field, there are 13 possible combinations, as in the picture. (assuming all white squares are 1x1).

I've found a way to solve this by using brute force, but it is way too inefficient (taking almost 8 minutes to calculate an 8x8 field, since it corresponds to possibilities 35.863.972 :D ). So I've been trying to find a mathematical algorithm to solve this, but I've been stuck for quite a while. I was wondering if anyone has any tip or knows a way to solve the problem without testing every single possibility.

I hope you all have a great day!
Thank you!

slow blade Dec 10, 2022, 4:43 PM

#

long shard Hello Everyone, First of all, english is not my main language, so apologies :P...

here's a thought

#

wait nvm

long shard Dec 10, 2022, 4:45 PM

#

shdfhsa

#

dw :P

slow blade Dec 10, 2022, 4:47 PM

#

#

here's what I got

#

haven't checked it

#

essentially just iterate over each square size, the number of squares of that size you can fit

#

rafian here to correct me again

pallid kestrel Dec 10, 2022, 4:48 PM

#

This counts the number of ways to select one square

slow blade Dec 10, 2022, 4:48 PM

#

pallid kestrel Dec 10, 2022, 4:49 PM

#

while Belchior wants the number of ways to assign potentially multiple non 1x1 squares

slow blade Dec 10, 2022, 4:50 PM

#

yes, that's what this is

#

S is square size

#

so for a 1x1 square, there are MxN possible assignments

#

for a 2x2 there are (M-1)x(N-1)

#

and it continues until it runs out of room

pallid kestrel Dec 10, 2022, 4:53 PM

#

According to the formula you gave (which admittedly was my first thought as well), the 3x4 rectangle grid Belchior showed should yield 12+6+2 = 20 possible assignments

#

Yet those 13 configurations Belchior showed do look convincingly exhaustive

#

There is a disconnect between the formula and the quantity Belchior seeks

slow blade Dec 10, 2022, 4:54 PM

#

I think I misunderstood then

#

I do have an idea that might work and is better than brute forcing

long shard Dec 10, 2022, 4:56 PM

#

slow blade

That was also my first thought, but it's not exactly what I need

slow blade Dec 10, 2022, 4:56 PM

#

so you just want the # of ways to divide the space into squares? are you counting even configurations where not all the space is accounted for?

long shard Dec 10, 2022, 4:56 PM

#

pallid kestrel while Belchior wants the number of ways to assign potentially multiple non 1x1 s...

Exactly

pallid kestrel Dec 10, 2022, 4:57 PM

#

slow blade so you just want the # of ways to divide the space into squares? are you countin...

They are still accounted for, by 1x1 squares

slow blade Dec 10, 2022, 4:57 PM

#

pallid kestrel They are still accounted for, by 1x1 squares

nah, not combinatorially the same

long shard Dec 10, 2022, 4:57 PM

#

pallid kestrel They are still accounted for, by 1x1 squares

yeah

pallid kestrel Dec 10, 2022, 4:58 PM

#

Nonetheless I think we are on the same page

long shard Dec 10, 2022, 5:04 PM

#

I've tried doing the following:
Tried to go through each one of the rows, from bottom to top. Trying to calculate the combination of 2x2 Squares, 3x3 squares ... that could "start" on said row.
Repeating it to the "possible" rows above (for example, if I tried with 2x2 squares on the last row, I'd only repeat this on the second to last row) and analyse everything.
The problem is that this would exclude possibilities like the 6th and the 9th on the picture

slow blade Dec 10, 2022, 5:04 PM

#

I'm wondering if a tree based algorithm could do the job

#

I don't think it would work

long shard Dec 10, 2022, 5:06 PM

#

and how would I do that

#

I mean

#

where should I split the tree

slow blade Dec 10, 2022, 5:06 PM

#

yeah, that's the issue

#

you need something more general, which is just equivalent to recursion at that point

long shard Dec 10, 2022, 5:08 PM

#

yeah

#

that has been my problem

#

I cannot find a way to divide this

#

without making it like brute force

#

because I basically calculate the same things multiple times

slow blade Dec 10, 2022, 5:11 PM

#

I mean other than splitting your space into equivalence classes (perhaps by some sort of hashing) and recording the number of square divisons on each class, I can't think of anything

#

even then though

#

caching would give you a quite significant speedup

long shard Dec 10, 2022, 5:22 PM

#

Yeah, tbf caching would drastically improve the performance of the algorithm

#

but I'm not sure

slow blade Dec 10, 2022, 5:22 PM

#

I have an idea of a hashing algorithm that guarantees equivalence of spaces if you need one

long shard Dec 10, 2022, 5:23 PM

#

long shard but I'm not sure

what could I cache

#

?

slow blade Dec 10, 2022, 5:23 PM

#

long shard what could I cache

wdym

#

you'd cache the result of the algorithm on the space

#

so the number of placements

long shard Dec 10, 2022, 5:24 PM

#

slow blade I have an idea of a hashing algorithm that guarantees equivalence of spaces if y...

Sure, I'd really appreciate if you could :D

long shard Dec 10, 2022, 5:24 PM

#

slow blade you'd cache the result of the algorithm on the space

OMG

#

that makes sense!!!!!!

#

let me try

slow blade Dec 10, 2022, 5:26 PM

#

yeah, it's pretty simple. just have the top row (that has open squares) be the largest (in terms of squares that are still open), left column be the second largest, right column (farthest right column that still has open squares) be the third largest, and bottom row (lowest row with open squares) be the fourth largest

#

so rotate it/reflect it so that it's true

#

then hash over the entire "span" of the space using your favorite hashing algorithm

long shard Dec 10, 2022, 5:35 PM

#

I think it might work

#

Atleast now I know what I should try :P

#

but thank you! I'm really grateful

#

Now I'm going to try implementing it

slow blade Dec 10, 2022, 5:38 PM

#

yeah, no idea what your time complexity will look like

#Dividing a field into smaller squares