Problem 166: Criss Cross

Detailed mathematical approach

Problem Summary

Each of the \(16\) cells of a \(4\times4\) grid receives one of the digits \(0,1,\dots,9\), and digits may repeat. A filling is counted when the four rows, the four columns and the two diagonals, one from the top left to the bottom right corner and one from the top right to the bottom left corner, all have the same sum. This common sum is not prescribed and can be any number from \(0\) to \(36\), since each of these ten lines holds four digits. The statement shows a grid in which all ten lines add up to \(12\) and asks for the number of fillings with this property. ^[1] Such grids are magic squares in a wide sense: the classical ones of order \(4\) use each of the numbers \(1,\dots,16\) once, and work of Bernard Frénicle de Bessy, published in 1693, showed that there are exactly \(880\) of them up to rotations and reflections. ^[2] Here digits repeat, any common sum is allowed, and rotated or reflected grids count separately.

The whole solution in one sentence: the ten equal sums are linear equations, so once the nine cells of the top left \(3\times3\) block are chosen, the common sum and the other seven cells follow by subtraction; a search over these nine cells that abandons a branch as soon as a computed cell is not a digit, and finally checks the sum of the last row, counts every valid grid exactly once in about \(1.4\cdot10^8\) innermost steps instead of \(10^{16}\) fillings.

Mathematical Approach

We name the cells, count small cases, and then use the equations to compute most cells from the others; two identities show which tests are really needed.

1. Cells, lines and the common sum

We name the cells row by row:

$$\begin{matrix}a&b&c&d\\e&f&g&h\\i&j&k&l\\m&n&o&p\end{matrix}$$

The ten lines are the rows \(a+b+c+d\), \(e+f+g+h\), \(i+j+k+l\) and \(m+n+o+p\), the columns \(a+e+i+m\), \(b+f+j+n\), \(c+g+k+o\) and \(d+h+l+p\), and the diagonals \(a+f+k+p\) and \(d+g+j+m\). A filling is valid when all ten sums are equal, and we call their common value \(S\). In the grid of the statement every one of them is \(12\); for instance, the first column gives \(6+5+0+1=12\) and the second diagonal \(0+4+7+1=12\). Testing all \(10^{16}\) fillings is out of the question: at \(10^9\) fillings per second it would take about \(116\) days.

2. The smallest cases

Write \(t\) for the largest allowed digit, so the problem has \(t=9\). For \(t=0\) only the grid of zeros exists. For \(t=1\) the common sum is one of \(0,1,2,3,4\), and a search over all \(2^{16}=65536\) fillings finds \(1\), \(8\), \(16\), \(8\) and \(1\) valid grids for these sums, \(34\) in total. Some of these numbers can be checked by hand. For \(S=0\) and \(S=4\) only the grid of zeros and the grid of ones remain. For \(S=1\) every row and every column holds exactly one \(1\), so the ones form one of the \(4!=24\) permutation patterns, and a valid pattern has exactly one \(1\) on each diagonal. The \(1\) on the main diagonal can stand in \(4\) places, and the other three ones must avoid that diagonal, which leaves \(2\) ways: with the diagonal \(1\) in \(a\), the other ones are \(g,l,n\) or \(h,j,o\). Each of these \(8\) patterns has exactly one \(1\) on the other diagonal too, \(g\) or \(j\) in the examples, so \(8\) grids have \(S=1\).

Replacing every digit \(x\) by \(t-x\) turns a valid grid with sum \(S\) into one with sum \(4t-S\), so the counts for \(S\) and \(4t-S\) agree, like the two counts \(8\) above. For \(t=2\) a search over all \(3^{16}=43\,046\,721\) fillings gives \(1, 8, 48, 144, 219, 144, 48, 8, 1\) valid grids for \(S=0,1,\dots,8\), \(621\) in total, and for \(t=3\) the \(4^{16}\) fillings contain \(5400\) valid grids. Ten equations tie the cells together, so the counts stay tiny.

