Problem 147: Rectangles in Cross-Hatched Grids

Project Euler Problem 147 Solution

EulerSolve provides an optimized solution for Project Euler Problem 147, Rectangles in Cross-Hatched Grids, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $R(a,b)$ denote the number of rectangles that can be placed in an $a \times b$ cross-hatched grid, where every unit square contains both diagonals. The implementations solve the cumulative quantity $$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$$ so for the target instance we need $S(47,43)$. The total is symmetric in the two dimensions, so the code immediately normalizes them to $N=\min(W,H)$ and $M=\max(W,H)$. The count naturally splits into two families. Ordinary axis-aligned rectangles admit a direct combinatorial sum. Slanted rectangles, whose sides lie on the diagonal hatch lines, are handled by a 45-degree change of coordinates that turns the geometry into a box-counting problem on an integer lattice. Mathematical Approach Everything below is written for $N \le M$. The crucial point is that the program is not solving a single-grid counting problem in isolation; it is summing rectangle counts over every smaller cross-hatched grid up to the target size. What the total actually counts The cumulative form matters because a rectangle that first appears in a small grid also appears in every larger grid that can contain it....

Detailed mathematical approach

Problem Summary

Let $R(a,b)$ denote the number of rectangles that can be placed in an $a \times b$ cross-hatched grid, where every unit square contains both diagonals. The implementations solve the cumulative quantity

$$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$$

so for the target instance we need $S(47,43)$. The total is symmetric in the two dimensions, so the code immediately normalizes them to $N=\min(W,H)$ and $M=\max(W,H)$.

The count naturally splits into two families. Ordinary axis-aligned rectangles admit a direct combinatorial sum. Slanted rectangles, whose sides lie on the diagonal hatch lines, are handled by a 45-degree change of coordinates that turns the geometry into a box-counting problem on an integer lattice.

Mathematical Approach

Everything below is written for $N \le M$. The crucial point is that the program is not solving a single-grid counting problem in isolation; it is summing rectangle counts over every smaller cross-hatched grid up to the target size.

What the total actually counts

The cumulative form matters because a rectangle that first appears in a small grid also appears in every larger grid that can contain it. The implementation exploits that viewpoint throughout: once it knows the smallest grid dimensions required by a rectangle, it can count all larger grids containing it in one multiplication instead of re-enumerating the rectangle for every grid size.

Axis-aligned rectangles

An ordinary $a \times b$ grid contains

$$\binom{a+1}{2}\binom{b+1}{2}$$

axis-aligned rectangles, because we choose two horizontal grid lines and two vertical grid lines. Summing over all admissible sizes gives

$$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$$

This is exactly the closed form that the implementations add to the answer before doing any geometric work on slanted rectangles.

Turning slanted rectangles into axis-aligned boxes

The slanted rectangles have sides parallel to the two diagonal directions of the hatching. The implementation parameterizes the relevant diagonal-intersection lattice by integers $0 \le i \le 2N$ and $0 \le j \le 2M$ with $i+j$ even, then applies the linear map

$$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$$

The translation by $\sigma$ only keeps the array indices positive; it does not alter the combinatorics. Under this map, the valid intersection points become the integer lattice points in the diamond-shaped region

$$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$$

In these new coordinates, every slanted rectangle in the original cross-hatched grid becomes an ordinary axis-aligned rectangle. That is the central mathematical reduction behind the code.

Detecting valid boxes with a 2D prefix sum

The implementations mark every point of $P_{N,M}$ in a padded array and build a 2D prefix sum $Q$. For a candidate box $B=[l_x,r_x]\times[l_y,r_y]$, the number of marked lattice points inside is

$$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$$

If the box lies completely inside the diamond, then every lattice point in the box is valid, so

$$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$$

This equality is the key invariant tested in the four nested loops. A candidate box contributes exactly when it is completely filled with marked points, which is equivalent to saying that the corresponding slanted rectangle is geometrically valid.

Recovering the smallest grid that can contain a slanted rectangle

Each valid transformed box corresponds to one slanted rectangle prototype. The implementation converts its extreme transformed coordinates back into the smallest ordinary grid dimensions that can contain it. If $B=[l_x,r_x]\times[l_y,r_y]$, those minimal dimensions are

$$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$$

The factor $1/2$ appears because the transformed lattice measures diagonal half-steps while the grid dimensions are counted in unit squares. Once $h_{\min}$ and $w_{\min}$ are known, the same slanted rectangle appears in every cross-hatched grid with height at least $h_{\min}$ and width at least $w_{\min}$. Therefore its multiplicity in the cumulative sum is

$$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$$

Worked example: the $3\times 2$ checkpoint

After normalization, the checkpoint case uses $N=2$ and $M=3$. The axis-aligned subtotal is

