Project Euler

Rectangles in Cross-hatched Grids

In a cross-hatched grid (a grid with both horizontal/vertical lines and diagonal lines through each cell), rectangles can be placed either aligned with the grid axes or tilted at 45 degrees along t...

Source sync Apr 19, 2026

Problem #0147

Level Level 08

Solved By 3,562

Languages C++, Python

Answer 846910284

Length 360 words

geometrysearchbrute_force

In a $3 \times 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 \times 2$, vertical and horizontal dimensions being important, i.e. $1 \times 1$, $2 \times 1$, $3 \times 1$, $1 \times 2$ and $2 \times 2$. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:


$1 \times 1$	$1$

$2 \times 1$	$4$

$3 \times 1$	$8$

$1 \times 2$	$4$

$2 \times 2$	$18$

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

How many different rectangles could be situated within $47 \times 43$ and smaller grids?

Problem 147: Rectangles in Cross-hatched Grids

Mathematical Analysis

Axis-Aligned Rectangles

For a $w \times h$ grid, the axis-aligned rectangle count is:

A(w, h) = \binom{w+1}{2}\binom{h+1}{2} = \frac{w(w+1)}{2} \cdot \frac{h(h+1)}{2}

The total axis-aligned count is:

\sum_{w=1}^{47} \sum_{h=1}^{43} A(w, h)

Diagonal (Tilted) Rectangles

Diagonal rectangles have sides at 45 degrees. There is no known elegant closed-form formula for the number of diagonal rectangles in a $w \times h$ grid.

Algorithm: Doubled-Coordinate Enumeration

To avoid floating-point arithmetic, all coordinates are multiplied by 2. The diagonal grid creates two types of diamond-shaped unit cells:

Type 0 (parity 0): Center at integer $x$ , half-integer $y$ — in doubled coords, odd $X$ , even $Y$ .
Type 1 (parity 1): Center at half-integer $x$ , integer $y$ — in doubled coords, even $X$ , odd $Y$ .

For each cell type and each starting position $(i, j)$ within the grid:

Start at the doubled coordinates $(2i+1+p, 2j+2-p)$ where $p$ is the parity.
Scan along the lower-right direction (increasing width) by incrementing $X$ and decrementing $Y$ .
For each width step, scan along the upper-right direction (increasing height) by incrementing both $X$ and $Y$ .
Count each valid rectangle found (one whose endpoint fits within the grid boundary at $(2w, 2h)$ ).
Track the maximum valid height to prune the search.

This enumerates every diagonal rectangle exactly once, anchored at its bottom-left corner.

Total

\text{Total} = \sum_{w=1}^{47} \sum_{h=1}^{43} \left[ A(w,h) + D(w,h) \right]

where $D(w,h)$ is the diagonal rectangle count computed by the algorithm above.

Note that $D(w,h) = D(h,w)$ , so results are cached with sorted keys.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Axis-aligned: $O(1)$ per sub-grid, $O(MN)$ total.
Diagonal: $O(w \cdot h \cdot \min(w,h))$ per sub-grid in the worst case, with caching reducing repeated computations.
Total runtime: under 1 second with caching.

Answer

\boxed{846910284}

C++ project_euler/problem_147/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Count diagonal rectangles in a w x h grid.
// Uses doubled coordinates to avoid floating point.
// Two types of diagonal unit squares based on parity of center position.
// For each starting square, scan along rotated axes to enumerate all valid rectangles.
unsigned long long diagonal(int width, int height) {
    int a = width, b = height;
    if (a < b) swap(a, b);

    unsigned long long count = 0;
    for (int i = 0; i < a; i++)
        for (int j = 0; j < b; j++)
            for (int parity = 0; parity <= 1; parity++) {
                int startX = 2 * i + 1 + parity;
                int startY = 2 * j + 2 - parity;

                bool stop = false;
                int maxHeight = INT_MAX;

                for (int cw = 0; !stop; cw++) {
                    int currentX = startX + cw;
                    int currentY = startY - cw;
                    if (currentY <= 0) break;

                    for (int ch = 0; ch < maxHeight; ch++) {
                        int endX = currentX + ch;
                        int endY = currentY + ch;
                        if (endX >= 2 * a || endY >= 2 * b) {
                            if (maxHeight > ch) maxHeight = ch;
                            stop = (ch == 0);
                            break;
                        }
                        count++;
                    }
                }
            }
    return count;
}

int main() {
    int M = 47, N = 43;

    // Cache diagonal counts since diagonal(w,h) = diagonal(h,w)
    map<pair<int,int>, unsigned long long> cache;

    unsigned long long total = 0;
    for (int w = 1; w <= M; w++) {
        for (int h = 1; h <= N; h++) {
            // Axis-aligned rectangles in w x h grid
            unsigned long long axis = (unsigned long long)w * (w + 1) / 2 * h * (h + 1) / 2;

            // Diagonal rectangles (with caching)
            int a = min(w, h), b = max(w, h);
            auto key = make_pair(a, b);
            if (cache.find(key) == cache.end())
                cache[key] = diagonal(w, h);
            unsigned long long diag = cache[key];

            total += axis + diag;
        }
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_147/solution.py

"""
Problem 147: Rectangles in Cross-hatched Grids

Find the total number of rectangles (axis-aligned and diagonal) that could be
situated within cross-hatched grids of sizes w x h, for 1 <= w <= 47, 1 <= h <= 43.

The answer is the SUM over all sub-grid sizes (w, h) of the rectangle counts.
"""

def diagonal(width, height):
    """Count diagonal (tilted 45-degree) rectangles in a width x height grid.

    Uses doubled coordinates to avoid floating point.
    Two types of diagonal unit squares exist based on parity:
    - Type 0: center has integer x, half-integer y
    - Type 1: center has half-integer x, integer y
    For each starting square, scan along rotated axes to enumerate valid rectangles.
    """
    a, b = max(width, height), min(width, height)
    count = 0

    for i in range(a):
        for j in range(b):
            for parity in range(2):
                startX = 2 * i + 1 + parity
                startY = 2 * j + 2 - parity

                stop = False
                max_height = float('inf')

                cw = 0
                while not stop:
                    currentX = startX + cw
                    currentY = startY - cw
                    if currentY <= 0:
                        break

                    ch = 0
                    while ch < max_height:
                        endX = currentX + ch
                        endY = currentY + ch
                        if endX >= 2 * a or endY >= 2 * b:
                            if max_height > ch:
                                max_height = ch
                            stop = (ch == 0)
                            break
                        count += 1
                        ch += 1
                    cw += 1

    return count

def solve():
    M, N = 47, 43

    cache = {}
    total = 0

    for w in range(1, M + 1):
        for h in range(1, N + 1):
            # Axis-aligned rectangles
            axis = w * (w + 1) // 2 * (h * (h + 1) // 2)

            # Diagonal rectangles (cache with sorted key)
            key = (min(w, h), max(w, h))
            if key not in cache:
                cache[key] = diagonal(w, h)
            diag = cache[key]

            total += axis + diag

    print(total)

if __name__ == "__main__":
    solve()


\(1 \times 1\)	\(1\)

\(2 \times 1\)	\(4\)

\(3 \times 1\)	\(8\)

\(1 \times 2\)	\(4\)

\(2 \times 2\)	\(18\)