6
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – Lukas Rotter
    Commented Aug 28, 2020 at 8:48

3 Answers 3

Reset to default
4
$\begingroup$

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}

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

Answer to the first question

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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}

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 28, 2020 at 14:22
  • 1
    $\begingroup$ 56 optimal solutions for 3x3 and 3280 for 4x4 $\endgroup$
    – RobPratt
    Commented Aug 28, 2020 at 15:27
  • $\begingroup$ Thank you RobPratt! $\endgroup$
    – Dmitry Kamenetsky
    Commented Aug 28, 2020 at 23:11
  • $\begingroup$ 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. $\endgroup$
    – xd y
    Commented Apr 14, 2022 at 12:10
  • $\begingroup$ @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. $\endgroup$
    – RobPratt
    Commented Apr 14, 2022 at 20:35

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