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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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