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.
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.
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\).
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 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\).
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.
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.
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.
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\).
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.
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.
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)\).
Problem 11 gibt ein festes \(20\times 20\)-Gitter aus nichtnegativen ganzen Zahlen vor und fragt nach dem größten Produkt von vier benachbarten Einträgen auf einem geraden Segment. Erlaubt sind horizontale, vertikale, diagonal nach rechts unten und diagonal nach links unten verlaufende Segmente. Die Implementierungen behandeln zusätzlich eine allgemeine Fensterlänge \(w\), daher ist es sinnvoll, die Methode zunächst für beliebiges \(w\) zu formulieren und erst danach \(w=4\) einzusetzen.
Hier braucht man weder dynamische Programmierung noch Zahlentheorie. Das zentrale mathematische Objekt ist einfach die endliche Menge aller gültigen Segmente der Länge \(w\) im Gitter. Sobald diese Menge sauber beschrieben ist, besteht die Antwort aus nichts anderem als dem Maximum ihrer Produkte.
Bezeichne das Gitter mit \(A[r,c]\), wobei \(0 \le r \lt R\) und \(0 \le c \lt C\) gilt. Für Project Euler 11 ist \(R=C=20\), aber die folgenden Formeln funktionieren für jedes rechteckige Gitter.
Jeder Kandidat wird durch eine Startzelle \((r,c)\), einen Richtungsvektor \((\Delta r,\Delta c)\) und die Fensterlänge \(w\) bestimmt. Die Implementierungen verwenden die vier Richtungsvektoren
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
Für ein solches Tripel ist das Produkt entlang des Segments
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$$
Gesucht ist also
$$M=\max P(r,c,\Delta r,\Delta c),$$
wobei das Maximum über alle gültigen Startzellen und alle Richtungen aus \(\mathcal D\) genommen wird.
Ein gerades Segment kann in zwei entgegengesetzten Orientierungen durchlaufen werden, aber das Produkt seiner Einträge ändert sich dabei nicht. Wird ein Segment in Richtung \((\Delta r,\Delta c)\) gelesen, dann erhält man dieselben Zellen rückwärts vom anderen Endpunkt aus mit \((-\Delta r,-\Delta c)\).
Formal gilt, sobald die Indizes gültig sind,
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$$
Daher reicht es, nur nach rechts, nach unten, diagonal rechts unten und diagonal links unten zu prüfen. Genau diese Symmetrie sorgt dafür, dass jedes zulässige Segment genau einmal erfasst wird und keine Doppeltzählung entsteht.
Die Implementierungen prüfen nicht jeden Zwischenindex gesondert, bevor multipliziert wird. Sie verwenden eine einfachere Invariante: Für die vier gewählten Richtungen verlaufen Zeilen- und Spaltenkoordinate monoton, also ist ein Segment genau dann gültig, wenn seine letzte Zelle noch im Gitter liegt. Definiere die Endzelle durch
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$$
Liegt \(e\) innerhalb des Rechtecks, dann liegen auch alle Zwischenpunkte zwischen \((r,c)\) und \(e\) im Rechteck, weil sich jede Koordinate pro Schritt nur um \(0\), \(1\) oder \(-1\) ändert und den Endpunkt nicht überschießen kann.
Damit ergeben sich die zulässigen Startbereiche direkt.
Horizontal: \(0 \le r \lt R\), \(0 \le c \le C-w\).
Vertikal: \(0 \le r \le R-w\), \(0 \le c \lt C\).
Hauptdiagonale: \(0 \le r \le R-w\), \(0 \le c \le C-w\).
Nebendiagonale: \(0 \le r \le R-w\), \(w-1 \le c \lt C\).
Weil jedes gültige Segment genau durch ein Start-Richtungs-Paar beschrieben wird, ist die vollständige Enumeration mathematisch exakt. Die Anzahl der Kandidaten lautet
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$$
vorausgesetzt \(1 \le w \le \min(R,C)\). Für den Euler-Fall \((R,C,w)=(20,20,4)\) ergibt sich
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$$
Das Problem ist also schlicht das Maximum von 1258 explizit berechenbaren Produkten. Genau deshalb ist die direkte Enumeration hier nicht nur ausreichend, sondern die natürliche exakte Methode.
Eine Implementierung enthält ein \(4\times 4\)-Prüfgitter mit \(w=3\):
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
Das Hauptdiagonalsegment ab der zweiten Zeile und zweiten Spalte hat das Produkt \(9\cdot 8\cdot 7=504\). Jedes andere Segment der Länge 3 enthält höchstens eine der Zahlen \(9,8,7\), während die übrigen Faktoren gleich \(1\) sind. Deshalb kann kein Konkurrenzprodukt größer als \(504\) werden. Dieses Miniaturbeispiel ist exakt dieselbe Rechnung wie im \(20\times 20\)-Fall: gültige gerade Segmente auflisten, Einträge multiplizieren, Maximum behalten.
Das gegebene Gitter enthält Nullen, und die Fensterlänge beträgt nur vier. Dadurch ist die direkte Produktformel besonders passend: Jeder Kandidat ist kurz, exakt und benötigt keinen Sonderfall für Division durch null. Eine rollende Produkttechnik würde auf einem \(20\times 20\)-Gitter fast nichts einsparen und gleichzeitig die Nullbehandlung komplizierter machen.
Die Implementierungen in C++, Python und Java hinterlegen das \(20\times 20\)-Gitter fest im Programm und speichern die vier Richtungsvektoren in einer kleinen Tabelle. Außerdem ist die Segmentlänge als Parameter \(w\) formuliert, obwohl die Euler-Aufgabe selbst \(w=4\) verlangt.
Die Hauptsuche verwendet verschachtelte Schleifen über Zeilen, Spalten und die vier Richtungen. Für jedes Tripel berechnet die Implementierung die Endzelle nach \(w-1\) Schritten. Liegt diese Endzelle außerhalb des Gitters, wird der Kandidat sofort übersprungen. Das entspricht genau dem oben bewiesenen Randkriterium und verhindert jeden Zugriff außerhalb des gültigen Bereichs.
Ist ein Kandidat gültig, multipliziert die Implementierung die \(w\) Einträge auf diesem Segment direkt und vergleicht das Ergebnis mit dem bisher besten Wert. Das Maximum wird nur dann aktualisiert, wenn ein größeres Produkt gefunden wird. Die C++-Version führt zusätzlich vor der Hauptlösung einen kleinen Test auf einem diagonal betonten Spielzeugbeispiel aus; die Python- und Java-Versionen verwenden dieselbe Kernenumeration ohne diese zusätzliche Kommandozeilenhülle.
Mit \(R\) Zeilen, \(C\) Spalten, Fensterlänge \(w\) und vier Richtungen beträgt die Laufzeit \(O(RCw)\); ausgeschrieben \(O(RC|\mathcal D|w)\) mit \(|\mathcal D|=4\). Für die konkrete Euler-Eingabe gibt es \(20\cdot 20\cdot 4=1600\) Randtests für Start-Richtungs-Kombinationen und 1258 gültige Produkte, von denen jedes nur vier kurze Multiplikationen benötigt. Der Rechenaufwand ist winzig.
Der zusätzliche Arbeitspeicher ist \(O(1)\) über dem gespeicherten Gitter und der kleinen Richtungs-Tabelle. Zählt man das Eingangsgitter selbst zur Speicherung, liegt der Gesamtbedarf bei \(O(RC)\).
Problem 11, sabit bir \(20\times 20\) ızgaradaki negatif olmayan tamsayılar arasından, aynı doğru parçası üzerinde yer alan dört komşu değerin en büyük çarpımını ister. İzin verilen doğrultular yatay, dikey, sağ aşağı çapraz ve sol aşağı çaprazdır. Uygulamalar ayrıca genel bir pencere uzunluğu \(w\) ile yazıldığı için, yöntemi önce genel \(w\) için anlatıp sonra \(w=4\) durumuna inmek en temiz yaklaşımdır.
Bu soru için dinamik programlama, grafik araması ya da sayı teorisi gerekmez. Temel matematiksel nesne, ızgaradaki tüm geçerli uzunluk-\(w\) parçalarının sonlu kümesidir. Bu küme doğru tanımlandığında aranan cevap, bu parçaların çarpımları içindeki maksimumdan ibarettir.
Izgarayı \(A[r,c]\) ile gösterelim; burada \(0 \le r \lt R\) ve \(0 \le c \lt C\). Project Euler 11 için \(R=C=20\), fakat aşağıdaki formüller her dikdörtgen ızgara için geçerlidir.
Her aday parça bir başlangıç hücresi \((r,c)\), bir yön vektörü \((\Delta r,\Delta c)\) ve pencere uzunluğu \(w\) ile belirlenir. Uygulamaların kullandığı dört yön vektörü şunlardır:
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
Bu üçlü için parça üzerindeki çarpım
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c]$$
şeklindedir. Dolayısıyla aradığımız büyüklük
$$M=\max P(r,c,\Delta r,\Delta c)$$
olur; burada maksimum, tüm geçerli başlangıç hücreleri ve \(\mathcal D\) içindeki tüm yönler üzerinde alınır.
Düz bir parça iki zıt yönde taranabilir, fakat üzerindeki sayıların çarpımı başlangıcı hangi uç olarak seçtiğimize bağlı değildir. Bir parça \((\Delta r,\Delta c)\) yönünde okunuyorsa, aynı hücreler öteki uçtan \((-\Delta r,-\Delta c)\) yönüyle ters sırada da okunur.
Biçimsel olarak, indisler geçerli olduğu sürece
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr)$$
eşitliği vardır. Bu yüzden yalnızca sağa, aşağı, sağ aşağı çapraza ve sol aşağı çapraza bakmak yeterlidir. Bu simetri sayesinde her geçerli doğru parçası tam bir kez temsil edilir ve çift sayım oluşmaz.
Uygulamalar çarpma yapmadan önce ara indislerin hepsini tek tek denetlemez. Daha basit bir değişmez kullanırlar: seçilen dört yön için satır ve sütun koordinatları monoton ilerler; dolayısıyla bir parça, ancak ve ancak son hücresi ızgara içinde kalıyorsa geçerlidir. Son hücreyi
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr)$$
olarak tanımlayalım. \(e\) dikdörtgenin içindeyse, \((r,c)\) ile \(e\) arasındaki tüm ara noktalar da içeridedir; çünkü her koordinat her adımda yalnızca \(0\), \(1\) ya da \(-1\) kadar değişir ve uç noktayı aşamaz.
Böylece geçerli başlangıç aralıkları hemen çıkar.
Yatay: \(0 \le r \lt R\), \(0 \le c \le C-w\).
Dikey: \(0 \le r \le R-w\), \(0 \le c \lt C\).
Ana çapraz: \(0 \le r \le R-w\), \(0 \le c \le C-w\).
Ters çapraz: \(0 \le r \le R-w\), \(w-1 \le c \lt C\).
Her geçerli parça tam olarak bir başlangıç-yön çiftiyle temsil edildiği için, kapsamlı tarama matematiksel olarak tam isabetlidir. Aday sayısı
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1)$$
olur; burada \(1 \le w \le \min(R,C)\) varsayılır. Euler örneğinde \((R,C,w)=(20,20,4)\) için
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258$$
elde edilir. Yani problem, açıkça hesaplanabilen 1258 çarpımın maksimumunu almaktan ibarettir. Bu yüzden doğrudan numaralandırma burada sadece yeterli değil, aynı zamanda doğal ve tam yöntemdir.
Uygulamalardan biri \(w=3\) için şu \(4\times 4\) kontrol ızgarasını içerir:
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
İkinci satır ikinci sütundan başlayan ana çapraz parçanın çarpımı \(9\cdot 8\cdot 7=504\) olur. Uzunluğu 3 olan başka herhangi bir parça en fazla \(9\), \(8\) ya da \(7\) sayılarından birini içerir; geri kalan çarpanlar \(1\) olduğundan hiçbir rakip çarpım \(504\)'ü geçemez. Bu küçük örnek, tam \(20\times 20\) çözümün yaptığı şeyin aynısıdır: geçerli doğru parçalarını listele, üzerlerindeki değerleri çarp, en büyüğü sakla.
Verilen ızgarada sıfırlar vardır ve pencere uzunluğu yalnızca dörttür. Bu yüzden doğrudan çarpım formülü özellikle uygundur: her aday kısa, tam ve sıfıra bölme gibi bir özel durum gerektirmez. Kayan çarpım yaklaşımı \(20\times 20\) gibi küçük bir ızgarada neredeyse hiçbir kazanç sağlamazken sıfır içeren durumları daha karmaşık hale getirirdi.
C++, Python ve Java uygulamaları \(20\times 20\) ızgarayı sabit olarak kod içine yerleştirir ve dört yön vektörünü küçük bir tabloda tutar. Ayrıca Euler sorusu \(w=4\) istemesine rağmen, parça uzunluğu \(w\) bir parametre olarak bırakılmıştır.
Ana arama satırlar, sütunlar ve dört yön üzerinde iç içe döngüler kurar. Her üçlü için uygulama, \(w-1\) adım sonraki son hücreyi hesaplar. Bu hücre ızgara dışındaysa aday hemen atlanır. Bu, yukarıda kanıtlanan sınır ölçütüyle tam olarak aynıdır ve geçersiz indis erişimini engeller.
Aday geçerliyse uygulama o parça üzerindeki \(w\) değeri doğrudan çarpar ve sonucu o ana kadarki en iyi değerle karşılaştırır. Sadece daha büyük bir çarpım bulunduğunda maksimum güncellenir. C++ sürümü ana örneği çözmeden önce çapraz ağırlıklı küçük bir kontrol de yapar; Python ve Java sürümleri aynı temel taramayı bu ek komut satırı katmanı olmadan uygular.
\(R\) satır, \(C\) sütun, pencere uzunluğu \(w\) ve dört yön için çalışma süresi \(O(RCw)\) olur; daha açık yazarsak \(|\mathcal D|=4\) ile \(O(RC|\mathcal D|w)\). Gerçek Euler girdisinde \(20\cdot 20\cdot 4=1600\) başlangıç-yön sınır testi ve 1258 geçerli çarpım vardır; her birinde yalnızca dört kısa çarpma yapılır. İş yükü çok küçüktür.
Ek çalışma belleği, saklanan ızgara ve küçük yön tablosunun ötesinde \(O(1)\)'dir. Giriş ızgarasını da depolamaya dahil edersek toplam bellek kullanımı \(O(RC)\) olur.
El Problema 11 da una cuadrícula fija de \(20\times 20\) enteros no negativos y pide el mayor producto de cuatro entradas adyacentes situadas sobre un mismo segmento recto. Los segmentos permitidos son horizontales, verticales, diagonales hacia abajo a la derecha y diagonales hacia abajo a la izquierda. Las implementaciones también admiten una longitud de ventana general \(w\), así que conviene explicar el método para \(w\) arbitrario y luego especializar a \(w=4\).
Aquí no hace falta programación dinámica, teoría de grafos ni teoría de números. El objeto matemático central es simplemente el conjunto finito de todos los segmentos válidos de longitud \(w\) dentro de la cuadrícula. Una vez descrito correctamente ese conjunto, la respuesta es el máximo de sus productos.
Sea la cuadrícula \(A[r,c]\), con \(0 \le r \lt R\) y \(0 \le c \lt C\). En Project Euler 11 se tiene \(R=C=20\), pero las fórmulas siguientes valen para cualquier cuadrícula rectangular.
Cada candidato queda determinado por una celda inicial \((r,c)\), un vector de dirección \((\Delta r,\Delta c)\) y la longitud de ventana \(w\). Las implementaciones usan los cuatro vectores
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
Para tal triple, el producto sobre el segmento es
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$$
Por tanto, la cantidad buscada es
$$M=\max P(r,c,\Delta r,\Delta c),$$
donde el máximo se toma sobre todas las celdas iniciales válidas y todas las direcciones de \(\mathcal D\).
Un segmento recto puede recorrerse en dos orientaciones opuestas, pero el producto de sus entradas no cambia al invertir el orden. Si un segmento se recorre en dirección \((\Delta r,\Delta c)\), las mismas celdas se recorren en sentido contrario desde el extremo opuesto con \((-\Delta r,-\Delta c)\).
Formalmente, siempre que los índices sean válidos,
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$$
Así, basta con examinar derecha, abajo, diagonal principal descendente y antidiagonal descendente. Esta simetría garantiza que cada segmento admisible quede representado exactamente una vez y evita contar dos veces el mismo producto.
Las implementaciones no comprueban por separado cada índice intermedio antes de multiplicar. Usan una invariante más simple: para las cuatro direcciones elegidas, las coordenadas de fila y columna evolucionan de forma monótona, así que un segmento es válido si y solo si su última celda permanece dentro de la cuadrícula. Definimos la celda terminal como
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$$
Si \(e\) está dentro del rectángulo, entonces todos los puntos intermedios entre \((r,c)\) y \(e\) también lo están, porque cada coordenada cambia solo en pasos de \(0\), \(1\) o \(-1\) y nunca sobrepasa el extremo final.
De ahí se obtienen inmediatamente los rangos de inicio válidos.
Horizontal: \(0 \le r \lt R\), \(0 \le c \le C-w\).
Vertical: \(0 \le r \le R-w\), \(0 \le c \lt C\).
Diagonal principal: \(0 \le r \le R-w\), \(0 \le c \le C-w\).
Antidiagonal: \(0 \le r \le R-w\), \(w-1 \le c \lt C\).
Como cada segmento válido queda representado por exactamente un par inicio-dirección, la búsqueda exhaustiva es matemáticamente exacta. El número de candidatos es
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$$
suponiendo \(1 \le w \le \min(R,C)\). Para el caso de Euler \((R,C,w)=(20,20,4)\), resulta
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$$
En otras palabras, el problema consiste sencillamente en tomar el máximo entre 1258 productos explícitamente calculables. Por eso la enumeración directa no solo es suficiente aquí; es el método exacto natural.
Una de las implementaciones incluye una cuadrícula de control \(4\times 4\) con \(w=3\):
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
El segmento de la diagonal principal que empieza en la segunda fila y segunda columna tiene producto \(9\cdot 8\cdot 7=504\). Cualquier otro segmento de longitud 3 contiene como mucho uno de los números \(9\), \(8\) o \(7\), y los demás factores son \(1\), de modo que ningún producto competidor puede superar \(504\). Este ejemplo pequeño es exactamente el mismo cálculo que se hace en la cuadrícula completa \(20\times 20\): enumerar segmentos rectos válidos, multiplicar sus entradas y conservar el mayor valor.
La cuadrícula dada contiene ceros y la ventana tiene longitud cuatro. Eso hace que la fórmula directa del producto sea especialmente adecuada: cada candidato es corto, exacto y no requiere tratar aparte divisiones por cero. Un método de producto deslizante ahorraría casi nada en una cuadrícula \(20\times 20\) y complicaría el manejo de las entradas nulas.
Las implementaciones en C++, Python y Java incorporan la cuadrícula \(20\times 20\) en el propio programa y guardan los cuatro vectores de dirección en una tabla pequeña. Además, parametrizan la longitud del segmento con \(w\), aunque la pregunta de Project Euler use concretamente \(w=4\).
La búsqueda principal usa bucles anidados sobre filas, columnas y las cuatro direcciones. Para cada triple, la implementación calcula la celda terminal tras \(w-1\) pasos. Si esa celda queda fuera de la cuadrícula, el candidato se descarta inmediatamente. Esto coincide exactamente con el criterio de frontera demostrado antes y evita cualquier acceso fuera de rango.
Cuando un candidato es válido, la implementación multiplica directamente las \(w\) entradas del segmento y compara el resultado con el mejor valor visto hasta ese momento. El máximo solo se actualiza cuando aparece un producto mayor. La implementación en C++ añade además una pequeña comprobación previa sobre una cuadrícula de juguete muy diagonal; las versiones en Python y Java siguen la misma enumeración central sin esa capa adicional de línea de comandos.
Con \(R\) filas, \(C\) columnas, longitud de ventana \(w\) y cuatro direcciones, el tiempo de ejecución es \(O(RCw)\); escrito de forma más explícita, \(O(RC|\mathcal D|w)\) con \(|\mathcal D|=4\). En la entrada real de Euler hay \(20\cdot 20\cdot 4=1600\) comprobaciones de frontera para pares inicio-dirección y 1258 productos válidos, cada uno con solo cuatro multiplicaciones cortas. La carga de trabajo es muy pequeña.
La memoria auxiliar es \(O(1)\) más allá de la cuadrícula almacenada y de la pequeña tabla de direcciones. Si la propia cuadrícula de entrada se cuenta como almacenamiento, entonces la memoria total es \(O(RC)\).
第 11 题给出一个固定的 \(20\times 20\) 非负整数网格，要求找出同一直线段上四个相邻数字的最大乘积。允许的方向只有四种：水平、竖直、右下对角线和左下对角线。三种实现还把窗口长度写成了一般的 \(w\)，因此最自然的讲法是先讨论任意 \(w\)，再把题目的具体值 \(w=4\) 代入。
这道题不需要动态规划、图搜索或数论技巧。真正的数学对象只是“网格中所有合法的长度为 \(w\) 的直线段”这一有限集合。只要把这个集合描述准确，答案就是这些线段乘积中的最大值。
记网格为 \(A[r,c]\)，其中 \(0 \le r \lt R\)，\(0 \le c \lt C\)。对 Project Euler 11 而言，\(R=C=20\)，但下面的公式对任意矩形网格都成立。
每一个候选线段都由三个量唯一决定：起点单元格 \((r,c)\)、方向向量 \((\Delta r,\Delta c)\) 以及窗口长度 \(w\)。实现中使用的四个方向向量是
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
对于这样的三元组，线段上的乘积写成
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$$
于是题目要求的量就是
$$M=\max P(r,c,\Delta r,\Delta c),$$
这里最大值是在所有合法起点和所有 \(\mathcal D\) 中的方向上取得的。
一条直线段可以从两个相反方向去读，但把其中的数字反过来排列并不会改变乘积。如果某条线段按 \((\Delta r,\Delta c)\) 方向扫描，那么从它的另一端点出发、按 \((-\Delta r,-\Delta c)\) 方向扫描，得到的是完全相同的一组格子。
形式化地说，只要相关下标合法，就有
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$$
因此只看向右、向下、右下和左下四个方向就已经覆盖了全部合法直线段，而且每条线段只会出现一次。这一对称性正是穷举不会重复计数的原因。
实现里并不会在乘法之前逐个检查所有中间位置是否越界，而是利用了一个更简单的不变量：对于选定的四个方向，行坐标和列坐标都是单调变化的，所以一条线段合法，当且仅当它的最后一个格子仍然在网格内部。把终点定义为
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$$
如果 \(e\) 落在矩形范围内，那么从 \((r,c)\) 到 \(e\) 之间的所有中间点也一定都在范围内，因为每一步坐标只会变化 \(0\)、\(1\) 或 \(-1\)，不会“跳过”终点之后再回来。
这样一来，四种方向的合法起点范围就能直接写出来。
水平：\(0 \le r \lt R\)，\(0 \le c \le C-w\)。
竖直：\(0 \le r \le R-w\)，\(0 \le c \lt C\)。
主对角线：\(0 \le r \le R-w\)，\(0 \le c \le C-w\)。
副对角线：\(0 \le r \le R-w\)，\(w-1 \le c \lt C\)。
由于每一条合法线段都恰好对应一个“起点 + 方向”组合，所以穷举搜索在数学上就是精确解法。候选线段总数为
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$$
这里假设 \(1 \le w \le \min(R,C)\)。代入 Euler 题目的 \((R,C,w)=(20,20,4)\)，得到
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$$
也就是说，本题本质上只是从 1258 个可以明确计算的乘积里取一个最大值。正因为如此，直接枚举并不是“勉强能用”的办法，而是这道题最自然的精确方法。
其中一个实现包含了一个 \(4\times 4\)、窗口长度 \(w=3\) 的检查网格：
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
从第二行第二列开始的主对角线段乘积是 \(9\cdot 8\cdot 7=504\)。任何别的长度为 3 的线段，至多只能包含 \(9\)、\(8\)、\(7\) 中的一个，其余因子都是 \(1\)，因此不可能超过 \(504\)。这个小例子和完整 \(20\times 20\) 网格上的做法完全一样：列出所有合法直线段，计算乘积，保留最大值。
题目给定的网格里本来就有若干个零，而且窗口长度只有四。这样一来，直接按定义重算乘积就非常合适：每个候选都很短，结果完全精确，也不需要处理“除以零”之类的特殊情况。滚动乘积一类的方法在 \(20\times 20\) 这样的小网格上几乎省不了多少时间，却会让含零窗口的逻辑更麻烦。
C++、Python 和 Java 三个实现都把 \(20\times 20\) 网格直接写在程序里，并用一个很小的方向表保存四个方向向量。虽然题目最终需要的是 \(w=4\)，实现本身仍然把线段长度保留成参数 \(w\)。
主搜索由对行、列以及四个方向的嵌套循环组成。对于每个三元组，实现先算出走 \(w-1\) 步之后的终点。如果这个终点落在网格外面，这个候选就立刻跳过。这个做法与上面证明过的边界判定完全一致，也保证了不会发生越界访问。
当某个候选合法时，实现就直接把该线段上的 \(w\) 个数字相乘，并把结果与当前最优值比较。只有在发现更大的乘积时，最大值才会被更新。C++ 版本在处理主网格之前还额外做了一个偏重对角线的小检查；Python 和 Java 版本则使用同样的核心枚举逻辑，只是不带那层额外的命令行外壳。
若网格有 \(R\) 行、\(C\) 列，窗口长度为 \(w\)，方向数为 4，那么时间复杂度是 \(O(RCw)\)；写得更展开一些，就是 \(|\mathcal D|=4\) 时的 \(O(RC|\mathcal D|w)\)。对题目的实际输入而言，共有 \(20\cdot 20\cdot 4=1600\) 次“起点-方向”边界检查，以及 1258 个真正有效的候选乘积，每个候选只需要四次很短的乘法。计算量非常小。
除网格本身和很小的方向表之外，额外工作内存是 \(O(1)\)。如果把输入网格也计入存储，那么总空间复杂度就是 \(O(RC)\)。
В задаче 11 дана фиксированная таблица \(20\times 20\) из неотрицательных целых чисел, и требуется найти наибольшее произведение четырёх соседних элементов, лежащих на одном прямом отрезке. Разрешены четыре типа направлений: по горизонтали, по вертикали, по главной диагонали вниз и по побочной диагонали вниз. Реализации также допускают общую длину окна \(w\), поэтому удобно сначала описать метод для произвольного \(w\), а затем подставить значение \(w=4\).
Здесь не нужны ни динамическое программирование, ни обход графа, ни какая-либо нетривиальная теория чисел. Центральный математический объект очень прост: это конечное множество всех допустимых отрезков длины \(w\) внутри решётки. Как только это множество описано правильно, ответом становится максимум по произведениям на этих отрезках.
Обозначим таблицу через \(A[r,c]\), где \(0 \le r \lt R\) и \(0 \le c \lt C\). Для Project Euler 11 имеем \(R=C=20\), но все формулы ниже верны для любой прямоугольной решётки.
Каждый кандидат определяется стартовой клеткой \((r,c)\), вектором направления \((\Delta r,\Delta c)\) и длиной окна \(w\). В реализациях используются четыре направления
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
Для такого набора данных произведение вдоль отрезка равно
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$$
Следовательно, искомая величина есть
$$M=\max P(r,c,\Delta r,\Delta c),$$
где максимум берётся по всем допустимым стартовым клеткам и всем направлениям из \(\mathcal D\).
Один и тот же прямой отрезок можно проходить в двух противоположных ориентациях, но произведение его элементов не зависит от того, какой конец считать началом. Если отрезок просматривается в направлении \((\Delta r,\Delta c)\), то тот же набор клеток читается в обратном порядке из дальнего конца с направлением \((-\Delta r,-\Delta c)\).
Формально, если индексы допустимы, то
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$$
Значит, достаточно проверять только вправо, вниз, вниз по главной диагонали и вниз по побочной диагонали. Эта симметрия гарантирует, что каждый допустимый отрезок учитывается ровно один раз и не возникает двойного счёта.
Реализации не проверяют отдельно каждый промежуточный индекс перед умножением. Они используют более простую инварианту: для выбранных четырёх направлений координаты строки и столбца меняются монотонно, поэтому отрезок допустим тогда и только тогда, когда его последняя клетка остаётся внутри таблицы. Определим конечную клетку как
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$$
Если \(e\) лежит внутри прямоугольника, то и все промежуточные точки между \((r,c)\) и \(e\) тоже лежат внутри, потому что каждая координата меняется лишь на \(0\), \(1\) или \(-1\) на каждом шаге и не может перескочить через конечную точку.
Отсюда сразу следуют допустимые диапазоны стартов.
Горизонталь: \(0 \le r \lt R\), \(0 \le c \le C-w\).
Вертикаль: \(0 \le r \le R-w\), \(0 \le c \lt C\).
Главная диагональ: \(0 \le r \le R-w\), \(0 \le c \le C-w\).
Побочная диагональ: \(0 \le r \le R-w\), \(w-1 \le c \lt C\).
Поскольку каждый допустимый отрезок задаётся ровно одной парой «старт + направление», полный перебор является математически точным методом. Число кандидатов равно
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$$
при условии \(1 \le w \le \min(R,C)\). Для случая Euler \((R,C,w)=(20,20,4)\) получаем
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$$
То есть задача сводится просто к нахождению максимума среди 1258 явно вычислимых произведений. Именно поэтому прямой перебор здесь не просто допустим, а является естественным точным решением.
В одной из реализаций есть проверочная решётка \(4\times 4\) с \(w=3\):
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
Отрезок по главной диагонали, начинающийся во второй строке и втором столбце, даёт произведение \(9\cdot 8\cdot 7=504\). Любой другой отрезок длины 3 содержит не более одного из чисел \(9\), \(8\), \(7\), а остальные множители равны \(1\), поэтому никакое другое произведение не может превысить \(504\). Этот маленький пример показывает в точности ту же идею, что и на полном поле \(20\times 20\): перечислить все допустимые прямые отрезки, перемножить их элементы и оставить максимум.
В исходной решётке есть нули, а длина окна равна всего четырём. Поэтому прямое вычисление по формуле особенно удобно: каждый кандидат короткий, результат точный, и не нужны специальные случаи для деления на ноль. Схема со скользящим произведением почти ничего не сэкономила бы на сетке \(20\times 20\), зато усложнила бы обработку нулевых элементов.
Реализации на C++, Python и Java жёстко задают таблицу \(20\times 20\) внутри программы и хранят четыре вектора направления в маленькой таблице. Длина сегмента также задаётся параметром \(w\), хотя сама задача Project Euler использует именно \(w=4\).
Основной поиск построен на вложенных циклах по строкам, столбцам и четырём направлениям. Для каждой тройки программа вычисляет конечную клетку после \(w-1\) шагов. Если эта клетка выходит за границы решётки, кандидат сразу отбрасывается. Это в точности соответствует доказанному выше критерию границ и исключает любые обращения вне диапазона.
Если кандидат допустим, реализация напрямую перемножает \(w\) элементов на этом отрезке и сравнивает результат с текущим лучшим значением. Максимум обновляется только тогда, когда найдено большее произведение. В версии на C++ перед решением основной задачи дополнительно выполняется маленькая проверка на игрушечной сетке с выделенной диагональю; версии на Python и Java используют ту же самую центральную схему перебора без этой дополнительной оболочки командной строки.
При \(R\) строках, \(C\) столбцах, длине окна \(w\) и четырёх направлениях время работы равно \(O(RCw)\); если писать подробнее, то \(O(RC|\mathcal D|w)\) при \(|\mathcal D|=4\). Для реального ввода Euler имеется \(20\cdot 20\cdot 4=1600\) проверок границ для пар «старт-направление» и 1258 допустимых произведений, каждое из которых требует всего четырёх коротких умножений. Объём вычислений очень мал.
Дополнительная рабочая память составляет \(O(1)\) сверх самой решётки и маленькой таблицы направлений. Если учитывать хранение входной решётки, общий расход памяти равен \(O(RC)\).
تعطي المسألة 11 شبكة ثابتة بحجم \(20\times 20\) من الأعداد الصحيحة غير السالبة، وتطلب أكبر جداء لأربعة عناصر متجاورة تقع على مقطع مستقيم واحد. الاتجاهات المسموح بها هي: الأفقي، العمودي، القطر الهابط إلى اليمين، والقطر الهابط إلى اليسار. كما أن التطبيقات الثلاثة تصيغ طول النافذة على نحو عام بالرمز \(w\)، لذا فمن الأنسب شرح الطريقة أولًا لطول عام \(w\)، ثم تخصيصها بعد ذلك إلى حالة المسألة \(w=4\).
لا تحتاج هذه المسألة إلى برمجة ديناميكية أو بحث في الرسوم البيانية أو أدوات من نظرية الأعداد. الكائن الرياضي الأساسي هنا هو فقط المجموعة المنتهية لجميع المقاطع الصحيحة ذات الطول \(w\) داخل الشبكة. ومتى وُصفت هذه المجموعة بدقة، صار الجواب هو القيمة العظمى بين جداءات تلك المقاطع.
لنرمز إلى الشبكة بـ \(A[r,c]\)، حيث \(0 \le r \lt R\) و\(0 \le c \lt C\). في مسألة Project Euler 11 لدينا \(R=C=20\)، لكن الصيغ الآتية صالحة لأي شبكة مستطيلة.
كل مقطع مرشح يتحدد بخلية بداية \((r,c)\)، ومتجه اتجاه \((\Delta r,\Delta c)\)، وطول نافذة \(w\). الاتجاهات الأربعة التي تستعملها التطبيقات هي
$$\mathcal D=\{(0,1),(1,0),(1,1),(1,-1)\}.$$
وبالنسبة إلى هذا الثلاثي يكون الجداء على المقطع
$$P(r,c,\Delta r,\Delta c)=\prod_{t=0}^{w-1} A[r+t\Delta r,\;c+t\Delta c].$$
ومن ثم فإن الكمية المطلوبة هي
$$M=\max P(r,c,\Delta r,\Delta c),$$
حيث يؤخذ هذا العظمى على جميع خلايا البداية الصالحة وعلى جميع الاتجاهات في \(\mathcal D\).
يمكن اجتياز المقطع المستقيم نفسه في اتجاهين متعاكسين، لكن جداء عناصره لا يتغير إذا عكسنا ترتيب القراءة. فإذا فُحص المقطع في الاتجاه \((\Delta r,\Delta c)\)، فإن الخلايا نفسها تُقرأ من الطرف الآخر في الاتجاه \((-\Delta r,-\Delta c)\).
وبصيغة رياضية، ما دامت الفهارس صالحة فإن
$$P(r,c,\Delta r,\Delta c)=P\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c,\;-\Delta r,\;-\Delta c\bigr).$$
لذلك يكفي أن نفحص الاتجاهات: يمين، أسفل، قطر مائل إلى أسفل يمين، وقطر مائل إلى أسفل يسار. هذا التناظر يضمن أن كل مقطع صالح يُمثَّل مرة واحدة بالضبط، ويمنع عدّ المقطع نفسه مرتين.
لا تقوم التطبيقات بفحص كل فهرس وسيط على حدة قبل إجراء الضرب، بل تستخدم ثابتًا أبسط: في الاتجاهات الأربعة المختارة تتحرك إحداثيات الصف والعمود على نحو رتيب، ولذلك يكون المقطع صالحًا إذا وفقط إذا بقيت خليته الأخيرة داخل الشبكة. نعرّف الخلية النهائية بـ
$$e(r,c,\Delta r,\Delta c)=\bigl(r+(w-1)\Delta r,\;c+(w-1)\Delta c\bigr).$$
إذا وقعت \(e\) داخل المستطيل، فإن جميع النقاط الوسيطة بين \((r,c)\) و\(e\) تقع داخله أيضًا، لأن كل إحداثي يتغير في كل خطوة بمقدار \(0\) أو \(1\) أو \(-1\) فقط، ولا يمكن أن يتجاوز نقطة النهاية ثم يعود.
ومن هنا تظهر مجالات البدايات الصالحة مباشرة.
أفقيًا: \(0 \le r \lt R\)، \(0 \le c \le C-w\).
عموديًا: \(0 \le r \le R-w\)، \(0 \le c \lt C\).
القطر الرئيسي: \(0 \le r \le R-w\)، \(0 \le c \le C-w\).
القطر المعاكس: \(0 \le r \le R-w\)، \(w-1 \le c \lt C\).
بما أن كل مقطع صالح يقابله زوج وحيد من «بداية + اتجاه»، فإن الاستقصاء الشامل هنا حل دقيق تمامًا من الناحية الرياضية. عدد المقاطع المرشحة يساوي
$$N=R(C-w+1)+(R-w+1)C+2(R-w+1)(C-w+1),$$
وذلك بافتراض \(1 \le w \le \min(R,C)\). وعند التعويض بحالة Euler، أي \((R,C,w)=(20,20,4)\)، نحصل على
$$N=20\cdot 17+17\cdot 20+2\cdot 17\cdot 17=340+340+289+289=1258.$$
أي إن المسألة في جوهرها ليست أكثر من أخذ القيمة العظمى بين 1258 جداءً يمكن حسابها مباشرة. ولهذا فالتعداد المباشر ليس مجرد حل مقبول، بل هو الطريقة الدقيقة الطبيعية لهذه المسألة.
إحدى التطبيقات تتضمن شبكة فحص \(4\times 4\) مع \(w=3\):
$$\begin{pmatrix} 1&1&1&1\\ 1&9&1&1\\ 1&1&8&1\\ 1&1&1&7 \end{pmatrix}.$$
المقطع الواقع على القطر الرئيسي ابتداءً من الصف الثاني والعمود الثاني يعطي الجداء \(9\cdot 8\cdot 7=504\). أما أي مقطع آخر بطول 3 فإنه يحتوي في أحسن الأحوال على واحد فقط من الأعداد \(9\) أو \(8\) أو \(7\)، بينما تكون العوامل الأخرى مساوية لـ \(1\)، ولذلك لا يمكن لأي جداء منافس أن يتجاوز \(504\). هذا المثال الصغير يوضح بالضبط ما يحدث في الشبكة الكاملة \(20\times 20\): نحصي المقاطع المستقيمة الصالحة، نحسب جداء عناصرها، ثم نحتفظ بالأكبر.
الشبكة المعطاة تحتوي أصلًا على أصفار، وطول النافذة لا يتجاوز أربعة. لذلك تكون صيغة الجداء المباشر مناسبة جدًا: كل مرشح قصير، والنتيجة دقيقة، ولا نحتاج إلى معالجة خاصة لحالات القسمة على الصفر. أما أساليب الجداء المنزلق فلن توفر إلا قدرًا ضئيلًا جدًا من العمل على شبكة \(20\times 20\)، بينما ستجعل التعامل مع النوافذ التي تحتوي على صفر أكثر تعقيدًا.
تقوم تطبيقات C++ وPython وJava بتضمين الشبكة \(20\times 20\) داخل البرنامج نفسه، وتخزن متجهات الاتجاه الأربعة في جدول صغير. كما تُبقي طول المقطع وسيطًا عامًا \(w\)، مع أن سؤال Project Euler الفعلي يستخدم \(w=4\).
البحث الرئيسي يعتمد على حلقات متداخلة فوق الصفوف والأعمدة والاتجاهات الأربعة. ولكل ثلاثي، تحسب الشيفرة الخلية النهائية بعد \(w-1\) خطوة. فإذا كانت هذه الخلية خارج الشبكة، أُهمل هذا المرشح فورًا. وهذا يطابق تمامًا معيار الحدود المثبت أعلاه، ويضمن عدم وقوع أي وصول خارج المجال المسموح.
إذا كان المرشح صالحًا، تضرب الشيفرة مباشرةً قيم \(w\) الخلايا الواقعة على ذلك المقطع، ثم تقارن الناتج بأفضل قيمة معروفة حتى تلك اللحظة. ولا تُحدَّث القيمة العظمى إلا عند العثور على جداء أكبر. وتضيف نسخة C++ فحصًا صغيرًا مسبقًا على شبكة لعب بسيطة ذات قطر واضح، بينما تستخدم نسختا Python وJava المنطق العددي نفسه من دون تلك الطبقة الإضافية الخاصة بسطر الأوامر.
إذا كان لدينا \(R\) صفوف و\(C\) أعمدة وطول نافذة \(w\) وأربعة اتجاهات، فإن زمن التنفيذ يساوي \(O(RCw)\)؛ وبصيغة أكثر تفصيلًا هو \(O(RC|\mathcal D|w)\) مع \(|\mathcal D|=4\). في مُدخل Euler الفعلي توجد \(20\cdot 20\cdot 4=1600\) عملية فحص حدود لأزواج «بداية-اتجاه»، و1258 جداءً صالحًا، وكل واحد منها يحتاج إلى أربع عمليات ضرب قصيرة فقط. عبء الحساب صغير جدًا.
الذاكرة الإضافية أثناء العمل هي \(O(1)\) فوق الشبكة المخزنة وجدول الاتجاهات الصغير. وإذا اعتبرنا أن تخزين الشبكة نفسها جزء من الذاكرة المطلوبة، فإن الاستهلاك الكلي يصبح \(O(RC)\).