Problem 166: Criss Cross

Mathematical Development

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:

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:

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

The code uses meet-in-the-middle around the common sum $S$. For a fixed $S$, every row must be a 4-tuple of digits summing to $S$, so the first step is to generate that row catalog once. Instead of trying all four rows together, the program groups the top two rows and the bottom two rows separately.

For the top half, it records the four partial column sums and the two partial diagonal sums that those rows contribute. For the bottom half, it computes the complementary values needed so that the full columns and diagonals land exactly on $S$. A hash map from the top-half signature to its multiplicity then makes the final count a lookup problem: every bottom-half configuration asks how many matching top halves can complete it. This turns a much heavier brute-force search into a manageable join over summarized states.

Pseudocode

Initialize the total answer to zero.

For each possible common sum $S$ from 0 to 36:
    Generate every row of four digits whose entries add up to $S$.

    Enumerate all ordered pairs of top rows.
    For each pair, store in a map:
        the four column sums contributed so far,
        the two diagonal partial sums,
        and how many times this signature occurs.

    Enumerate all ordered pairs of bottom rows.
    For each pair, compute the complementary signature needed from the top half
    so that every column and both diagonals finish with total sum $S$.
    Add the number of matching top-half signatures from the map.

Return the accumulated total.

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

#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;
}

"""
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()