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

A grid of $a\times b$ unit squares, $a$ squares wide and $b$ high, is cross-hatched: besides its horizontal and vertical grid lines, both diagonals of every unit square are drawn. A rectangle is situated within the grid when each of its four sides runs along drawn lines; let $R(a,b)$ be the number of these rectangles. The statement gives $R(3,2)=37$ and the values for the five smaller grids, in which width and height are told apart: $R(1,1)=1$, $R(2,1)=4$, $R(3,1)=8$, $R(1,2)=4$ and $R(2,2)=18$, so that the $3\times2$ grid and the smaller grids together contain $72$ rectangles. We must find the same total for the $47\times43$ grid and all smaller grids, that is, ^[1]

$$S(A,B)=\sum_{a=1}^{A}\sum_{b=1}^{B}R(a,b)$$

for $A=47$ and $B=43$.

The whole solution in one sentence: upright rectangles are counted by choosing two vertical and two horizontal grid lines, and after a turn of the plane by $45^\circ$ the slanted rectangles become ordinary boxes on an integer lattice, so the program lists the slanted rectangles of the largest grid as boxes and counts each one once for every smaller grid, placed in the same corner, that still contains it.

Mathematical Approach

1. The drawing and its crossing points

Place the $a\times b$ grid with its lower left corner at the origin, so that it fills the region $0\le x\le a$, $0\le y\le b$. The two diagonals of the unit square $[i,i+1]\times[j,j+1]$ lie on the lines $x-y=i-j$ and $x+y=i+j+1$, so every drawn diagonal lies on a line $x+y=c$ or $x-y=c$ with an integer $c$. Conversely, such a line meets the border of the grid only at points with integer coordinates, and its points with integer coordinates cut its part inside the grid into diagonals of unit squares, so this whole part is drawn. Two drawn lines meet either at a corner, a point with integer coordinates, or at the centre of a unit square, where its diagonals cross; the vertices of every rectangle are such points.

2. Upright and slanted rectangles

Neighbouring sides of a rectangle are perpendicular, and a horizontal or vertical line makes an angle of $45^\circ$ with both diagonal directions. So either all four sides are horizontal and vertical, an upright rectangle, or all four run along the diagonal directions, a slanted rectangle; we write $R(a,b)=U(a,b)+D(a,b)$ for the two counts. The smallest grids can be checked by hand:

$1\times1$: the square itself is the only rectangle, so $R(1,1)=1$.
$2\times1$: three upright rectangles and one slanted square, the small diamond around the middle edge, with the ends $(1,0)$ and $(1,1)$ of that edge and the centres $(\tfrac12,\tfrac12)$ and $(\tfrac32,\tfrac12)$ as vertices and four half-diagonals as sides. So $R(2,1)=4$.
$2\times2$: nine upright and nine slanted rectangles: four small diamonds, one around each inner unit edge; the large diamond with vertices $(0,1)$, $(1,2)$, $(2,1)$, $(1,0)$; and four rectangles with one side of half a diagonal and one of a whole diagonal, such as the one with vertices $(0,1)$, $(\tfrac12,\tfrac32)$, $(\tfrac32,\tfrac12)$, $(1,0)$. So $R(2,2)=18$.

3. Upright rectangles

An upright rectangle is fixed by two of the $a+1$ vertical grid lines and two of the $b+1$ horizontal ones. The number of ways to choose $2$ of $n$ objects is the binomial coefficient $\binom n2=n(n-1)/2$, ^[2] so

$$U(a,b)=\binom{a+1}{2}\binom{b+1}{2};$$

for example $U(2,2)=3\cdot3=9$ and $U(3,2)=6\cdot3=18$. Summed over all grids up to $A\times B$, the double sum is the product of two single sums, and each of them is a case of the hockey-stick identity ^[3]

$$\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}.$$

With $r=2$ and $n=A+1$ it gives $\sum_{a=1}^{A}\binom{a+1}{2}$${}=\binom{A+2}{3}$, hence

$$\sum_{a=1}^{A}\sum_{b=1}^{B}U(a,b)=\binom{A+2}{3}\binom{B+2}{3}$$

The identity follows from Pascal's rule $\binom{k+2}{3}-\binom{k+1}{3}=\binom{k+1}{2}$, which makes the sum telescope. For the $3\times2$ checkpoint the upright part is $\binom53\binom43=10\cdot4=40$, so the slanted rectangles of the six grids contribute $72-40=32$. Indeed, subtracting the upright counts from the values of the statement gives $D(1,1)=0$, $D(2,1)=1$, $D(3,1)=2$, $D(1,2)=1$, $D(2,2)=9$ and $D(3,2)=19$, with sum $32$.

4. Turning the plane by 45 degrees

