I need to find out the number of squares in $N\times M$ grid.
I came across this formula
$$S = \frac{1}{6}N(N+1)(3M-N+1)$$
But in my case the squares do not necessarily need to be aligned with the axes of the grid. How do I calculate the number in that case?
Let's have R rows and C columns of dots. We'll assume C >= R.
First count all the squares that are aligned with the axes:
number of 1x1 squares is (R-1)*(C-1)
number of 2x2 squares is (R-2)*(C-2)
... until we get to R-R (we assumed R was smaller).
Now count all the squares not aligned with the axes:
(this squares will be tilted around an inner point or a smaller square)
number of 1x1 squares is the number of inner points => (R-2)*(C-2), each one can be rotated in place in only one way.
2x2 squares = inner 1x1 squares => (R-3)*(C-3), each rotated in 2 ways
3x3 squares = inner 2x2 squares => (R-4)*(C-4), each rotated in 3 ways
... until we get to R-R
Writing the sum of both: $$\sum_{i=1}^{R} i(R-i)(C-i)$$
which equals: $\sum_{i=1}^{R} RCi - Ri^2 - Ci^2 + i^3$
= RC$\sum_{i=1}^{R}i$ - (R+C)$\sum_{i=1}^{R}i^{2}$ + $\sum_{i=1}^{R}i^{3}$
= $RC\frac{1}{2} R(R+1) - (R+C)\frac{1}{6}R(R+1)(2R+1) + \frac{1}{4}R^{2}(R+1)^{2}$
= $\frac{1}{12}(R-1)R(R+1)(2C-R)$
This formula solves the Google Kickstart problem of Square Counting.