Detailed mathematical approach

Problem Summary

Problem 11 gives a fixed \(20\times 20\) grid of nonnegative integers and asks for the largest product of four adjacent entries lying on one straight segment. The allowed segments are horizontal, vertical, diagonal down-right, and diagonal down-left. The implementations also expose a general window length \(w\), so it is natural to describe the method for arbitrary \(w\) and then specialize to \(w=4\).

This is not a problem that needs dynamic programming, graph search, or number theory. The core mathematical object is simply the finite set of all valid length-\(w\) segments in the grid. Once that set is described correctly, the answer is the maximum of their products.

Mathematical Approach

Let the grid be \(A[r,c]\) with \(0 \le r \lt R\) and \(0 \le c \lt C\). For Project Euler 11 we have \(R=C=20\), but the formulas below work for any rectangular grid.

Straight segments as direction vectors

Every candidate segment is determined by a starting cell \((r,c)\), a direction vector \((\Delta r,\Delta c)\), and the window length \(w\). The implementations use the four direction vectors

$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$

For such a triple, the product along the segment is

$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$

The desired quantity is therefore

$M=\max P(r,c,\Delta r,\Delta c),$

where the maximum ranges over every valid start cell and every direction in \(\mathcal D\).

Why four directions are enough

A straight segment can be traversed in two opposite orientations, but the product of its entries is unchanged when the order is reversed. If a segment is scanned in direction \((\Delta r,\Delta c)\), then the same cells are scanned in reverse from the far endpoint using \((-\Delta r,-\Delta c)\).

Formally, whenever the indices are valid,

$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$

So it is enough to check right, down, down-right, and down-left. This symmetry ensures that every admissible straight segment is represented exactly once and prevents double counting.

The terminal-cell boundary test

The implementations do not separately validate every intermediate index before multiplying. They use a simpler invariant: for the four chosen directions, the row and column coordinates move monotonically, so a segment is valid if and only if its last cell stays inside the grid. Define the terminal cell

$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$

If \(e\) lies inside the rectangle, then every intermediate point between \((r,c)\) and \(e\) also lies inside, because each coordinate changes only by \(0\), \(1\), or \(-1\) at each step and never overshoots the endpoint.

This gives the valid start ranges immediately.

Horizontal: \(0 \le r \lt R\), \(0 \le c \le C-w\).

Vertical: \(0 \le r \le R-w\), \(0 \le c \lt C\).

Main diagonal: \(0 \le r \le R-w\), \(0 \le c \le C-w\).

Anti-diagonal: \(0 \le r \le R-w\), \(w-1 \le c \lt C\).

Counting the search space

Because every valid segment is represented by exactly one start-direction pair, exhaustive search is mathematically exact. The number of candidates is

$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$

assuming \(1 \le w \le \min(R,C)\). For the Euler instance \((R,C,w)=(20,20,4)\), this becomes

$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$

So the problem is simply the maximum of 1258 explicitly computable products. That is why direct enumeration is not merely acceptable here; it is the natural exact method.

Worked example from the checkpoint grid

One implementation includes a \(4\times 4\) check grid with \(w=3\):

$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$

The main diagonal segment starting at the second row and second column has product \(9\cdot 8\cdot 7=504\). Any other length-3 segment contains at most one of the numbers \(9,8,7\), with the remaining factors equal to \(1\), so no competing product can exceed \(504\). This miniature case is exactly the same computation performed on the full \(20\times 20\) grid: enumerate valid straight segments, multiply their entries, and keep the largest value.

Why direct recomputation is the right choice here

The given grid contains zeros, and the window length is only four. That makes the direct product formula especially attractive: each candidate is short, exact, and needs no special handling for division by zero. A rolling-product method would save almost nothing on a \(20\times 20\) grid while making the zero cases more awkward.

How the Code Works

Representing the data

The C++, Python, and Java implementations hard-code the \(20\times 20\) grid and store the four direction vectors in a small table. They also parameterize the segment length by \(w\), even though the Project Euler question itself uses \(w=4\).

Enumerating valid candidates

The main search uses nested loops over rows, columns, and the four directions. For each triple, the implementation computes the terminal cell after \(w-1\) steps. If that terminal cell lies outside the grid, the candidate is skipped immediately. This matches the boundary criterion proved above and guarantees that no out-of-range access can occur.

Computing products and tracking the optimum

When a candidate is valid, the implementation multiplies the \(w\) entries on that segment directly and compares the result with the current best value. The maximum is updated only when a larger product is found. The C++ implementation additionally performs a small checkpoint on a diagonal-heavy toy grid before solving the main instance; the Python and Java implementations use the same core enumeration without that extra command-line layer.

Complexity Analysis

With \(R\) rows, \(C\) columns, window length \(w\), and four directions, the running time is \(O(RCw)\); written more explicitly, \(O(RC|\mathcal D|w)\) with \(|\mathcal D|=4\). For the actual Euler input there are \(20\cdot 20\cdot 4=1600\) start-direction boundary checks and 1258 valid products, each involving four short multiplications. The workload is tiny.

The extra working memory is \(O(1)\) beyond the stored grid and the small direction table. If the input grid itself is counted as part of storage, the total memory usage is \(O(RC)\).

Footnotes and References

1. Project Euler Problem 11: https://projecteuler.net/problem=11
2. Matrix (mathematics): Wikipedia - Matrix
3. Diagonal: Wikipedia - Diagonal
4. Brute-force search: Wikipedia - Brute-force search
5. Big O notation: Wikipedia - Big O notation