Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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 4x4 line-sum system

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.

A convenient set of free cells

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.$

Solving the remaining seven cells

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.

Why only two final checks remain

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.

Worked example

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.

How the Code Works

Enumeration order and early pruning

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.

Final validation and counting

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.

Complexity Analysis

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.

Footnotes and References

1. Project Euler problem 166: https://projecteuler.net/problem=166
2. Magic square: Wikipedia - Magic square
3. Constraint satisfaction problem: Wikipedia - Constraint satisfaction problem
4. Gaussian elimination: Wikipedia - Gaussian elimination
5. System of linear equations: Wikipedia - System of linear equations