$$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$$

In the transformed plane, one of the smallest valid boxes corresponds to a slanted rectangle whose minimal container is $1\times 2$. It is therefore counted in exactly four grid sizes: $1\times 2$, $1\times 3$, $2\times 2$, and $2\times 3$. That is precisely the multiplicity

$$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$$

When all valid boxes are swept, their multiplicities sum to 32. Adding the ordinary rectangles gives

$$40+32=72,$$

which is the checkpoint value used by the C++ and Python implementations.

How the Code Works

Normalize the dimensions and add the easy part

The C++, Python, and Java implementations first reorder the dimensions so the smaller one comes first. They then add the closed-form axis-aligned subtotal $\binom{N+2}{3}\binom{M+2}{3}$ immediately.

Build the transformed lattice

Next, the implementation allocates a square integer array large enough to hold the translated diamond $P_{N,M}$. Every admissible parity-matched pair $(i,j)$ is mapped to an integer lattice point, and a 2D prefix sum is computed over that marker array.

Sweep boxes and accumulate multiplicities

The remaining work is an exhaustive scan over all axis-aligned boxes in the transformed plane. For each box, the prefix sum determines in constant time whether the box is fully inside the valid diamond. If it is, the implementation recovers the minimal containing grid dimensions $(h_{\min},w_{\min})$, discards impossible cases, and adds the multiplicity $(N-h_{\min}+1)(M-w_{\min}+1)$ to the running total.

All three languages implement the same mathematics. The C++ and Python versions also expose the small $3\times 2$ checkpoint, while the Java version directly evaluates the target instance.

Complexity Analysis

The closed-form axis-aligned part is $O(1)$. Building the transformed marker array and its prefix sums costs $O(M^2)$ time and $O(M^2)$ space, because the array side length is $2M+8$.

The dominant phase is the four-loop sweep over candidate boxes in the transformed plane, which is $O(M^4)$. For the target instance $M=47$, this is still easily practical. The overall algorithm is therefore $O(M^4)$ time and $O(M^2)$ space after normalization.

Footnotes and References

Problem page: Project Euler 147 - Rectangles in Cross-Hatched Grids
Rectangle: Wikipedia - Rectangle
Lattice point: Wikipedia - Lattice point
Prefix sum: Wikipedia - Prefix sum
Affine transformation: Wikipedia - Affine transformation
Binomial coefficient: Wikipedia - Binomial coefficient

Problem 147 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    int width = 47;
    int height = 43;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--width=", options.width) ||
            parse_int_after_prefix(arg, "--height=", options.height)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.width >= 1 && options.height >= 1;
}

i64 solve(const int width, const int height) {
    int n = std::min(width, height);
    int m = std::max(width, height);

    i64 answer = static_cast<i64>(n) * (n + 1) * (n + 2) / 6 *
                 static_cast<i64>(m) * (m + 1) * (m + 2) / 6;

    const int shift = m + 3;
    const int dim = 2 * shift + 2;
    std::vector<std::vector<int>> grid(static_cast<std::size_t>(dim), std::vector<int>(static_cast<std::size_t>(dim), 0));

    for (int i = 0; i <= 2 * n; ++i) {
        for (int j = 0; j <= 2 * m; ++j) {
            if (((i + j) & 1) != 0) {
                continue;
            }
            const int x = (i + j) / 2;
            const int y = (i + 2 * shift - j) / 2;
            grid[static_cast<std::size_t>(x + 1)][static_cast<std::size_t>(y + 1)] = 1;
        }
    }

    for (int i = 1; i < dim; ++i) {
        for (int j = 1; j < dim; ++j) {
            grid[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] +=
                grid[static_cast<std::size_t>(i - 1)][static_cast<std::size_t>(j)] +
                grid[static_cast<std::size_t>(i)][static_cast<std::size_t>(j - 1)] -
                grid[static_cast<std::size_t>(i - 1)][static_cast<std::size_t>(j - 1)];
        }
    }

    for (int lx = 1; lx < dim; ++lx) {
        for (int rx = lx + 1; rx < dim; ++rx) {
            for (int ly = 1; ly < dim; ++ly) {
                for (int ry = ly + 1; ry < dim; ++ry) {
                    const int area = (rx - lx + 1) * (ry - ly + 1);
                    const int full = grid[static_cast<std::size_t>(rx)][static_cast<std::size_t>(ry)] -
                                     grid[static_cast<std::size_t>(rx)][static_cast<std::size_t>(ly - 1)] -
                                     grid[static_cast<std::size_t>(lx - 1)][static_cast<std::size_t>(ry)] +
                                     grid[static_cast<std::size_t>(lx - 1)][static_cast<std::size_t>(ly - 1)];
                    if (full != area) {
                        continue;
                    }

                    const int mi = (rx + ry - shift - 1) / 2;
                    const int mj = (rx - ly + shift + 1) / 2;
                    if (mi < 1 || mj < 1 || mi > n || mj > m) {
                        continue;
                    }
                    answer += static_cast<i64>(n - mi + 1) * (m - mj + 1);
                }
            }
        }
    }

    return answer;
}