3. Seven cells follow from nine

Every condition is a linear equation: a sum of cells equals \(S\). A cell that is the only unknown on its line is found by subtraction; if \(S\) is known, the first row gives \(d=S-a-b-c\). But \(S\) is not given. The way around this is to compare two lines that share a cell: the first row and the second diagonal both contain \(d\),

$$a+b+c+d=S=d+g+j+m,$$

and cancelling \(d\) gives \(m\) without knowing \(S\). Then the first column is complete and yields \(S\). So we choose the nine cells \(a,b,c,e,f,g,i,j,k\) of the top left \(3\times3\) block and compute first

$$\begin{aligned}m&=a+b+c-g-j,\\S&=a+e+i+m,\end{aligned}$$

then \(d=S-a-b-c\), \(h=S-e-f-g\) and \(l=S-i-j-k\) from the first three rows, \(n=S-b-f-j\) and \(o=S-c-g-k\) from the second and third columns, and \(p=S-a-f-k\) from the main diagonal. These six lines and the first column, which defined \(S\), have the sum \(S\) by construction, and so does the second diagonal, which defined \(m\): substituting \(d\) and \(m\) into \(d+g+j+m\), everything except \(S\) cancels. Eight of the ten lines are thus automatic. It remains to test that the seven computed cells are digits and that the last row and the last column have the sum \(S\).

4. The last column comes for free

Adding the four rows and adding the four columns both give the total of all sixteen cells. If the first three rows and the first three columns have the sum \(S\), the last row and the last column both equal this total minus \(3S\), so their sums always agree, and one test is enough. In the language of linear algebra, the ten equations are dependent, since the four row equations minus the four column equations give \(0=0\); Section 6 shows that this is their only dependence.

5. The last row is a condition on the centre

Write \(R=m+n+o+p\) for the sum of the last row. Substituting the formulas of Section 3 gives

$$\begin{aligned}R&=(a+b+c-g-j)\\&\quad+(S-b-f-j)\\&\quad+(S-c-g-k)\\&\quad+(S-a-f-k)\\&=3S-2(f+g+j+k).\end{aligned}$$

So the last row has the sum \(S\) exactly when the four centre cells have it:

$$f+g+j+k=S.$$

Two consequences matter. First, once the other eight cells of the block are fixed, at most one value of \(k\) can pass, namely \(k=S-f-g-j\), and only if it is a digit. Second, every valid grid has the sum \(S\) in its four centre cells, and since the two diagonals together consist of the centre and the four corners, the corners add up to \(2S-S=S\) as well. In the example the centre gives \(0+4+7+1=12\) and the corners \(6+0+1+5=12\). Dürer's magic square of 1514 shows the same with its sum \(34\): its centre cells \(10,11,6,7\) and its corners \(16,13,4,1\) both add up to \(34\). ^[2]

6. Eight cells determine the grid

By Sections 3 to 5, a valid grid is determined by its eight cells \(a,b,c,e,f,g,i,j\): they give \(m\) and \(S\), then \(k=S-f-g-j\), then the other six cells. Conversely, any numbers chosen for these eight cells give, by the same formulas, a grid whose ten lines all have the sum \(S\), and it is a valid filling exactly when all sixteen entries are digits. Since the formulas are linear, the solutions of the ten equations in the sixteen cells and \(S\) form a space of dimension \(8\), so by the rank–nullity theorem these equations in \(17\) unknowns have rank \(17-8=9\): every dependence among them is a multiple of the relation of Section 4. ^[4] In particular there are at most \(10^8\) valid grids. The published programs still loop over \(k\) and test the last row, which gives the same count with ten times as many innermost steps.

7. Every valid grid is counted exactly once

