(2 votes, average: 5.00 out of 5)

## Project Euler 147: Count the number of horizontal, vertical and diagonal rectangles in a rectangular grid

#### Problem Description

In a 3×2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.

There are 5 grids smaller than 3×2, vertical and horizontal dimensions being important, i.e. 1×1, 2×1, 3×1, 1×2 and 2×2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1×1: 1
2×1: 4
3×1: 8
1×2: 4
2×2: 18

Adding those to the 37 of the 3×2 grid, a total of 72 different rectangles could be situated within 3×2 and smaller grids.

How many different rectangles could be situated within 47×43 and smaller grids?

#### Analysis

1. Count the number of horizontal and vertical rectangles in the grid.

$\frac{m(m+1)\cdot n(n+1)}{4}$

2. Count the number of diagonal rectangles in the grid. Since m ≥ n, you can safely exchange m and n if this isn’t already the case.

$\frac{n[(2m-n)(4n^2-1)-3]}{6},\:where\: m\geq n$

3. Add the two together for a total for each iteration of m and n. The sum of this series is the answer.

Example: for a 2×3 grid you have 18 horizontal and vertical rectangles and 19 diagonal rectangles for a total of 37.

#### Project Euler 147 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 147 Solution Python 2.7 source.

#### Afterthoughts

No afterthoughts yet.
Project Euler 147 Solution last updated