Naive Attempt at TimesSquare.

In the 04/26 copy of Communications of the ACM, the Upstart Puzzle is one called TimesSquare. The basic idea is a square matrix of single digit numbers where you are given some details and asked to fill in missing digits.

Specifically, the conditions are the sum of all digits and a value called RowCol which is the sum of all row products minus the sum of all colunm products.

Brute force is relatively straight forward to consider here. Place a digit and check the conditions. For the small square, this is explored in the column.

As you go to larger and larger squares, you are still left with a lot of work to consider here. So the question naturally arises on how you can cut down on the work before diving in.

I did not have any algorithm insights to pursue here. I was curious on how well solvers could handle the naive encoding of the problem. In this case, I mean to simply look at the numbers in the problem such as:

Where the RowCol is easy enough, \[abc + def + ghi - adg - beh - cfi\] with digit sum being the even easier \[a+b+c+d+e+f+g+h+i\]

Obviously, looping over the rows and columns could make this smaller to codify, but the general idea is to see if I could put this in a format that solvers could use and I didn't want to dive into the syntax just yet.

Doing a rather brief search online, I landed on some sample ZIMPL code that seemed like it would be easy enough to modify. Indeed, for the \(3 \times 3\) case given in the column, the two conditions look like:

subto digit_sum: a + b + c + d + e + f + g + h + i == 47;
subto row_col: a*b*c + d*e*f + g*h*i - a*d*g - b*e*h - c*f*i == 9;

Defining the variables can be done such that they are given integer constraints and kept 1-9.

var a integer >= 1 <= 9;

And, of course, some of the variables are already known, so I just follow up with constraints on those to be set values. That would look like the following.

subto fix_a: a == 5;

Finally, since solvers need an objective, I arbitrarily picked a variable to make the target. Nothing fancy there.

Executing with scip, I get the following at the top of my output:

primal solution (original space):
=================================

objective value:                                    5
a                                                   5   (obj:1)
b                                                   2   (obj:0)
c                                                   8   (obj:0)
d                                                   2   (obj:0)
e                                                   7   (obj:0)
f                                                   8   (obj:0)
g                                                   7   (obj:0)
h                                                   7   (obj:0)
i                                                   1   (obj:0)

Which corresponds nicely with the answer in the column.

I hit a snag when I first did the \(4\times4\) puzzle, though. My code for that one came up with a solution of the following.

Checking, the digits all sum to 64, and the RowCol comes out to 132. Asking the solver to count the solutions and it came up with 122 solutions.

Dumping the solutions, I could find the values given in the column. So unsure if I neglected a constraint or not.

This is one where getting a solution remains instant using the naive "dump it into a solver" approach. Counting all solutions it considered, though, was taking a longer time than I was willing to wait at the time.

I held my respect for the solvers. I was a little worried that my naive encoding of the problem would not get me any answers, but the code is able to get back a solution basically instantly.

Now, the column was asking for an algorithm that could find solutions. On that front, of course, I do not think I am offering anything. I think looking at the standard algorithms that solvers employ remains a good first step in understanding this, though. And would be happy to be shown any mistakes or otherwise silly parts of what I tried.

I was not going for anything complicated when I wrote these. As such, just linking directly here.

• three.zpl
• four.zpl
• five.zpl