TimesSquare Programming Puzzle - Part 1?

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…