TimesSquare Programming Puzzle - Part 1?

2026-04-23

TimesSquare is a programming puzzle created by Dennis Shasha and published in the April 2026 issue of Communications of the ACM. The puzzle requires deriving missing digit values within a square matrix, given, at least, the main diagonal, the sum of all digits within the matrix, and a value called the RowCol which is a function of all the digits. The challenge is to find a sub-exponential time algorithm. In this article, we describe the puzzle, present a dataset of example problems we developed for benchmark and testing purposes, and provide TypeScript code for a backtracking algorithm that finds solutions but fails to meet the performance goals.

TimesSquare Problem Description

A TimesSquare is a square matrix, \(N\times N\), where each value in the matrix is a digit between 1 and 9 inclusive. An unsolved TimesSquare instance will have one or more non-main diagonal values blank. In addition to the matrix, \(a\), the solver is given two values: the sum, \(S\), of all digits (including the unknown values), and the RowCol, \(R_C\). The RowCol is defined as the sum of the product of row values minus the sum of the product of the column values, or more formally:

\[ S = \sum\limits_{i}^{N}\sum\limits_{j}^{N}a_{ij} \]

\[ R_C = \sum\limits_{i}^{N}\prod\limits_{j}^{N}a_{ij} - \sum\limits_{j}^{N}\prod\limits_{i}^{N}a_{ij} \]

NB: In the original article, the 5x5 example should have a fully-defined main diagonal rather than a missing value at the 2,2 position. Also, the solution given to the 4x4 and 5x5 examples are non-unique; there are 15 and 12,462 solutions, respectively.

The Upstart challenge:

Given a TimesSquare of size N×N, the RowCol and the sum of digits and the diagonals, can you design a sub-exponential algorithm to fill in at least one solution?

2x2 Example

As an example, consider this 2x2 unsolved TimesSquare:

\[ \begin{array}{cc} 7 & a_{12} \\ a_{21} & 1 \end{array} \]

For this example, \(S\) is 18 and \(R_C\) is 12.

The two missing values, \(a_{12}\) and \(a_{21}\) must sum to 10 since the two known values sum to 8 and \(S\) is 18.

For the RowCol:

\[ R_C = 12 = (7a_{12} + a{21}) - (7a_{21} + a_{12}) = 6a_{12} - 6a_{21} \]

Combining the two equations, we have:

\[ \begin{array}{c} a_{12} + a_{21} = 10 \\ a_{12} - a_{21} = 2 \end{array} \]

This yields the solution:

\[ \begin{array}{cc} 7 & 6 \\ 4 & 1 \end{array} \]

While the 2x2 cases can be solved algebraically, larger \(N\) requires some innovation.

Problems Dataset

For my bench marking / testing purposes, I’ve developed a dataset of 100 example problems and solutions for 2x2, 3x3, 4x4, and 5x5 matrix sizes. The 2x2 cases all have two unknown values, while the other cases were targeted for approximately 40% unknown values (non main diagonal). Matrices were populated randomly using a uniform distribution for the digits. The 2x2 cases include one duplicate problem, but all others are distinct.

Download Links

Dataset Format

The dataset is in JSON format. At the top-level, the file contains an object with five string keys, each an array with 100 elements:

{
	"2x2": [...],
	"3x3": [...],
	"4x4": [...],
	"5x5": [...]
}

Each element in the arrays is an object with the following form:

{
	"problem": {
		"sum": INTEGER,
		"rowcol": INTEGER,
		"N": INTEGER,
		"grid": MaybeDigit[]
	},
	"sample_solution": {
		"sum": INTEGER,
		"rowcol": INTEGER,
		"N": INTEGER,
		"grid": Digit[]	
	}
}

The grid is an array, of length \(N^2\). A Digit is a number between 1 and 9 inclusive, while MaybeDigit is a number or the literal null value. Matrices are represented in a flattened, row-major order (i.e., in the 2x2 case: [1,1 1,2 2,1 2,2]).

Code

The following code is in TypeScript. At the top-level, we define the types for the matrix values using a discriminated union. The puzzle does not allow zero as a digit value. For a missing value, we use undefined. JavaScript (upon which TypeScript is based) includes both undefined and null values. The two values are distinct (i.e. null !=== undefined). Since a null is supposed to represent a missing object value, while undefined is a missing value, we consider undefined as the pedantic correct choice between the two options. However, since JSON does not include undefined as a value, only null, this choice necessitates swapping null values with undefined values when the dataset is read.

