5
$\begingroup$

This puzzle is inspired by this one: Board with all 2020s

Zeroes are written in all cells of a 3×3 board. Pressing a cell increases by 1 the number in this cell and all cells having a common side with it. Is it possible to obtain different numbers in each cell? Bonus question: what is the least number of presses needed to achieve this? Good luck!

$\endgroup$
7
$\begingroup$

Make these presses:

\begin{matrix} 0 &4 &2\\ 1 &2 &0\\ 0 &0 &0 \end{matrix}

To get these values:

\begin{matrix} 5 &8 &6\\ 3 &7 &4\\ 1 &2 &0 \end{matrix}

You can solve the problem via integer linear programming as follows. Let nonnegative integer decision variable $x_{i,j}$ be the number of times that cell $(i,j)$ is pressed. Let binary decision variable $y_{i,j,v}$ indicate whether cell $(i,j)$ contains value $v$. Let $N_{i,j}$ be the neighborhood of cell $(i,j)$, including $(i,j)$ itself. The problem is to minimize $$\sum_{i,j} x_{i,j} \tag1$$ subject to: \begin{align} \sum_{v\in V} y_{i,j,v} &= 1 &&\text{for all $i$ and $j$} \tag2 \\ \sum_{i,j} y_{i,j,v} &\le 1 &&\text{for all $v$} \tag3 \\ \sum_{(\bar{i},\bar{j})\in N_{i,j}} x_{\bar{i},\bar{j}} &= \sum_{v\in V} v\ y_{i,j,v} &&\text{for all $i$ and $j$} \tag4 \end{align} The objective function $(1)$ is the total number of presses. Constraint $(2)$ enforces one value per cell. Constraint $(3)$ enforces at most one cell per value. Constraint $(4)$ links the number of presses in the neighborhood to the value in the cell.

$\endgroup$
3
  • $\begingroup$ You got it! - this is optimal. I actually thought of Integer Programming when making this puzzle. $\endgroup$ Aug 28 '20 at 2:35
  • $\begingroup$ Why is this optimal? $\endgroup$
    – Greedoid
    Aug 28 '20 at 16:04
  • $\begingroup$ I'll describe the integer linear programming formulation later, but an easy lower bound is 8 presses because you need 9 different nonnegative integers, the largest of which must be at least 8. $\endgroup$
    – RobPratt
    Aug 28 '20 at 16:07
3
$\begingroup$

Yes, it is possible:

Press the corners 1, 3, 6, and 2 times. This gives the resulting grid of [143/705/682].

$\endgroup$
1
  • $\begingroup$ Correct answer to the first question! Note this does not use the minimal number of presses. $\endgroup$ Aug 28 '20 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.