A valid grid \(G\) satisfies all ten equations, so its seven outer cells are given by the formulas of Section 3; they are digits, and its last row has the sum \(S\). Hence the search accepts \(G\) when its loops reach the nine block cells of \(G\), and nothing else for these values, because they determine the other cells. Conversely, nine digits for which the seven computed cells are digits and the last row has the sum \(S\) form a valid grid by Sections 3 and 4. So the search counts every valid grid exactly once.

8. Testing as early as possible

The search chooses the nine digits not in reading order but so that each computed cell is tested as soon as the cells it depends on are fixed, and a failed test abandons the whole branch. This is backtracking, in which a single test eliminates every completion of a partial choice. ^[5]

• after \(a,b,c,g,j\): compute \(m\) and test it;
• after \(e,i\): compute \(S\) and \(d\), and test \(d\);
• after \(f\): compute and test \(h\) and \(n\);
• after \(k\): compute and test \(o\), \(l\) and \(p\), then test the last row.

For instance, \(a=b=c=0\) and \(g=1\) give \(m=-1-j\lt0\) for every \(j\), so ten tests dispose of all \(10^5\) choices of \(j,e,i,f,k\) behind this branch. A version of the search with counters added shows the effect for \(t=9\): \(55\,252\) of the \(10^5\) choices of \(a,b,c,g,j\) give a digit \(m\); \(3\,458\,872\) of their \(5\,525\,200\) extensions by \(e,i\) give a digit \(d\); and \(13\,885\,182\) of the next \(34\,588\,720\) extensions by \(f\) give digits \(h\) and \(n\). The loop over \(k\) therefore runs \(138\,851\,820\) times, about \(14\) percent of the \(10^9\) steps of nine unpruned loops, and \(47\,177\,956\) of these steps reach the test of the last row, which by Section 5 accepts at most one \(k\) in each branch.

9. A worked example

We follow the search to the grid of the statement. The digits \(a=6\), \(b=3\), \(c=3\), \(g=4\) and \(j=7\) give \(m=6+3+3-4-7=1\). Then \(e=5\) and \(i=0\) give \(S=6+5+0+1=12\) and \(d=12-6-3-3=0\), and \(f=0\) gives \(h=12-5-0-4=3\) and \(n=12-3-0-7=2\). In the last loop \(o=5-k\), \(l=5-k\) and \(p=6-k\), so \(k=0,1,\dots,5\) give digits, and the last row has the sum

$$\begin{aligned}R&=1+2+(5-k)+(6-k)\\&=14-2k,\end{aligned}$$

which is \(12\) only for \(k=1\), exactly when the centre \(0+4+7+k\) reaches \(12\), as Section 5 predicts. With \(k=1\) the computed cells are \(o=4\), \(l=4\) and \(p=5\), and we obtain the grid of the statement. The last column, \(0+3+(5-k)+(6-k)\), is also \(14-2k\) for every \(k\), as Section 4 says.

How the Code Works

The C++ program ^[6] keeps the count in i64, an alias of long long, and every cell in an int. main first calls parse_arguments: --skip-checkpoints turns the check off, and --max-digit=t, read by parse_int_after_prefix as a nonempty string of decimal digits, replaces the largest digit \(9\) by \(t\). Any other argument ends the program with exit status \(1\), and so does a final value outside \(0\le t\le9\); only the last of several --max-digit options counts. The digits are accumulated in an int before that test, so a very long digit string overflows, which is undefined behaviour in C++; in a test build --max-digit=4294967301 was accepted as \(t=5\). Next, run_checkpoints requires solve(1) to return \(34\), the count of Section 2, and otherwise the program stops with exit status \(2\). Finally main prints solve(max_digit).

solve(dmax) is the search of Section 8: nine nested loops over a, b, c, g, j, then e, i, then f, then k, each from \(0\) to dmax. After the fifth loop it computes m and leaves the branch with continue unless \(0\le m\le t\); after the seventh it computes S and d, after the eighth h and n, and inside the ninth o, l and p, each with its formula from Section 3 and the same range test. A surviving candidate is tested with m + n + o + p != S and then with d + h + l + p != S; by Section 4 the second test cannot fail at that point, and the counting run of Section 8 saw it reject nothing. Each remaining candidate adds one to answer. The file also defines brute_small, a direct search with sixteen loops that tests all ten lines, but nothing calls it, and a compiler with warnings enabled reports it as unused.