The diagonal lines become ordinary grid lines in the coordinates

$$\begin{aligned}u&=x+y,&\quad v&=x-y,\\x&=\frac{u+v}{2},&\quad y&=\frac{u-v}{2},\end{aligned}$$

since by Section 1 the drawn diagonals lie on the lines $u=c$ and $v=c$ with integer $c$. Up to the factor $\sqrt2$, these are the coordinates along the two diagonal directions: rotating the axes by $45^\circ$ gives $x'=(x+y)/\sqrt2$ and $y'=(y-x)/\sqrt2$, so $u=\sqrt2\,x'$ and $v=-\sqrt2\,y'$. ^[4] Every crossing point has integer $u$ and $v$, and every integer pair $(u,v)$ inside the grid is a crossing point: a corner when $u+v$ is even and a centre when $u+v$ is odd, since then $x$ and $y$ are both halves of odd numbers. For example, the corner $(1,0)$ has $(u,v)=(1,1)$, and the centre $(\tfrac12,\tfrac12)$ has $(u,v)=(1,0)$. The grid itself becomes the turned rectangle

$$0\le u+v\le2a,\quad 0\le u-v\le2b.$$

5. Slanted rectangles are boxes

A slanted rectangle has two sides on lines $u=u_1$ and $u=u_2$ and two on lines $v=v_1$ and $v=v_2$, with integers $u_1\lt u_2$ and $v_1\lt v_2$: in the $(u,v)$-plane it is the box $[u_1,u_2]\times[v_1,v_2]$. Its sides are drawn exactly when the box lies inside the grid, because there the four lines are drawn completely. Since $x=(u+v)/2$ grows with $u$ and with $v$, the smallest $x$ of the box is at its corner $(u_1,v_1)$ and the largest at $(u_2,v_2)$; since $y=(u-v)/2$ grows with $u$ and falls with $v$, the smallest $y$ is at $(u_1,v_2)$ and the largest at $(u_2,v_1)$. So the box lies inside the grid exactly when these four corners, the leftmost, rightmost, lowest and highest vertex of the rectangle, do:

$$\begin{aligned}u_1+v_1&\ge0,&\quad u_2+v_2&\le2a,\\u_1-v_2&\ge0,&\quad u_2-v_1&\le2b.\end{aligned}$$

For example, the small diamond of the $2\times1$ grid is the box $[1,2]\times[0,1]$, and indeed $1+0\ge0$, $2+1\le4$, $1-1\ge0$ and $2-0\le2$.

6. Shapes and positions

Call $(p,q)$, with $p=u_2-u_1$ and $q=v_2-v_1$, the shape of a slanted rectangle: its sides consist of $p$ and of $q$ half-diagonals. By Section 5 its $x$-values and its $y$-values both fill intervals of length $(p+q)/2$, so the rectangle sits in a bounding square of side $(p+q)/2$ with lower left corner $(x_0,y_0)$. Its leftmost vertex is $(x_0,y_0+q/2)$, and the other vertices follow from it by half-diagonal steps, each leading from a corner to a centre or back. So the shape fits at $(x_0,y_0)$ exactly when $2x_0$ and $2y_0$ are integers with

$$\begin{aligned}0&\le2x_0\le2a-p-q,\\0&\le2y_0\le2b-p-q\end{aligned}$$

and $2x_0-2y_0-q$ is even, which makes the leftmost vertex a corner or a centre. Counting these positions only needs the numbers of even and odd values in each range, $\lfloor t/2\rfloor+1$ and $\lfloor(t+1)/2\rfloor$ among $0,1,\dots,t$, so each shape costs constant time. The smallest shape $(1,1)$ is the small diamond: one of its diagonals is a unit edge and the other joins the centres of the squares on either side, so there is one small diamond for each inner unit edge, $(a-1)b+a(b-1)$ in all. Every other shape is higher than $1$, so a strip $a\times1$ has only its $a-1$ small diamonds. For the shape $(1,2)$ in the $3\times2$ grid, $2x_0\in\{0,1,2,3\}$ and $2y_0\in\{0,1\}$ must have the same parity, which leaves $4$ positions. In all, the $3\times2$ grid has $7$ small diamonds, $4$ rectangles each of the shapes $(1,2)$ and $(2,1)$, $2$ diamonds of shape $(2,2)$ and one rectangle each of the long shapes $(1,3)$ and $(3,1)$: $19$ slanted rectangles, so $R(3,2)=18+19=37$, as in the statement.

7. One sweep for all grids