The isDigit function is a type predicate. The TypeScript compiler can use type predicates as part of the type verification process. Because JavaScript has short-circuit evaluation, this function could be simplified to return Number.isInteger(d) && d >= 1 && d <= 9. However, the compiler isn’t yet smart enough to recognize Number.isInteger(d) will short-circuit to false if d is undefined, so complains that d may be undefined in the d >= 1 and d <= 9 expressions. Hence, we check for undefined explicitly.

export type Digit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;
export type MaybeDigit = undefined | Digit;

function isDigit(d: MaybeDigit | number): d is Digit {
    if (d === undefined) {
        return false;
    } else {
        return Number.isInteger(d) && d >= 1 && d <= 9;
    }
}

Leveraging the above types, we can represent a TimesSquare solution using a class. The class has three fields: the matrix (grid), the sum, and the rowcol value. We use the type predicate to filter the input grid within the constructor, but we still need as Digit[] to convince the compiler that we are filtering to the correct type. Alternatively, we could test the array using grid.every(isDigit). The constructor verifies that the matrix is square in size and that the actual sum and rowcol values match the expected values.

export class SolvedTimesSquare {
    /**
     * Square grid.
     */
    readonly grid: Digit[]

    /**
     * Sum of digits in the grid.
     */
    readonly sum: number

    /**
     * Sum of the products of the row values less the sum of the products of the column values.
     */
    readonly rowcol: number

    constructor(grid: Digit[] | number[], sum: number, rowcol: number) {
        this.grid = grid.filter(isDigit) as Digit[];
        if (grid.length !== this.grid.length) {
            throw new Error('entire grid must be defined');
        }
        this.sum = sum;
        this.rowcol = rowcol;

        if (!isSquare(this.grid)) {
            throw new Error('grid must be a square matrix NxN');
        }
        const actualSum: number = this.grid.reduce((left, right) => left + right, 0);
        if (this.sum !== actualSum) {
            throw new Error(`expected sum of digits ${this.sum} does not equal actual sum ${actualSum}`);
        }
        const actualRowCol: number = rowCol(this.grid);
        if (this.rowcol !== actualRowCol) {
            throw new Error(`expected rowcol ${this.rowcol} does not equal actual rowcol ${actualRowCol}`);
        }
    }
}

An unsolved TimesSquare is represented similarly. Since values may be missing, we use MaybeDigit instead of Digit. The sum and rowcol values are always given. For verifications, we verify the matrix is square and that all the diagonal values are defined.

export class UnsolvedTimesSquare {
    /**
     * Square grid. The main diagonal must be defined.
     */
    readonly grid: MaybeDigit[]

    /**
     * Sum of digits in the grid.
     */
    readonly sum: number

    /**
     * Sum of the products of the row values less the sum of the products of the column values.
     */
    readonly rowcol: number

    /**
     * Length of one side of the grid
     */
    readonly N: number

    constructor(grid: MaybeDigit[], sum: number, rowcol: number) {
        this.grid = grid;
        this.sum = sum;
        this.rowcol = rowcol;
        this.N = Math.sqrt(this.grid.length);

        if (!isSquare(this.grid)) {
            throw new Error("grid must be a square matrix NxN");
        }
        if (!isDiagonalDefined(this.grid)) {
            throw new Error("grid's main diagonal must be defined");
        }
    }
    
    /**
     * Find at most limit solutions
     * @param limit the maximum size of the returned array; must be positive integer
     */
    solveAtMost(limit: number): SolvedTimesSquare[] {
        // described below
    }
}

Since Typescript numbers are floating-point values, we could add further verifications using Number.isInteger or Number.isSafeInteger.

Backtracking Algorithm and Results

TimesSquare is an example of a constraint satisfaction problem. For a \(N \times N\) matrix, there are, at most, \(N^2 - N\) variables, each of which is constrained to the domain \( { 1, 2, …, 8, 9 } \), and the variables are further constrained by the sum and rowcol values. Backtracking is a common approach for solving constraint satisfaction problems.

Backtracking is an algorithmic approach which generates a set of potential sub-solutions or candidates at each step. The algorithm recursively chooses one of the candidates and then attempts to solve the smaller problem. If the current candidate is determined to be invalid, the algorithm will return to the parent and check the next candidate. Following this tree-search pattern, a solution will either be discovered or will exhaustively attempt all solutions and find nothing.

We implemented a backtracking algorithm for TimesSquare. The entrypoint is solveAtMost which takes a limit argument. In the case where we only want one solution, we pass 1 as the limit. (It is possible an UnsolvedTimesSquare is fully populated, but we ignore checking for that possibility for readability.)

    /**
     * Find at most limit solutions
     * @param limit the maximum size of the returned array; must be positive integer
     */
    solveAtMost(limit: number): SolvedTimesSquare[] {
        return this.solveBacktrack(limit);
    }

