Write the 4x4 grid with rows \((a,b,c,d)\), \((e,f,g,h)\), \((i,j,k,l)\), and \((m,n,o,p)\). Every entry is a digit from 0 to 9.
The goal is to count all fillings for which the four row sums, the four column sums, and the two main diagonal sums are all equal to the same value \(S\). In other words,
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
A direct search over all \(10^{16}\) grids is impossible. The implementations avoid that by choosing a convenient subset of cells to enumerate, solving the others from the line-sum equations, and discarding a branch as soon as a derived digit leaves the range 0 to 9.
The key idea is not to search over 16 independent digits. The equal-sum conditions are linear, so many cells can be recovered once a smaller set has been fixed.
The common sum \(S\) is not guessed in advance. Instead, it is produced by the cells chosen during the search. Since every line contains four digits from 0 to 9, any valid grid must satisfy \(0 \le S \le 36\).
The equations above connect rows, columns, and diagonals. The implementations exploit them in a very particular order so that each new formula uses values that are already known.
The search loops over the nine cells \(a,b,c,e,f,g,i,j,k\). This is not the smallest possible parameter count for the real solution space, but it is a very practical choice: every remaining cell becomes an affine expression, and every rejection test is just a bound check.
The first useful identity comes from combining the first row with the anti-diagonal:
$$a+b+c+d=S=d+g+j+m,$$
so the unknown \(d\) disappears and we get
$$m=a+b+c-g-j.$$
Once \(m\) is known, the first column determines the common sum immediately:
$$S=a+e+i+m.$$
After \(m\) and \(S\) are fixed, the rest of the dependent cells follow from one row, one column, or one diagonal at a time:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
Every one of these values must lie in \([0,9]\). If, for example, \(m\) or \(d\) comes out negative, that entire branch can be rejected immediately because no completion of it can ever become a valid digit grid.
By construction, the following eight lines already have sum \(S\): rows 1 to 3, columns 1 to 3, the main diagonal, and the anti-diagonal. The only lines not enforced yet are the last row and the last column.
That is why the implementations finish with exactly these two tests:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
If both equalities hold and every derived cell is a digit, then all ten required line sums are correct.
Take the free cells
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
Then
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
The dependent cells are therefore
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
This gives the grid with rows \((1,0,2,1)\), \((0,1,1,2)\), \((2,1,1,0)\), and \((1,2,0,1)\). All four rows, all four columns, and both diagonals sum to 4. That is exactly the pattern the code looks for: choose nine digits, derive seven more, then keep the grid only if the last two checks also pass.
The C++, Python, and Java implementations use nested loops over the nine free cells, but the order matters. After \(a,b,c,g,j\) are chosen, \(m\) is already known, so invalid branches die before the later loops even begin. After \(e\) and \(i\), the common sum \(S\) and the cell \(d\) are known. After \(f\), two more cells, \(h\) and \(n\), can be tested. After \(k\), the last three dependent cells \(o,l,p\) are available.
This staged evaluation is the whole reason the method is fast enough: many candidates are discarded long before the deepest loop level.
Once all dependent cells have been computed and passed the digit-range tests, the implementation checks the fourth row and fourth column. If both sums equal \(S\), the answer counter increases by one.
The C++ implementation also contains a small sanity test for the reduced digit set \(\{0,1\}\). In that tiny case the correct count is 34, which is a useful checkpoint that the optimized search agrees with brute force on an instance small enough to verify directly.
A naive search examines every 4x4 digit grid, so its cost is \(10^{16}\) when the digits are 0 through 9. The implemented method explicitly iterates only nine cells, so in general its worst-case running time is \(O((d_{\max}+1)^9)\), and for this problem that upper bound is \(10^9\).
The actual runtime is much smaller than that crude upper bound because the formulas for \(m,d,h,n,o,l,p\) trigger heavy early pruning. Memory usage is \(O(1)\): apart from the loop variables, a few temporary integers, and the final counter, no large data structure is needed.
Bezeichne die vier Zeilen des 4x4-Gitters mit \((a,b,c,d)\), \((e,f,g,h)\), \((i,j,k,l)\) und \((m,n,o,p)\). Jeder Eintrag ist eine Ziffer von 0 bis 9.
Gesucht ist die Anzahl aller Belegungen, bei denen die vier Zeilensummen, die vier Spaltensummen und die beiden Hauptdiagonalen denselben Wert \(S\) haben. Also gilt
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
Eine vollständige Suche über alle \(10^{16}\) Gitter ist ausgeschlossen. Die Implementierungen zählen deshalb nicht über alle 16 Felder direkt, sondern wählen einige freie Zellen, berechnen den Rest aus den Summengleichungen und verwerfen einen Zweig sofort, sobald ein berechneter Wert nicht mehr im Ziffernbereich liegt.
Der Kern der Lösung ist eine lineare Reduktion. Die 16 Zellen werden nicht als unabhängig behandelt, weil die Gleichungen der Zeilen, Spalten und Diagonalen viele Werte fest vorgeben.
Die gemeinsame Summe \(S\) wird nicht separat durchlaufen. Sie entsteht automatisch aus den bereits gewählten Zellen. Da jede Linie aus vier Ziffern zwischen 0 und 9 besteht, muss in jeder gültigen Lösung \(0 \le S \le 36\) gelten.
Entscheidend ist die Reihenfolge, in der die Gleichungen benutzt werden: Jede neue Formel soll nur auf Größen zugreifen, die bereits bekannt sind.
Die Implementierungen iterieren über die neun Zellen \(a,b,c,e,f,g,i,j,k\). Das ist nicht die minimal mögliche Parametrisierung des Lösungsraums, aber eine sehr zweckmäßige: Alle übrigen Zellen werden zu einfachen affinen Ausdrücken, und jede Prüfung ist nur noch eine Bereichsabfrage.
Aus erster Zeile und Gegendiagonale folgt
$$a+b+c+d=S=d+g+j+m,$$
also nach Eliminierung von \(d\)
$$m=a+b+c-g-j.$$
Sobald \(m\) bekannt ist, liefert die erste Spalte sofort die gemeinsame Summe:
$$S=a+e+i+m.$$
Danach ergeben sich die restlichen Felder nacheinander aus je einer Zeile, Spalte oder Diagonale:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
Jeder dieser Werte muss in \([0,9]\) liegen. Sobald beispielsweise \(m\) oder \(h\) negativ wird oder größer als 9 ist, kann die gesamte Verzweigung sofort verworfen werden.
Durch die Konstruktion haben bereits acht Linien sicher die Summe \(S\): die Zeilen 1 bis 3, die Spalten 1 bis 3 sowie beide Diagonalen. Noch nicht abgesichert sind nur die vierte Zeile und die vierte Spalte.
Darum reichen am Ende genau diese beiden Tests:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
Wenn beide Gleichungen stimmen und alle berechneten Zellen Ziffern sind, dann sind automatisch alle zehn geforderten Linien korrekt.
Nehmen wir die freien Zellen
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
Dann ist
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
Die abhängigen Werte lauten damit
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
Das ergibt die vier Zeilen \((1,0,2,1)\), \((0,1,1,2)\), \((2,1,1,0)\) und \((1,2,0,1)\). Alle Zeilen, alle Spalten und beide Diagonalen summieren sich zu 4. Genau so arbeitet das Programm: neun Ziffern wählen, sieben berechnen und erst dann die letzten beiden Summen testen.
Die C++-, Python- und Java-Implementierungen verwenden geschachtelte Schleifen über die neun freien Zellen, aber in einer bewusst gewählten Reihenfolge. Nach \(a,b,c,g,j\) ist \(m\) schon bekannt. Nach \(e\) und \(i\) stehen \(S\) und \(d\) fest. Nach \(f\) können \(h\) und \(n\) geprüft werden. Nach \(k\) sind schließlich \(o,l,p\) verfügbar.
Diese stufenweise Auswertung ist der entscheidende Geschwindigkeitsvorteil, weil viele Kandidaten weit vor der tiefsten Schleifenebene ausscheiden.
Wenn alle berechneten Zellen gültige Ziffern sind, prüft die Implementierung noch die vierte Zeile und die vierte Spalte. Stimmen beide mit \(S\) überein, wird der Zähler um eins erhöht.
Die C++-Implementierung enthält zusätzlich einen kleinen Kontrollfall für die reduzierte Ziffernmenge \(\{0,1\}\). Dort ist die korrekte Anzahl 34, was als nützlicher Plausibilitätstest gegen eine kleine Brute-Force-Instanz dient.
Eine naive Methode müsste alle 4x4-Zifferngitter prüfen und hätte daher bei Ziffern 0 bis 9 Aufwand \(10^{16}\). Die implementierte Methode iteriert explizit nur über neun Zellen. Allgemein ergibt das \(O((d_{\max}+1)^9)\), hier also als grobe obere Schranke \(10^9\).
Praktisch liegt die Laufzeit deutlich darunter, weil die Formeln für \(m,d,h,n,o,l,p\) sehr viele Zweige früh verwerfen. Der Speicherverbrauch ist \(O(1)\): außer Schleifenvariablen, einigen temporären Ganzzahlen und dem Ergebniszähler wird keine große Struktur aufgebaut.
4x4 tabloyu satırları sırasıyla \((a,b,c,d)\), \((e,f,g,h)\), \((i,j,k,l)\) ve \((m,n,o,p)\) olacak şekilde adlandıralım. Her hücre 0 ile 9 arasında bir rakamdır.
İstenen şey, dört satır toplamının, dört sütun toplamının ve iki ana köşegen toplamının aynı \(S\) değerine eşit olduğu tüm yerleşimleri saymaktır. Yani
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
Tüm \(10^{16}\) tabloyu denemek imkansızdır. Uygulamalar bunun yerine uygun bir hücre altkümesini döngüyle seçer, kalan hücreleri bu eşitliklerden çözer ve türetilen herhangi bir değer 0 ile 9 aralığının dışına çıkar çıkmaz o dalı hemen eler.
Ana fikir, 16 hücreyi bağımsız değişkenler gibi görmemektir. Eşit toplam koşulları doğrusal olduğu için, daha küçük bir serbest küme seçildiğinde geri kalan hücreler zorunlu olarak belirlenir.
Ortak toplam \(S\) baştan ayrı ayrı denenmez. Arama sırasında seçilen hücrelerden doğal olarak ortaya çıkar. Her doğru üzerinde dört tane 0 ile 9 arası rakam bulunduğu için geçerli bir tabloda mutlaka \(0 \le S \le 36\) olmalıdır.
Burada önemli olan, denklemlerin hangi sırayla kullanıldığıdır. Her yeni formül yalnızca zaten bilinen değerlere dayanacak şekilde kurulmuştur.
Uygulamalar dokuz hücreyi serbest bırakır: \(a,b,c,e,f,g,i,j,k\). Bu seçim, doğrusal sistemin teorik olarak en küçük parametreleştirmesi değildir; fakat pratiktir. Çünkü kalan tüm hücreler basit afin ifadeler haline gelir ve her reddetme testi yalnızca aralık kontrolü olur.
İlk önemli eşitlik, birinci satır ile yan köşegenin birleştirilmesinden gelir:
$$a+b+c+d=S=d+g+j+m,$$
buradan \(d\) yok edilirse
$$m=a+b+c-g-j$$
elde edilir. \(m\) belli olduktan sonra birinci sütun ortak toplamı doğrudan verir:
$$S=a+e+i+m.$$
\(m\) ve \(S\) bilindikten sonra bağımlı hücreler tek tek bir satır, bir sütun veya bir köşegen üzerinden hesaplanır:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
Bu değerlerin her biri \([0,9]\) aralığında olmalıdır. Örneğin \(m\) ya da \(n\) negatif çıkarsa, o koldan hiçbir geçerli çözüm doğmayacağı için arama hemen kesilir.
Bu kurgu sayesinde sekiz doğru zaten otomatik olarak \(S\) toplamına sahiptir: ilk üç satır, ilk üç sütun ve iki köşegen. Henüz zorlanmamış tek doğrular son satır ve son sütundur.
Bu nedenle programın sonunda yalnızca şu iki eşitlik kontrol edilir:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
Her ikisi de sağlanıyorsa ve türetilen tüm hücreler geçerli rakamsa, on gerekli toplamın tamamı doğru demektir.
Şu serbest hücreleri seçelim:
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
O zaman
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
Buna göre bağımlı hücreler
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1$$
olur. Son tablo satır bazında \((1,0,2,1)\), \((0,1,1,2)\), \((2,1,1,0)\) ve \((1,2,0,1)\) şeklindedir. Dört satırın, dört sütunun ve iki köşegenin toplamı 4 eder. Kodun yaptığı tam olarak budur: dokuz rakam seçilir, yedi rakam türetilir ve son iki toplam testi de geçerse çözüm sayılır.
C++, Python ve Java uygulamaları dokuz serbest hücre üzerinde iç içe döngüler kurar; fakat sıra rastgele değildir. \(a,b,c,g,j\) seçildiğinde \(m\) hemen hesaplanır. Ardından \(e\) ve \(i\) geldikten sonra \(S\) ile \(d\) bulunur. \(f\) seçilince \(h\) ve \(n\) test edilir. Son olarak \(k\) seçildiğinde \(o,l,p\) hesaplanır.
Hızın ana sebebi bu kademeli yapıdır: çok sayıda aday, en derin döngülere ulaşmadan önce aralık kontrolleriyle elenir.
Tüm bağımlı hücreler hesaplanıp rakam aralığını geçtiğinde, uygulama son satırı ve son sütunu kontrol eder. İkisi de \(S\) değerine eşitse sayaç bir artırılır.
C++ uygulaması ayrıca \(\{0,1\}\) rakam kümesi için küçük bir sağlamlık testi içerir. Bu küçültülmüş durumda doğru sayı 34'tür; bu da optimize edilmiş yöntemin küçük bir brute-force örneğiyle uyuştuğunu göstermeye yarar.
Naif yaklaşım her 4x4 rakam tablosunu dener ve rakamlar 0 ile 9 ise bunun maliyeti \(10^{16}\) olur. Uygulanan yöntemde açıkça döngüye sokulan hücre sayısı yalnızca dokuzdur. Genel durumda bu \(O((d_{\max}+1)^9)\), bu problemde ise kaba üst sınır olarak \(10^9\) demektir.
Gerçek çalışma süresi bundan çok daha küçüktür; çünkü \(m,d,h,n,o,l,p\) formülleri çok güçlü bir erken budama üretir. Bellek kullanımı \(O(1)\)'dir: döngü değişkenleri, birkaç geçici tam sayı ve sayaç dışında büyük bir veri yapısı tutulmaz.
Denotemos la cuadrícula 4x4 por las filas \((a,b,c,d)\), \((e,f,g,h)\), \((i,j,k,l)\) y \((m,n,o,p)\). Cada casilla contiene un dígito entre 0 y 9.
Hay que contar todas las configuraciones en las que las cuatro filas, las cuatro columnas y las dos diagonales principales tienen la misma suma \(S\). Es decir,
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
Un barrido directo sobre las \(10^{16}\) cuadrículas posibles es inviable. Por eso las implementaciones no recorren 16 variables independientes: fijan un subconjunto cómodo de celdas, deducen las demás a partir de las ecuaciones de suma y podan en cuanto algún valor calculado deja de ser un dígito válido.
La estructura del problema es lineal. Una vez elegidas algunas casillas, las restricciones de filas, columnas y diagonales fuerzan muchas de las restantes.
La suma común \(S\) no se recorre por separado. Surge de las celdas elegidas durante la búsqueda. Como cada línea contiene cuatro dígitos entre 0 y 9, cualquier solución válida debe cumplir \(0 \le S \le 36\).
La clave no es solo qué ecuaciones usar, sino en qué orden usarlas, para que cada nueva casilla dependa únicamente de cantidades ya conocidas.
Las implementaciones iteran sobre las nueve celdas \(a,b,c,e,f,g,i,j,k\). No es la parametrización lineal mínima posible, pero sí una muy cómoda: todas las demás casillas quedan como expresiones afines sencillas y cada descarte se reduce a comprobar si un valor está en \([0,9]\).
Combinando la primera fila con la diagonal secundaria se obtiene
$$a+b+c+d=S=d+g+j+m,$$
de donde desaparece \(d\) y queda
$$m=a+b+c-g-j.$$
Una vez conocido \(m\), la primera columna fija enseguida la suma común:
$$S=a+e+i+m.$$
Después de fijar \(m\) y \(S\), las casillas restantes se recuperan una por una:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
Cada una de estas cantidades debe pertenecer al intervalo \([0,9]\). Si alguna sale negativa o mayor que 9, esa rama ya no puede conducir a una cuadrícula válida y se abandona de inmediato.
Con esta construcción ya quedan forzadas ocho líneas: las tres primeras filas, las tres primeras columnas y las dos diagonales. Las únicas que todavía no han sido impuestas explícitamente son la cuarta fila y la cuarta columna.
Por eso el algoritmo termina con estas dos verificaciones:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
Si ambas se cumplen y todas las celdas calculadas son dígitos, entonces las diez sumas exigidas por el problema son correctas.
Tomemos como celdas libres
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
Entonces
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
Las celdas dependientes quedan
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
La cuadrícula resultante tiene filas \((1,0,2,1)\), \((0,1,1,2)\), \((2,1,1,0)\) y \((1,2,0,1)\). Todas las filas, columnas y diagonales suman 4. Ese es exactamente el mecanismo del programa: elegir nueve dígitos, deducir siete y aceptar solo si las dos restricciones finales también cierran.
Las implementaciones en C++, Python y Java usan bucles anidados sobre las nueve celdas libres, pero en un orden intencional. Tras fijar \(a,b,c,g,j\), ya se conoce \(m\). Después de elegir \(e\) e \(i\), se obtienen \(S\) y \(d\). Tras elegir \(f\), se pueden comprobar \(h\) y \(n\). Finalmente, cuando se fija \(k\), se calculan \(o,l,p\).
Esta evaluación por etapas es la razón de la eficiencia práctica: una gran fracción de candidatos se descarta antes de llegar al nivel más profundo de la enumeración.
Cuando todas las celdas derivadas han pasado las comprobaciones de rango, la implementación verifica la cuarta fila y la cuarta columna. Si ambas suman \(S\), el contador total aumenta en una unidad.
La implementación en C++ añade además una comprobación pequeña para el caso \(d_{\max}=1\). En ese universo reducido la cantidad correcta es 34, lo que sirve como verificación de consistencia frente a una fuerza bruta diminuta.
La búsqueda ingenua revisaría las \(10^{16}\) cuadrículas de dígitos posibles. El método implementado solo itera explícitamente nueve celdas, de modo que en general su cota superior es \(O((d_{\max}+1)^9)\); para el problema original, esa cota bruta es \(10^9\).
En la práctica el tiempo real es bastante menor, porque las fórmulas de \(m,d,h,n,o,l,p\) generan mucha poda anticipada. El consumo de memoria es \(O(1)\): aparte de unas pocas variables enteras temporales y el contador, no se almacena ninguna estructura grande.
把 4x4 方格的四行记为 \((a,b,c,d)\)、\((e,f,g,h)\)、\((i,j,k,l)\) 和 \((m,n,o,p)\)。每个格子都必须填入 0 到 9 之间的一个数字。
题目要求统计所有满足下列条件的填法：四行之和、四列之和以及两条主对角线之和全部等于同一个值 \(S\)。也就是说，
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
如果对全部 \(10^{16}\) 个 4x4 数字方格逐一检查，计算量完全不可接受。实现程序真正做的是：只枚举一个精心挑选的自由变量集合，再用这些线性等式推出其余格子，并在任何一个推导值超出 0 到 9 时立刻剪枝。
这个问题的本质不是 16 个彼此独立的数字，而是一个带有强线性约束的 4x4 系统。只要自由格子选得合适，其余很多格子都会被唯一确定。
公共和 \(S\) 并不是单独枚举出来的，而是由已经选定的格子自动决定。由于每条线都由四个 0 到 9 的数字组成，所以任何合法解都必然满足 \(0 \le S \le 36\)。
实现中的关键不只是“用了哪些等式”，更是“以什么顺序使用这些等式”。这样每个新求出的格子都只依赖于之前已经知道的量。
实现把 \(a,b,c,e,f,g,i,j,k\) 这九个格子当作自由变量来枚举。就线性代数而言，这未必是最小参数数目的表示法，但它非常适合程序：所有剩余格子都变成简单的仿射表达式，而每一次剪枝都只是检查一个值是否仍在 \([0,9]\) 内。
先把第一行和副对角线放在一起：
$$a+b+c+d=S=d+g+j+m.$$
这里可以消去 \(d\)，直接得到
$$m=a+b+c-g-j.$$
一旦 \(m\) 已知，第一列立刻给出公共和：
$$S=a+e+i+m.$$
有了 \(m\) 和 \(S\) 之后，其余依赖格子可以逐个恢复：
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
这些值每一个都必须是 0 到 9 之间的整数。只要其中任何一个超出范围，这条搜索分支就不可能产生合法方格，因此可以立即丢弃。
按照这种构造方式，前 3 行、前 3 列以及两条对角线，一共 8 条线已经被强制为和 \(S\) 相等。此时尚未显式保证的只剩第 4 行和第 4 列。
因此程序最后只做这两项检验：
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
如果这两式都成立，并且所有推导出的格子都是合法数字，那么题目要求的 10 条线就全部满足了。
取自由格子为
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
先算出
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
于是依赖格子为
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
最终四行分别是 \((1,0,2,1)\)、\((0,1,1,2)\)、\((2,1,1,0)\) 和 \((1,2,0,1)\)。这时四行、四列和两条对角线的和全都是 4。程序寻找的就是这种对象：先挑 9 个数字，再推出另外 7 个，最后只保留通过最后两条线检查的候选。
C++、Python 和 Java 实现都对这九个自由格子做嵌套枚举，但顺序是刻意安排的。选定 \(a,b,c,g,j\) 之后，\(m\) 就能立刻算出来；再选定 \(e\) 和 \(i\) 后，\(S\) 与 \(d\) 就确定了；选定 \(f\) 后，可以检查 \(h\) 和 \(n\)；最后选定 \(k\) 后，\(o,l,p\) 全部可得。
这种分阶段求值就是效率来源，因为大量候选会在最深层循环之前就被范围检查淘汰。
当所有依赖格子都算出并通过数字范围检查后，实现只需再验证第 4 行与第 4 列是否都等于 \(S\)。若答案为是，总计数就加一。
其中 C++ 实现还带有一个小规模校验：当允许的数字只有 \(\{0,1\}\) 时，正确答案应为 34。这个结果可以拿来确认优化后的枚举与小规模暴力完全一致。
朴素做法要检查全部 \(10^{16}\) 个 4x4 数字方格。现在的实现只显式枚举 9 个格子，因此一般上界是 \(O((d_{\max}+1)^9)\)；在原题中，这个粗上界是 \(10^9\)。
实际运行时间远小于这个数字，因为 \(m,d,h,n,o,l,p\) 的范围检查会提前剪掉大量分支。空间复杂度是 \(O(1)\)：除了少量整数变量和一个计数器之外，不需要额外的大型数据结构。
Обозначим строки таблицы 4x4 как \((a,b,c,d)\), \((e,f,g,h)\), \((i,j,k,l)\) и \((m,n,o,p)\). В каждой клетке стоит цифра от 0 до 9.
Нужно посчитать все заполнения, в которых суммы четырех строк, четырех столбцов и двух главных диагоналей совпадают и равны одному и тому же числу \(S\). То есть
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
Перебирать все \(10^{16}\) таблиц нельзя. Поэтому реализации не рассматривают 16 независимых клеток: они выбирают удобный набор свободных значений, выражают остальные из линейных условий и отбрасывают ветвь сразу, как только какой-либо вычисленный элемент перестает быть допустимой цифрой.
Главная идея состоит в линейном исключении. Из-за равенства сумм строки, столбцы и диагонали жестко связывают клетки между собой, так что многие значения можно восстановить из сравнительно малого числа свободных выборов.
Общее значение \(S\) не перебирается отдельно. Оно выводится из уже выбранных клеток. Поскольку каждая линия состоит из четырех цифр от 0 до 9, в любой допустимой конфигурации обязательно \(0 \le S \le 36\).
Важно не только то, какие уравнения используются, но и порядок их применения: каждая новая формула должна опираться лишь на уже известные величины.
Реализации перебирают девять клеток \(a,b,c,e,f,g,i,j,k\). Это не минимальная по числу параметров линейная модель, но очень удобная программно: все остальные клетки становятся простыми аффинными выражениями, а каждая отсечка сводится к проверке попадания в диапазон \([0,9]\).
Из первой строки и побочной диагонали получаем
$$a+b+c+d=S=d+g+j+m,$$
откуда после исключения \(d\) следует
$$m=a+b+c-g-j.$$
Как только \(m\) найдено, первый столбец сразу фиксирует общую сумму:
$$S=a+e+i+m.$$
Дальше зависимые значения восстанавливаются по одной строке, одному столбцу или одной диагонали:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
Каждое из этих чисел обязано быть цифрой из \([0,9]\). Если, например, \(m\) или \(o\) выходит за границы диапазона, дальнейшее продолжение этой ветви бессмысленно и она отбрасывается сразу.
После такой конструкции уже гарантированы восемь линий с суммой \(S\): первые три строки, первые три столбца и обе диагонали. Неохваченными остаются только четвертая строка и четвертый столбец.
Поэтому финал алгоритма состоит ровно из двух условий:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
Если оба равенства верны и все вычисленные клетки являются цифрами, то автоматически выполняются все десять ограничений задачи.
Выберем свободные клетки
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
Тогда
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
Зависимые клетки равны
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
Получается таблица со строками \((1,0,2,1)\), \((0,1,1,2)\), \((2,1,1,0)\) и \((1,2,0,1)\). У всех строк, столбцов и диагоналей сумма равна 4. Именно так и работает решение: выбрать девять цифр, восстановить семь остальных и принять конфигурацию только после двух последних проверок.
Реализации на C++, Python и Java используют вложенные циклы по девяти свободным клеткам, но порядок выбран не случайно. После выбора \(a,b,c,g,j\) уже вычисляется \(m\). После выбора \(e\) и \(i\) становятся известны \(S\) и \(d\). После выбора \(f\) можно проверить \(h\) и \(n\). После выбора \(k\) вычисляются \(o,l,p\).
Именно такая поэтапная схема и дает основной выигрыш по времени: огромное число кандидатов отсеивается еще до самых глубоких уровней перебора.
Когда все зависимые клетки вычислены и прошли проверки на диапазон, программа проверяет четвертую строку и четвертый столбец. Если обе суммы равны \(S\), общий счетчик увеличивается на единицу.
Кроме того, в реализации на C++ есть небольшой контрольный тест для случая \(d_{\max}=1\). В этом уменьшенном пространстве правильное число решений равно 34, и это удобно использовать как проверку корректности оптимизированного перебора.
Наивный алгоритм обязан был бы проверить все \(10^{16}\) таблиц. Реализованный подход явно перебирает только девять клеток, поэтому в общем виде его верхняя оценка равна \(O((d_{\max}+1)^9)\); для исходной задачи это грубая граница \(10^9\).
На практике время намного меньше, потому что формулы для \(m,d,h,n,o,l,p\) создают сильное раннее отсечение. Память равна \(O(1)\): кроме нескольких целочисленных переменных и счетчика, никакие крупные структуры не нужны.
لنرمز إلى صفوف الجدول 4x4 بالصفوف \((a,b,c,d)\) و\((e,f,g,h)\) و\((i,j,k,l)\) و\((m,n,o,p)\). كل خانة تحتوي رقمًا من 0 إلى 9.
المطلوب هو عدّ جميع التعبئات التي تكون فيها مجاميع الصفوف الأربعة، ومجاميع الأعمدة الأربعة، ومجموعا القطرين الرئيسيين، كلها مساوية للقيمة نفسها \(S\). أي إننا نريد
$$a+b+c+d=e+f+g+h=i+j+k+l=m+n+o+p=S,$$
$$a+e+i+m=b+f+j+n=c+g+k+o=d+h+l+p=S,$$
$$a+f+k+p=d+g+j+m=S.$$
فحص جميع الجداول الممكنة وعددها \(10^{16}\) غير عملي إطلاقًا. لذلك لا تتعامل التطبيقات مع 16 خانة مستقلة، بل تختار مجموعة صغيرة مناسبة من الخانات الحرة، ثم تستنتج الخانات الباقية من معادلات المجاميع، وتقصي الفرع فورًا إذا خرجت أي قيمة مشتقة عن مجال الأرقام المسموح.
جوهر الحل هو الحذف الخطي. فشروط تساوي المجاميع تجعل كثيرًا من الخانات غير حرة أصلًا، بل محددة بمجرد تثبيت مجموعة أصغر من القيم.
القيمة المشتركة \(S\) لا تُعدَّد مباشرة. بل تظهر تلقائيًا من الخانات التي جرى اختيارها أثناء البحث. وبما أن كل خط يتكون من أربعة أرقام بين 0 و9، فلا بد أن يكون \(0 \le S \le 36\) في أي حل صحيح.
المهم هنا ليس فقط ما المعادلات المستخدمة، بل أيضًا ترتيب استخدامها، بحيث تعتمد كل خانة جديدة على قيم سبق تحديدها بالفعل.
التطبيقات تعدّد القيم في الخانات التسع \(a,b,c,e,f,g,i,j,k\). هذا ليس أقل تمثيل ممكن من حيث عدد المعاملات، لكنه اختيار عملي جدًا: فكل الخانات المتبقية تصبح تعبيرات خطية بسيطة، وكل اختبار رفض يتحول إلى فحص نطاق لا أكثر.
بدمج الصف الأول مع القطر الثانوي نحصل على
$$a+b+c+d=S=d+g+j+m,$$
ومن ثم بعد حذف \(d\) نحصل على
$$m=a+b+c-g-j.$$
وبمجرد معرفة \(m\)، يحدد العمود الأول المجموع المشترك مباشرة:
$$S=a+e+i+m.$$
بعد تثبيت \(m\) و\(S\)، يمكن استخراج الخانات الأخرى واحدة بعد أخرى من صف أو عمود أو قطر:
$$d=S-a-b-c,$$
$$h=S-e-f-g,$$
$$n=S-b-f-j,$$
$$o=S-c-g-k,$$
$$l=S-i-j-k,$$
$$p=S-a-f-k.$$
ويجب أن تقع كل قيمة من هذه القيم داخل المجال \([0,9]\). فإذا خرجت قيمة مثل \(m\) أو \(p\) عن هذا المجال، فلا يمكن لهذا الفرع أن يؤدي إلى حل صحيح، ولذلك يُستبعد مباشرة.
بهذا البناء تصبح ثمانية خطوط مضمونة المجموع \(S\) تلقائيًا: الصفوف الثلاثة الأولى، والأعمدة الثلاثة الأولى، والقطران. والخطان الوحيدان اللذان لم يُفرضا صراحة بعد هما الصف الرابع والعمود الرابع.
ولهذا ينتهي البرنامج بهذين الشرطين فقط:
$$m+n+o+p=S,$$
$$d+h+l+p=S.$$
إذا تحقق الشرطان، وكانت كل الخانات المشتقة أرقامًا صحيحة ضمن النطاق، فإن جميع المجاميع العشرة المطلوبة في المسألة تكون قد تحققت.
لنأخذ الخانات الحرة التالية:
$$a=1,\ b=0,\ c=2,\ e=0,\ f=1,\ g=1,\ i=2,\ j=1,\ k=1.$$
عندها نحصل على
$$m=a+b+c-g-j=1+0+2-1-1=1,$$
$$S=a+e+i+m=1+0+2+1=4.$$
ثم تصبح الخانات التابعة
$$d=1,\quad h=2,\quad n=2,\quad o=0,\quad l=0,\quad p=1.$$
وهكذا تكون الصفوف هي \((1,0,2,1)\) و\((0,1,1,2)\) و\((2,1,1,0)\) و\((1,2,0,1)\). مجموع كل صف وكل عمود وكل قطر يساوي 4. هذا هو بالضبط النمط الذي تبحث عنه الشيفرة: نختار تسعة أرقام، نستنتج سبعة أخرى، ثم نقبل الحالة فقط إذا نجح الفحصان الأخيران أيضًا.
تستخدم تطبيقات C++ وPython وJava حلقات متداخلة على الخانات الحرة التسع، لكن بترتيب مقصود. بعد اختيار \(a,b,c,g,j\) تصبح \(m\) معروفة مباشرة. وبعد اختيار \(e\) و\(i\) نحصل على \(S\) و\(d\). وبعد اختيار \(f\) يمكن اختبار \(h\) و\(n\). وأخيرًا، بعد اختيار \(k\) تُحسب \(o,l,p\).
هذه البنية المرحلية هي سر الفعالية العملية، لأن عددًا كبيرًا من المرشحين يُستبعد قبل الوصول إلى أعمق مستوى من الحلقات.
بعد حساب جميع الخانات التابعة واجتيازها اختبارات النطاق، تتحقق الشيفرة من الصف الرابع والعمود الرابع. فإذا كان مجموع كل منهما يساوي \(S\)، يزيد العداد بمقدار واحد.
كما تتضمن نسخة C++ اختبارًا صغيرًا للحالة \(d_{\max}=1\). في هذا العالم المصغر يكون العدد الصحيح للحالات هو 34، وهو فحص مفيد للتأكد من أن التعداد المحسن يطابق القوة الغاشمة في مثال صغير يمكن التحقق منه مباشرة.
الطريقة الساذجة كانت ستفحص جميع الجداول الممكنة وعددها \(10^{16}\). أما الطريقة المطبقة فتعدّد صراحة تسع خانات فقط، ولذلك يكون الحد الأعلى العام هو \(O((d_{\max}+1)^9)\)، وفي المسألة الأصلية يعطي ذلك حدًا خشنًا مقداره \(10^9\).
الزمن الفعلي أقل بكثير من هذا الحد، لأن الصيغ الخاصة بـ \(m,d,h,n,o,l,p\) توفر تقليمًا مبكرًا قويًا جدًا. أما الذاكرة فهي \(O(1)\)، إذ لا توجد بنية بيانات كبيرة؛ فقط متغيرات صحيحة قليلة وعدّاد نهائي.