Instead of counting the slanted rectangles of each of the $AB$ grids separately, place every smaller grid in the lower left corner of the largest one. The $a\times b$ grid is then the part $0\le x\le a$, $0\le y\le b$ of the $A\times B$ grid, and its drawing is the part of the large drawing inside this region, so $D(a,b)$ is the number of slanted rectangles $K$ of the $A\times B$ grid that lie in it. Counting the pairs of a rectangle $K$ and a grid containing it in two ways, grid by grid and rectangle by rectangle, gives ^[5]

$$\sum_{a=1}^{A}\sum_{b=1}^{B}D(a,b)=\sum_{K}w(K),$$

where $w(K)$ is the number of grids that contain $K$. Since $K$ lies in the large grid, it lies in the $a\times b$ grid exactly when $x_{\max}\le a$ and $y_{\max}\le b$, that is, when $a\ge X$ and $b\ge Y$ for the integers $X=\lceil x_{\max}\rceil$ and $Y=\lceil y_{\max}\rceil$, so

$$w(K)=(A-X+1)(B-Y+1).$$

By Section 5, $x_{\max}=(u_2+v_2)/2$ and $y_{\max}=(u_2-v_1)/2$, and $\lceil k/2\rceil=\lfloor(k+1)/2\rfloor$ for every integer $k$, so $X=\lfloor(u_2+v_2+1)/2\rfloor$ and $Y=\lfloor(u_2-v_1+1)/2\rfloor$. Both factors of $w(K)$ are at least $1$, because $X\le A$ and $Y\le B$.

8. Worked example: the $3\times2$ checkpoint

Take $A=3$ and $B=2$, so that $w(K)=(4-X)(3-Y)$. The $19$ slanted rectangles of the $3\times2$ grid fall into five groups:

$9$ reach into the right column and the top row, $X=3$ and $Y=2$, so they lie only in the $3\times2$ grid: weight $1$;
$7$ have $X=Y=2$ and lie in the $2\times2$ and $3\times2$ grids: weight $2$;
the small diamond around the edge from $(2,0)$ to $(2,1)$ lies in the $3\times1$ and $3\times2$ grids: weight $2$;
the small diamond around the edge from $(1,0)$ to $(1,1)$ lies in the $2\times1$, $3\times1$, $2\times2$ and $3\times2$ grids: weight $4$;
the small diamond around the edge from $(0,1)$ to $(1,1)$ lies in the $1\times2$, $2\times2$ and $3\times2$ grids: weight $3$.

The weights add up to $9\cdot1+7\cdot2+2+4+3=32$, the slanted total of Section 3, and with the $40$ upright rectangles we get $S(3,2)=72$, the value of the statement. Grid by grid: the $2\times2$ grid contains the second group and the diamonds of weights $4$ and $3$, so $D(2,2)=9$.

How the Code Works

The C++ program ^[7] accepts --width= and --height= (digits read into an int without an overflow check; defaults $47$ and $43$) and --skip-checkpoints. Unless that flag is given, run_checkpoints checks that solve(3, 2) returns $72$, and otherwise the program exits with code $2$; then main prints solve(width, height).

solve sets n to the smaller and m to the larger size. Reflecting a grid in the line $y=x$ turns the $a\times b$ grid into the $b\times a$ grid and drawn lines into drawn lines, so $R(a,b)=R(b,a)$ and $S(A,B)=S(B,A)$; the program works with $A=n$ and $B=m$. It starts the 64-bit answer with n(n+1)(n+2)/6 times m(m+1)(m+2)/6, the upright total of Section 3; both divisions by $6$ are exact.

For the slanted part, grid is a square array of side dim = 2 * shift + 2 with shift = m + 3. The loops over $i=0,\dots,2n$ and $j=0,\dots,2m$ skip odd $i+j$ and so visit the doubled coordinates $(i,j)=(2x,2y)$ of all crossing points: both even for a corner, both odd for a centre. The code's x = (i + j) / 2 is $u$, its y = (i + 2 * shift - j) / 2 is $v$ plus shift, and the point is marked with a $1$ at grid[x + 1][y + 1]; the shift keeps the indices positive for $v\ge-m$, and row $0$ and column $0$ stay empty. The double loop grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1] turns the array into a summed-area table, in which each entry counts the marked points with both indices at most its own. ^[6]

Four nested loops run over all boxes, every pair of first indices lx < rx and every pair of second indices ly < ry from $1$ to $2m+7$. For each box, full = grid[rx][ry] - grid[rx][ly - 1] - grid[lx - 1][ry] + grid[lx - 1][ly - 1] is its number of marked points: the points with a first index below lx or a second index below ly are subtracted, and those with both indices too small, subtracted twice, are added back. The box is accepted when full equals area = (rx - lx + 1) * (ry - ly + 1), its number of lattice points. Then all its lattice points are crossing points of the grid, which by Section 5 happens exactly when its four corners are, so the accepted boxes are the slanted rectangles. Since rx, ry and ly are $u_2+1$, $v_2+m+4$ and $v_1+m+4$, the integer divisions mi = (rx + ry - shift - 1) / 2 and mj = (rx - ly + shift + 1) / 2 compute $X$ and $Y$ of Section 7; their numerators are positive, so truncating division in C++ and Java and floor division in Python agree. A guard skips values of mi or mj outside $1,\dots,n$ or $1,\dots,m$, which by Section 7 cannot occur, and every accepted box adds its weight (n - mi + 1) * (m - mj + 1).