The private method solveBacktrack calculates some values that will be used by the recursive function solveBacktrackRec. The knownSum variable is the sum of all the defined values in the matrix, while unknownSum is the expected sum for the undefined variables. Similarly, unknownCount is the number of variables or missing values in the matrix. We will decrement unknownSum and unknownCount as we apply additional candidates to the grid.

    private solveBacktrack(limit: number): SolvedTimesSquare[] {
        const knownSum = this.grid.filter(isDigit).reduce((sum, v) => sum + v, 0);
        const unknownSum = this.sum - knownSum;
        const unknownCount = this.grid.filter(v => !isDigit(v)).reduce((sum) => sum + 1, 0);

        return this.solveBacktrackRec(unknownSum, unknownCount, this.grid, limit);
    }

The recursive function solveBacktrackRec has separate paths if it is placing the potentially final candidate in a solution versus if there are more candidates. In the former case, the candidate will equal the current unknownSum, if unknownSum is a valid Digit. In addition, the candidate must also match the expected rowcol value. If both tests succeed, we return a solution as a SolvedTimesSquare instance. (There is a “defense-in-depth” technique in play, as the SolvedTimesSquare constructor verifies the same constraints. However, the constructor raises an exception on failure, while the code below avoids that cost. Since this is still code duplication, we could factor the calls out.)

In the case where there are more than one candidates to go, the code finds the next variable (undefined value). The code handles the case where the findIndex does not find the expected value, but outside development or dirty inputs, this should be a “can’t happen” case. The code generates the list of candidate possibilites which are the digits from 1 to 9, minus any digits that are impossible given the remaining sum of undefined variables. For example, if unknownCount is 2 and unknownSum is 5, then the list of possibilites is 1, 2, 3, or 4, since the next and last candidate must be at least 1.

Each possible candidate is checked in turn by placing it on a newly created grid and recursively checking the next candidate. If we have found a sufficient number of solutions, the code returns early.

    private solveBacktrackRec(unknownSum: number, 
					    	unknownCount: number, 
	    					gridSoFar: MaybeDigit[], 
					    	limit: number): SolvedTimesSquare[] {
        if (unknownCount == 1) {
            if (isDigit(unknownSum)) {
                const nextUnknownIdx = gridSoFar.findIndex(v => v === undefined);
                const newGrid = [...gridSoFar];
                newGrid[nextUnknownIdx] = unknownSum;
                if (rowCol(newGrid as Digit[]) === this.rowcol) {
                    return [new SolvedTimesSquare(newGrid as Digit[], this.sum, this.rowcol)];
                } else {
                    return [];
                }
            } else {
                return [];
            }
        } else {
            const nextUnknownIdx = gridSoFar.findIndex(v => v === undefined);

            if (nextUnknownIdx === -1) {
                if (unknownCount > 0) {
                    throw new Error("unknownCount > 0, but no unknown variables left?");
                } else {
                    // we've been given a solved solution
                    return [new SolvedTimesSquare(gridSoFar as Digit[], this.sum, this.rowcol)];
                }
            } else {
                const solutions = [];
                const possibilities = digitRange(1, Math.min(unknownSum - unknownCount + 1, 9) + 1);

                for (const p of possibilities) {
                    const newGrid = [...gridSoFar];
                    newGrid[nextUnknownIdx] = p;
                    const maybeSolutions: SolvedTimesSquare[] = this.solveBacktrackRec(
                    			unknownSum - p, 
			                    unknownCount - 1, 
			                    newGrid, 
			                    limit);
                    solutions.push(...maybeSolutions);

                    if (solutions.length >= limit) {
                        return solutions;
                    }
                }

                return solutions;
            }
        }
    }

Results

Using Tinybench, we benchmarked the code. Each operation involves solving all 100 problems for the given matrix size.

For the Upstart challenge, the numbers do not matter, but rather the computational complexity of the algorithm. If we take the base-2 log of the median latency (table below), we see that the backtracking algorithm is taking order exponential time.

Backtracking is not performing very well because it cannot reduce the size of the candidates rapidly at each step since each step only uses the S value as a filter. For larger matrices, the remaining sum will be greater than 10 for many steps, yielding all 9 digits as candidates. Compare this to N Queens, where the first step has eight candidates (in the 8x8 case), but the second step may have just five, and the third step may have just two. Our baseline solution will find all the TimesSquare solutions, but does not meet the Upstart challenge of taking less than exponential time.

References

Dennis Shasha. 2026. TimesSquare. Commun. ACM 69, 4 (April 2026), 96. https://doi.org/10.1145/3797279