Question

Given a rectangular MxN array of square cells, how many square "subgrids" can you create?

say this is my grid:
\[#
[1][1]
[1][1]\]

I can make 4 unicellular square grids, or 1 multicellular square grid comprising those 4 baby grids.

Answer 1

\[#
[1][1][1]
[1][1][1]\]

For the above 2x3 grid (2 rows, 3 cols) I can create 6 baby grids, and 2 big square grids

Answer 2

if you can give me a program that computes the answer, then that's alright too:

here's what I came up with and it isn't working:
\[#
def is_square_grid(Grid):
return Grid.rows == Grid.cols

def computepossiblesquares(Grid):
squares = []
for left in xrange(Grid.cols):
for right in xrange(1, Grid.cols):
for top in xrange(Grid.rows):
for bottom in xrange(1, Grid.rows):
possiblesquare = Grid.slicegrid(left, right, top, bottom)
if (possiblesquare.is_square()):
squares.append(possiblesquare)\]

Answer 3

so is slicing the grid according to every possible combination of slices not the way to go? :(

Answer 4

It is the way to go... but I'm doing it wrong!...

Luckily I just remembered we took something about this in the Stanford public Machine Learning class. Time to improve my code!

Answer 5

My Python implementation of the Grid object sucks! I should have just wrapped numpy's Array objects...

Answer 6

You should figure out how to do this without writing a computer program.

Answer 7

I'm sure there's an elegant way to compute it using factorials

Answer 8

I think there are M*N + fact(min(M,N)) squares

Answer 9

or am I mistaken?

Answer 10

For example....
without loss of generality, let M be less than or equal to N.

How many 1x1 grids are there? MN

How many 2x2 grids are there? ...

and so on up to

MxM grids: N-M

Then add then up.

Answer 11

\[# M=1, N=5
[1][1][1][1][1]
\]
The number of 1x1 grids up there is M*N = 5

5 total square grids

\[# M=2, N=5
[1][1][1][1][1]
[1][1][1][1][1]
\]
The number of 1x1 grids up there is 10
The number of 2x2 grids up there is 4

18 total square grids

\[# M = 3, N = 5
[1][1][1][1][1]
[1][1][1][1][1]
[1][1][1][1][1]\]
The number of 1x1 grids up there is M*N = 15
The number of 2x2 grids up there is 8
The number of 3x3 grids up there is 3


I'm beginning to see a pattern up there.

Answer 12

oh and 3x5 grid up there has 26 total square grids

Answer 13

We can also sum the squares and get a closed form solution in terms of m,n | m<n:
\[\ f(m,n)=sum_{i=1}^{m} \ (m+1-i)(n+1-i) = \frac{m(m+1)(2n+1-m)}{6}\]
and we see that
f(1,1)=1
f(1,2)=2
f(1,3)=3
f(2,3)=8
f(3,4)=20
f(3,5)=26
...

Answer 14

Sorry, the summation should read:
\[\sum_{i=1}^m (m+1-i)(n+1-i)\]

Answer 15

I finally got it now thanks to you!

Answer 16

I''ve got another problem about grids though