Project Euler

Criss Cross

A 4 x 4 grid is filled with digits d (0 <= d <= 9), and we require that every row, every column, and both main diagonals all share the same sum S. How many such grids exist?

Source sync Apr 19, 2026

Problem #0166

Level Level 07

Solved By 4,733

Languages C++, Python

Answer 7130034

Length 399 words

optimizationlinear_algebrabrute_force

A $4 \times 4$ grid is filled with digits $d$, $0 \le d \le 9$. \[ \begin {matrix} 6 & 3 & 3 & 0\\ 5 & 0 & 4 & 3\\ 0 & 7 & 1 & 4\\ 1 & 2 & 4 & 5 \end {matrix} \] the sum of each row and each column has the value $12$. Moreover the sum of each diagonal is also $12$.

In how many ways can you fill a $4 \times 4$ grid with the digits $d$, $0 \le d \le 9$ so that each row, each column, and both diagonals have the same sum?

Problem 166: Criss Cross

Mathematical Foundation

Definition. A semi-magic square of order 4 over digits is a $4 \times 4$ matrix $(a_{ij})$ with $a_{ij} \in \{0, 1, \ldots, 9\}$ such that all row sums, column sums, and both main diagonal sums equal a common value $S$ .

Theorem 1 (Constraint rank). The 10 linear constraints (4 rows + 4 columns + 2 diagonals summing to $S$ ) have rank 7 over $\mathbb{Q}$ , leaving 9 free variables among the 16 entries.

Proof. Write the grid as:

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

The 4 row-sum equations give: $a+b+c+d = e+f+g+h = i+j+k+l = m+n+o+p = S$ . The 4 column-sum equations give: $a+e+i+m = b+f+j+n = c+g+k+o = d+h+l+p = S$ . The 2 diagonal equations: $a+f+k+p = d+g+j+m = S$ .

Summing all 4 row equations gives the same total ( $4S$ ) as summing all 4 column equations, so these 8 equations are not independent. The row equations determine 3 independent constraints (given $S$ ). The column equations add 3 more (since one column sum is implied by the other three plus the total). The diagonal equations add 1 more (since the sum of both diagonals relates to the row/column sums). Total independent constraints: $3 + 3 + 1 = 7$ (plus $S$ itself as a parameter). $\square$

Theorem 2 (Fourth row determination). Given rows 1—3 each summing to $S$ , the fourth row is uniquely determined by the column-sum constraints:

m = S - a - e - i, \quad n = S - b - f - j, \quad o = S - c - g - k, \quad p = S - d - h - l

Moreover, $m + n + o + p = S$ is automatically satisfied.

Proof. Each fourth-row entry is forced by the corresponding column sum equaling $S$ . For the row-sum check: $m+n+o+p = 4S - (a+b+c+d) - (e+f+g+h) - (i+j+k+l) = 4S - 3S = S$ . $\square$

Lemma 1. The magic sum $S$ ranges from 0 to 36, since each row of four digits in $\{0,\ldots,9\}$ has sum between 0 and 36.

Proof. Minimum: all zeros, sum = 0. Maximum: all nines, sum = 36. $\square$

Lemma 2 (Diagonal constraints as filter). After determining the fourth row, the two diagonal conditions $a + f + k + p = S$ and $d + g + j + m = S$ serve as a filter, rejecting configurations that fail either constraint.

Proof. These are the only constraints not yet enforced by the row-sum and column-sum conditions. $\square$

Editorial

Optimization: precompute tuples per sum $S$ . Use early termination: after fixing rows 1 and 2, check partial diagonal feasibility before enumerating row 3. Split enumeration with meet-in-the-middle on top-two vs. bottom-two rows. We generate all 4-tuples of digits summing to S. We then determine Row 4. Finally, check digits in range.

Pseudocode

Generate all 4-tuples of digits summing to S
Determine Row 4
Check digits in range
Check diagonals

Complexity Analysis

Time: Let $T(S)$ = number of 4-tuples of digits summing to $S$ . Naively $O\bigl(\sum_S T(S)^3\bigr)$ . Since $\sum_S T(S) = 10^4$ and $T(S) \leq 220$ (for $S = 18$ ), the worst case is $O(37 \cdot 220^3) \approx 3.9 \times 10^8$ , manageable with pruning. With meet-in-the-middle, this drops to $O\bigl(\sum_S T(S)^2 \cdot \log T(S)\bigr)$ .
Space: $O\bigl(\max_S T(S)^2\bigr)$ for meet-in-the-middle hash tables, or $O(T(S))$ for the tuple lists.

Answer

\boxed{7130034}

