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 May 21, 2026

Problem #0147

Level Level 08

Solved By 3,562

Languages C++, Python

Answer 846910284

Length 449 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 Development

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.

Editorial

The total is accumulated over every sub-grid size, so for each pair $(w,h)$ the program needs the rectangle count in a single cross-hatched grid and then adds it to the grand sum. The axis-aligned part is immediate from the standard rectangle formula, so the only real work is counting tilted rectangles.

The implementation handles tilted rectangles by switching to doubled coordinates. In that model every 45-degree rectangle has integer endpoints, and the two possible parities of the starting cell correspond to the two families of diamond-shaped unit cells created by the cross-hatching. For each possible anchor and parity, the code extends one side along a descending diagonal and the other side along an ascending diagonal, counting every rectangle that stays inside the current grid. Because the tilted count is symmetric in $(w,h)$ , it is cached with a sorted key and reused whenever the transposed grid appears later in the outer summation.

Pseudocode

Initialize the total answer to zero and create a cache for tilted counts.

For every sub-grid width $w$ from 1 to 47:
    For every sub-grid height $h$ from 1 to 43:
        Add the axis-aligned rectangle count
        $$
        \binom{w+1}{2}\binom{h+1}{2}.
        $$

        If the tilted count for the unordered pair $(w,h)$ is not cached yet:
            Enumerate every possible anchor cell and both parity classes.
            From each anchor, extend the lower side along one diagonal direction.
            For each such width, extend the opposite side along the perpendicular diagonal direction
            while the far corner remains inside the doubled-coordinate boundary.
            Count every valid placement exactly once and store the result in the cache.

        Add the cached tilted count for this sub-grid.

Return the accumulated total.

Complexity Analysis

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\)