bool run_checkpoints() {
    if (solve(3, 2) != 72LL) {
        std::cerr << "Checkpoint failed for 3x2" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.width, options.height) << '\n';
    return 0;
}

Python

import sys

def solve(width, height):
    n = min(width, height)
    m = max(width, height)

    answer = (n * (n + 1) * (n + 2) // 6) * (m * (m + 1) * (m + 2) // 6)

    shift = m + 3
    dim = 2 * shift + 2
    grid = [[0] * dim for _ in range(dim)]

    for i in range(2 * n + 1):
        for j in range(2 * m + 1):
            if ((i + j) & 1) != 0:
                continue
            x = (i + j) // 2
            y = (i + 2 * shift - j) // 2
            grid[x + 1][y + 1] = 1

    for i in range(1, dim):
        for j in range(1, dim):
            grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]

    for lx in range(1, dim):
        for rx in range(lx + 1, dim):
            for ly in range(1, dim):
                for ry in range(ly + 1, dim):
                    area = (rx - lx + 1) * (ry - ly + 1)
                    full = grid[rx][ry] - grid[rx][ly - 1] - grid[lx - 1][ry] + grid[lx - 1][ly - 1]
                    if full != area:
                        continue

                    mi = (rx + ry - shift - 1) // 2
                    mj = (rx - ly + shift + 1) // 2
                    if mi < 1 or mj < 1 or mi > n or mj > m:
                        continue
                    answer += (n - mi + 1) * (m - mj + 1)

    return answer

def run_checkpoints():
    if solve(3, 2) != 72:
        return False
    return True

def parse_arguments(args):
    options = {
        'width': 47,
        'height': 43,
        'run_checkpoints': True
    }
    
    i = 1
    while i < len(args):
        arg = args[i]
        if arg == '--skip-checkpoints':
            options['run_checkpoints'] = False
            i += 1
            continue
        
        if arg.startswith('--width='):
            try:
                value = int(arg[8:])
                options['width'] = value
                i += 1
                continue
            except ValueError:
                return None, "Invalid width value"
        
        if arg.startswith('--height='):
            try:
                value = int(arg[9:])
                options['height'] = value
                i += 1
                continue
            except ValueError:
                return None, "Invalid height value"
        
        return None, f"Unknown argument: {arg}"
    
    if options['width'] < 1 or options['height'] < 1:
        return None, "Width and height must be at least 1"
    
    return options, None

def main():
    args = sys.argv[1:]
    options, error = parse_arguments(args)
    
    if error:
        print(error, file=sys.stderr)
        sys.exit(1)
    
    if options['run_checkpoints'] and not run_checkpoints():
        print("Checkpoint failed for 3x2", file=sys.stderr)
        sys.exit(2)
    
    print(solve(options['width'], options['height']))

if __name__ == '__main__':
    main()

Java

public class Euler147 {
    static long solve(int width, int height) {
        int n = Math.min(width, height), m = Math.max(width, height);
        long answer = (long) (n * (n + 1) * (n + 2) / 6) * (long) (m * (m + 1) * (m + 2) / 6);
        int shift = m + 3, dim = 2 * shift + 2;
        int[][] grid = new int[dim][dim];
        for (int i = 0; i <= 2 * n; i++)
            for (int j = 0; j <= 2 * m; j++) {
                if (((i + j) & 1) != 0)
                    continue;
                int x = (i + j) / 2, y = (i + 2 * shift - j) / 2;
                grid[x + 1][y + 1] = 1;
            }
        for (int i = 1; i < dim; i++)
            for (int j = 1; j < dim; j++)
                grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
        for (int lx = 1; lx < dim; lx++)
            for (int rx = lx + 1; rx < dim; rx++)
                for (int ly = 1; ly < dim; ly++)
                    for (int ry = ly + 1; ry < dim; ry++) {
                        int area = (rx - lx + 1) * (ry - ly + 1);
                        int full = grid[rx][ry] - grid[rx][ly - 1] - grid[lx - 1][ry] + grid[lx - 1][ly - 1];
                        if (full != area)
                            continue;
                        int mi = (rx + ry - shift - 1) / 2, mj = (rx - ly + shift + 1) / 2;
                        if (mi < 1 || mj < 1 || mi > n || mj > m)
                            continue;
                        answer += (long) (n - mi + 1) * (m - mj + 1);
                    }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solve(47, 43));
    }
}