The weights are at most $nm=2021$ and the $47\times43$ grid has $2\,702\,851$ slanted rectangles, so the a priori bound on the slanted part, about $5.5\cdot10^9$, exceeds the 32-bit range; C++ sums in long long, Java in long, and Python's integers are unbounded. The Python program copies solve line by line, but parse_arguments receives sys.argv[1:] and still starts at index $1$, so the first option is ignored, and --width=3 --height=2 computes $S(47,2)$; the default run has no options and is not affected. The Java program has only solve and a main that prints solve(47, 43), with no options and no checkpoint; it computes the two binomial factors in int, which is exact for these sizes.

Complexity and Verification

The upright part costs $O(1)$. Marking the crossing points takes $(2n+1)(2m+1)$ steps, and the summed-area pass updates $(2m+7)^2$ of the $(2m+8)^2$ cells, so this stage needs $O(m^2)$ time and memory: for the target, $102^2=10404$ cells, of which $44\cdot48+43\cdot47=4133$ are marked. The sweep tests $\binom{2m+7}{2}^2$ boxes at constant cost each, so the running time is $\Theta(m^4)$: $5050^2=25\,502\,500$ tests, of which $2\,702\,851$ are accepted. The number of boxes depends only on $m$, so a thin grid such as $47\times1$ needs the same sweep as $47\times47$, and by Section 7 this single sweep serves all $2021$ grids. In tests on a desktop computer, C++ and Java took a small fraction of a second and Python a few seconds. The count by shapes of Section 6 gives a single $D(a,b)$ in $O(\min(a,b)^2)$ steps, without a sweep; below it serves as an independent check.

The C++ and Python programs check $S(3,2)=72$ before the main computation; the Java program has no check. Outside the published solutions, a separate brute force follows the unit edges and half-diagonals of the drawing step by step, from every crossing point and for every pair of side lengths. It reproduces all six values of the statement and the total $72$, and the published Python solve agrees with its totals $S(A,B)$ for all $81$ sizes with $A,B\le9$ and for $S(10,10)=136543$. The count by shapes agrees with the brute force for every $D(a,b)$ with $a,b\le9$ and, together with the upright part, gives the same total for $47\times43$ as the three programs, which agree with each other; the guard never skips a box. For testing other programs: $S(4,4)=906$, $S(10,5)=S(5,10)=17989$ and $S(20,20)=7303506$.

Footnotes and References

The references below supply the background facts used above; the reduction of slanted rectangles to boxes, the count by shapes and the weights of Section 7 are derived explicitly in this article.

Project Euler 147 — Rectangles in Cross-hatched Grids. The official statement: a 3 × 2 cross-hatched grid holds 37 rectangles, and the grids 1 × 1, 2 × 1, 3 × 1, 1 × 2 and 2 × 2, whose two dimensions are told apart, hold 1, 4, 8, 4 and 18, for a total of 72; the task asks for the number of rectangles in the 47 × 43 grid and all smaller grids.
Wikipedia — Binomial coefficient. C(n, k) is the number of k-element subsets of an n-element set and equals n! / (k! (n − k)!).
Wikipedia — Hockey-stick identity. For integers n ≥ r ≥ 0, the sum of C(i, r) over i = r, …, n equals C(n + 1, r + 1); the page proves it by induction with Pascal's identity.
Wikipedia — Rotation of axes in two dimensions. Rotating the axes by an angle θ gives a point the new coordinates x′ = x cos θ + y sin θ and y′ = −x sin θ + y cos θ; for θ = 45° these are (x + y) / √2 and (y − x) / √2.
Wikipedia — Double counting (proof technique). Two expressions are shown to be equal by counting the same set in two ways; Section 7 counts the pairs of a slanted rectangle and a grid that contains it.
Wikipedia — Summed-area table. Each entry holds the sum of all values above and to the left of it, inclusive; one pass with I(x, y) = i(x, y) + I(x, y − 1) + I(x − 1, y) − I(x − 1, y − 1) builds the table, and a rectangle sum then needs exactly four array references.
C++ — Euler147.cpp. The linked immutable revision contains solve, the option parser and run_checkpoints with the check for the 3 × 2 grid; it is the implementation record for this article.

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));
    }
}