# Different numbers in all cells of a 4x4 board

This is a harder version of this puzzle: Different numbers in all cells of a 3x3 board

Zeroes are written in all cells of a 4×4 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!

• I wonder if the bonus question is just there to throw us off, as it assumes the answer to the previous question would be yes :) Aug 28, 2020 at 8:48

I think the least amount of presses is

27

Press the following cells $$x$$ amount of times

$$\begin{matrix} 0 &1 &2 &1\\ 0 &7 &1 &1\\ 0 &2 &4 &6 \\ 0 &0 &1 &1 \end{matrix}$$

yielding

$$\begin{matrix} 1 &10 &5 &4\\ 7 &11 &15 &9\\ 2 &13 &14 &12 \\ 0 &3 &6 &8 \end{matrix}$$

• Well done! That is optimal indeed. Aug 28, 2020 at 13:12
• @DmitryKamenetsky How do you know? Aug 28, 2020 at 14:32
• looking at this and the previous puzzle, I am wondering if an n x n grid would take 3^(n-1) moves? Aug 28, 2020 at 18:23
• @SeanC, the minimum for $n=5$ is 63, not 81. Aug 28, 2020 at 18:43
• @DmitryKamenetsky 128 for $n=6$ and 237 for $n=7$ Aug 28, 2020 at 23:50

Yes it is possible

Make these presses

$$\begin{matrix} 1 &0 &0 &0\\ 1 &0 &8 &0\\ 1 &2 &8 & 2 \\ 1 &2 &2 &2 \end{matrix}$$

To get these values

$$\begin{matrix} 2 &1 &8 &0\\ 3 &11 &16 &10\\ 5 &13 &22 & 12 \\ 4 &7 &14 &6 \end{matrix}$$

Not sure if this is optimal.

Here's another optimal solution, obtained via integer linear programming. Make these presses:

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

To get these values:

$$\begin{matrix} 8 &6 &1 &4 \\ 13 &14 &15 &5 \\ 9 &12 &10 &11 \\ 0 &2 &7 &3 \end{matrix}$$

By request, here's the ILP formulation I used. For each cell $$(i,j)$$, let $$N_{ij} = \{(i_2,j_2): |i-i_2| + |j-j_2| \le 1\}$$ be the neighborhood of the cell. For each cell $$(i,j)$$, let nonnegative integer decision variable $$x_{ij}$$ represent the number of times to press the cell. For each cell $$(i,j)$$ and value $$k\in\{0,\dots,M\}$$, let binary decision variable $$y_{ijk}$$ indicate whether cell $$(i,j)$$ takes value $$k$$. The problem is to minimize $$\sum_{i,j} x_{ij}$$ subject to \begin{align} \sum_k y_{ijk} &= 1 &&\text{for all i,j} \\ \sum_{i,j} y_{ijk} &\le 1 &&\text{for all k} \\ \sum_{(i_2,j_2) \in N_{ij}} x_{i_2,j_2} &= \sum_k k y_{ijk} &&\text{for all i,j} \end{align}

• Nice. Is ILP able to produce multiple optimal solutions? I am interested to know how many there are, at least for the 3x3 case. I found a few, but there could be others lurking. Aug 28, 2020 at 14:22
• 56 optimal solutions for 3x3 and 3280 for 4x4 Aug 28, 2020 at 15:27
• Thank you RobPratt! Aug 28, 2020 at 23:11
• Hi RobPratt, I'm trying to build this model. I use $n^2$ integers variables to determine how many times to press, and $O(n^4)$ binary variables to realize the inequal constraints of every pair. I also tried using $(Mn^2)$ binary variables to realize the inequal constraints, where $M$ is a predefined upper bound of the result matrix. But that seems worse. I wonder how you build the model, and how long do you need to solve the model of $n=6, 7$, thank you.
– xd y
Apr 14, 2022 at 12:10
• @xdy I added my formulation. For $n=6$, it took 8 minutes. For $n=7$, it took 28 minutes. I used $M=n^2-1$ for both. Apr 14, 2022 at 20:35