I found this game https://sumplete.com/ and it was made by AI. Let's try to say mathematically what this game is about. We have $n\times n$ matrix $A$. Let $B= \{n\times n \text{ matrices, having } b_1, b_2, ..., b_n \text{ on its diagonal}\}$, $C= \{n\times n \text{ matrices, having } c_1, c_2, ..., c_n \text{ on its diagonal}\}$. In the game we need to find $n\times n$ matrix $X$ with elements from $\{0,1\}$ so that $AX \in B, A^TX^T \in C$. I think that there are a lot of questions we can ask.

For example:

  1. Does this matrix $X$ exist for any $A, B, C$? (obvious one)
  2. Is there a criteria for existence of $X$?
  3. Let all elements in all matrices have elements from $\mathbb{N}$ and an appropriate $X$ exists. Is there an algorythm for finding $X$?
  4. Let all elements in all matrices have elements from $\mathbb{Z}$ and an appropriate $X$ exists. Is there an algorythm for finding $X$? And so on... This list can be easily expanded.

I find this problem very exciting, but I don't have any ideas about significant steps that can be done here :)

  • 2
    $\begingroup$ A simple observation is that for the existence of $X$ it is necessary that $\sum b_i=\sum c_i$, as $\operatorname{trace}(AX)=\operatorname{trace}(XA) =\operatorname{trace}(XA)^T =\operatorname{trace}(A^T X^T)$. It looks a nice problem. $\endgroup$ Commented Mar 15, 2023 at 23:03
  • $\begingroup$ I think a first step would be to look at the two extreme cases. The one where all the coefficients of $A$ are equal to 1, and the one in which $b_i$ determines the $i$-th row of $X$ (analogous for $c_i$). An instance of the second one would be $a_{ij}=10^{i+j}$, for which it is immediate to compute the matrix $X$ if writing numbers in base $10$. The first case looks simpler than the general problem, but I guess it contains a considerable part of the difficulty $\endgroup$ Commented Mar 16, 2023 at 0:31
  • $\begingroup$ If $A = I$ clearly there isn't any solution unless all $b_i = c_i$ $\endgroup$
    – Zoe Allen
    Commented Mar 16, 2023 at 9:31

1 Answer 1


This game is in connection with the domain called discrete tomography.

In fact if the issue is

"being given the margins, reconstruct a possible distribution of values in the 9 boxes"

(starting or not from an initial distribution ; I am not certain I have well understood the rules).

A major issue is the non unicity due to the "linear algebra" fact that

An underdetermined system of 9 unknowns and 6 equations can be "solved" by fixing $9-6 = 3$ parameters, which can be considered as "degrees of freedom"...

... this value $3$, not surprizingly, can be interpreted as the dimension of a certain kernel, with for example this basis with 3 elements :

$$\begin{pmatrix}1&-1&0\\-1&1&0\\0&0&0\end{pmatrix}, \begin{pmatrix}1&0&-1\\0&0&0\\-1&0&1\end{pmatrix}, \begin{pmatrix}0&0&0\\0&1&-1\\0&-1&1\end{pmatrix}$$

i.e., a basis of the subspace of matrices for which all the lines and columns sum up to $0$.

Please note that the elements belong to $\mathbb{Z}$. Limitations to elements of $\mathbb{N}$ would imply another branch of mathematics, i.e. linear programming (simplex method, etc.)

In this kind of game, strategies are of a very mathematical nature. Therefore, a (suitably programmed) computer should always beat human players...

Remark : a hidden constraint is that the right margin and bottom margin must have the same sum.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .