# Different numbers in all cells of a 3x3 board

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!

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.

• You got it! - this is optimal. I actually thought of Integer Programming when making this puzzle. Aug 28 '20 at 2:35
• Why is this optimal? Aug 28 '20 at 16:04
• 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. Aug 28 '20 at 16:07

Yes, it is possible:

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

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