The Python and Java programs use the same loop order, formulas and final tests, with the largest digit fixed at \(9\), and have no command-line options and no self-test. Python's integers have unlimited precision; its solve returns the count as a string, which the main block prints. Java runs the loops in main, with int cells and a long counter. The arithmetic of the search cannot overflow in any of the three: every value it computes lies between \(-18\) and \(36\), and by Section 6 the count is at most \(10^8\), which even a 32-bit integer holds.

Complexity and Verification

With largest digit \(t\), nine unpruned loops would make \((t+1)^9\) innermost steps; the tests of Section 8 reduce this to \(138\,851\,820\) steps of the \(k\) loop for \(t=9\), each a few additions and comparisons, and the memory is a handful of integers. On an Apple M4 Max, with GCC 16 at -O2, OpenJDK 17 and Python 3.11, the C++ program took \(0.22\) s including its check, the Java program about \(0.3\) s and the Python program about \(11\) s, start-up included. Computing \(k=S-f-g-j\) instead of looping over it, as Section 6 allows, would make \(13\,885\,182\) candidate evaluations, a tenth of these steps and at most \((t+1)^8\) in general. The programs use neither this shortcut nor the symmetry \(x\mapsto t-x\).

The only check in the published programs is the C++ test of the count \(34\) for \(t=1\). For this article, exhaustive searches over all \(2^{16}\), \(3^{16}\) and \(4^{16}\) fillings gave \(34\), \(621\) and \(5400\) valid grids for \(t=1,2,3\), the values that the C++ program prints with --max-digit. An independent count by meeting in the middle splits the grid into its top two and bottom two rows and, for each common sum, matches the halves by their four column sums and their shares of the two diagonals; it agreed with the C++ program for every \(t\le8\), for example with \(30277\) grids for \(t=4\), and with all three programs for \(t=9\). So did a count with eight loops and \(k=S-f-g-j\) that checked all ten lines of every grid it found. Gaussian elimination over the rationals confirmed the rank \(9\) of Section 6, ^[3] and all \(621\) grids for \(t=2\) have the centre and corner sums of Section 5. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The formulas for the seven computed cells, the centre condition, the proof that every grid is counted once and the operation counts are derived explicitly in this article.

1. Project Euler 166 — Criss Cross. The official statement asks in how many ways a 4 × 4 grid can be filled with digits from 0 to 9 so that each row, each column and both diagonals have the same sum, and shows an example grid in which all these sums are 12.
2. Wikipedia — Magic square. In a magic square all rows, all columns and both main diagonals have the same sum, the magic constant, which is 34 for a normal square of order 4, made of the numbers 1 to 16. Treatises of Frénicle de Bessy, published in 1693, showed that there are exactly 880 magic squares of order four up to rotations and reflections, and in Dürer's square of 1514 the sum 34 also appears in the four centre cells and in the corners.
3. Wikipedia — Gaussian elimination. Row reduction brings a matrix to row echelon form and also computes its rank, the number of nonzero rows of that form; the verification applies it to the ten line equations.
4. Wikipedia — Rank–nullity theorem. For a matrix with n columns, the rank plus the nullity equals n, where the nullity is the dimension of the solution space of the homogeneous system; Section 6 obtains the rank 17 − 8 = 9 from a solution space of dimension 8.
5. Wikipedia — Backtracking. A backtracking search builds candidates step by step and abandons a partial candidate as soon as it cannot be completed to a valid solution, so the whole subtree below it is skipped and a single test eliminates many candidates.
6. C++ — Euler166.cpp. The linked immutable C++ revision contains solve, the unused brute_small, the option parser and the check in run_checkpoints. It is the implementation record for this article.