5
$\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!

$\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$ Aug 28 '20 at 8:48
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}

$\endgroup$
6
  • $\begingroup$ Well done! That is optimal indeed. $\endgroup$ Aug 28 '20 at 13:12
  • $\begingroup$ @DmitryKamenetsky How do you know? $\endgroup$
    – Greedoid
    Aug 28 '20 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
    Aug 28 '20 at 18:23
  • 1
    $\begingroup$ @SeanC, the minimum for $n=5$ is 63, not 81. $\endgroup$
    – RobPratt
    Aug 28 '20 at 18:43
  • 1
    $\begingroup$ @DmitryKamenetsky 128 for $n=6$ and 237 for $n=7$ $\endgroup$
    – RobPratt
    Aug 28 '20 at 23:50
4
$\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.

$\endgroup$
2
$\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}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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