# 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 '20 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 '20 at 13:12
• @DmitryKamenetsky How do you know? Aug 28 '20 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 '20 at 18:23
• @SeanC, the minimum for $n=5$ is 63, not 81. Aug 28 '20 at 18:43
• @DmitryKamenetsky 128 for $n=6$ and 237 for $n=7$ Aug 28 '20 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}$$

• 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 '20 at 14:22
• 56 optimal solutions for 3x3 and 3280 for 4x4 Aug 28 '20 at 15:27
• Thank you RobPratt! Aug 28 '20 at 23:11