C++ project_euler/problem_166/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Problem 166: Count 4x4 grids of digits 0-9 where all rows, columns,
    // and both diagonals have the same sum S.
    //
    // Grid:
    // a b c d
    // e f g h
    // i j k l
    // m n o p
    //
    // Given rows 1-3, row 4 is determined by column constraints.
    // We check validity and diagonal constraints.
    //
    // Optimization: for each S, enumerate pairs (row1, row2) as "top half"
    // and store in a map keyed by partial column sums and partial diagonal info.
    // Then enumerate (row3) and derive row4, check constraints.
    //
    // Actually, a direct enumeration with pruning is fast enough.

    long long total = 0;

    for(int S = 0; S <= 36; S++){
        // Generate all 4-tuples of digits summing to S
        vector<array<int,4>> tuples;
        for(int x0 = 0; x0 <= 9 && x0 <= S; x0++)
            for(int x1 = 0; x1 <= 9 && x0+x1 <= S; x1++)
                for(int x2 = 0; x2 <= 9 && x0+x1+x2 <= S; x2++){
                    int x3 = S - x0 - x1 - x2;
                    if(x3 >= 0 && x3 <= 9)
                        tuples.push_back({x0,x1,x2,x3});
                }

        int NT = tuples.size();

        // For meet-in-the-middle: enumerate top 2 rows, store by
        // (col0_partial, col1_partial, col2_partial, col3_partial, diag0_partial, diag1_partial)
        // where diag0 = a+f, diag1 = d+g
        // Key: (c0, c1, c2, c3, d0, d1) where each in [0..18]
        // Use a flat map: key = c0*19^5 + c1*19^4 + c2*19^3 + c3*19^2 + d0*19 + d1

        unordered_map<long long, int> topmap;
        topmap.reserve(NT * NT / 2);

        for(int r1 = 0; r1 < NT; r1++){
            auto &t1 = tuples[r1];
            for(int r2 = 0; r2 < NT; r2++){
                auto &t2 = tuples[r2];
                int c0 = t1[0]+t2[0], c1 = t1[1]+t2[1];
                int c2 = t1[2]+t2[2], c3 = t1[3]+t2[3];
                int d0 = t1[0]+t2[1]; // a + f
                int d1 = t1[3]+t2[2]; // d + g
                long long key = (((((long long)c0*19+c1)*19+c2)*19+c3)*19+d0)*19+d1;
                topmap[key]++;
            }
        }

        // Enumerate bottom 2 rows (row3=i,j,k,l and row4=m,n,o,p)
        // Column constraints: c0+i+m=S => i+m = S-c0, etc.
        // Diag constraints: diag0: k+p, need a+f+k+p=S => k+p = S-d0
        //                   diag1: j+m, need d+g+j+m=S => j+m = S-d1
        // So we need:
        //   bottom_c0 = i+m = S - top_c0
        //   bottom_c1 = j+n = S - top_c1
        //   bottom_c2 = k+o = S - top_c2
        //   bottom_c3 = l+p = S - top_c3
        //   bottom_d0 = k+p = S - top_d0
        //   bottom_d1 = j+m = S - top_d1

        for(int r3 = 0; r3 < NT; r3++){
            auto &t3 = tuples[r3];
            for(int r4 = 0; r4 < NT; r4++){
                auto &t4 = tuples[r4];
                int bc0 = t3[0]+t4[0], bc1 = t3[1]+t4[1];
                int bc2 = t3[2]+t4[2], bc3 = t3[3]+t4[3];
                int bd0 = t3[2]+t4[3]; // k + p
                int bd1 = t3[1]+t4[0]; // j + m

                // We need top values: tc0 = S-bc0, etc.
                int tc0 = S-bc0, tc1 = S-bc1, tc2 = S-bc2, tc3 = S-bc3;
                int td0 = S-bd0, td1 = S-bd1;
                if(tc0<0||tc1<0||tc2<0||tc3<0||td0<0||td1<0) continue;
                if(tc0>18||tc1>18||tc2>18||tc3>18||td0>18||td1>18) continue;

                long long key = (((((long long)tc0*19+tc1)*19+tc2)*19+tc3)*19+td0)*19+td1;
                auto it = topmap.find(key);
                if(it != topmap.end())
                    total += it->second;
            }
        }
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_166/solution.py

"""
Problem 166: Criss Cross

Count 4x4 grids of digits 0-9 where all rows, columns, and both diagonals
have the same sum S.

Meet-in-the-middle: enumerate top 2 rows and bottom 2 rows separately,
then match on column sums and diagonal partial sums.
"""

from collections import defaultdict

def solve():
    total = 0

    for S in range(37):
        # Generate all 4-tuples of digits summing to S
        tuples = []
        for a in range(min(10, S+1)):
            for b in range(min(10, S-a+1)):
                for c in range(min(10, S-a-b+1)):
                    d = S - a - b - c
                    if 0 <= d <= 9:
                        tuples.append((a, b, c, d))

        # Top half: rows 1 and 2 (a,b,c,d) and (e,f,g,h)
        # Track: col sums (a+e, b+f, c+g, d+h), diag partials (a+f, d+g)
        top_map = defaultdict(int)
        for t1 in tuples:
            for t2 in tuples:
                key = (
                    t1[0]+t2[0], t1[1]+t2[1], t1[2]+t2[2], t1[3]+t2[3],
                    t1[0]+t2[1],  # a + f
                    t1[3]+t2[2],  # d + g
                )
                top_map[key] += 1

        # Bottom half: rows 3 and 4 (i,j,k,l) and (m,n,o,p)
        # Need: col sums i+m = S - top_c0, etc.
        # Diag: k+p = S - (a+f), j+m = S - (d+g)
        for t3 in tuples:
            for t4 in tuples:
                bc0 = t3[0]+t4[0]
                bc1 = t3[1]+t4[1]
                bc2 = t3[2]+t4[2]
                bc3 = t3[3]+t4[3]
                bd0 = t3[2]+t4[3]  # k + p
                bd1 = t3[1]+t4[0]  # j + m

                needed = (S-bc0, S-bc1, S-bc2, S-bc3, S-bd0, S-bd1)
                if any(v < 0 or v > 18 for v in needed):
                    continue
                total += top_map.get(needed, 0)

    print(total)

solve()