8
$\begingroup$

This is a follow-up question to Different numbers in all cells of a 3x3 board v2

Here is the playable version.

You have a 5 × 5 grid whose entries all start at 0. A legal move is:

  • Select any 3 × 3 square that is aligned with the grid.
  • Add 1 to every entry inside that 3 × 3 square.

5 by 5 grid of zeros

Can you find a sequence of moves that fills the 5x5 grid with 25 distinct numbers while minimizing the number that ends up in the center cell?

Here is the playable version.

Improve this question
$\endgroup$
4
  • $\begingroup$ How’s that possible? Every step increments the centre cell, so it always has the largest number. $\endgroup$ Commented Aug 3 at 6:35
  • 1
    $\begingroup$ @Pranay smallest possible number in the center i meant. $\endgroup$ Commented Aug 3 at 6:37
  • 2
    $\begingroup$ Ah I see. I thought you meant smallest among all the numbers in the grid. This makes more sense. $\endgroup$ Commented Aug 3 at 6:38
  • 3
    $\begingroup$ So equivalent to minimize number of steps. Lower bound not smaller than 24. $\endgroup$ Commented Aug 3 at 12:00

2 Answers 2

Reset to default
10
$\begingroup$

I found the minimum via constraint programming (with an alldifferent constraint).

Moves:

$\begin{matrix} 1 & 15 & 2 \\ 4 & 0 & 2 \\ 3 & 3 & 9 \end{matrix}$

Grid:

$\begin{matrix} 1 & 16 & 18 & 17 & 2 \\ 5 & 20 & 24 & 19 & 4 \\ 8 & 26 & \color{red}{39} & 31 & 13 \\ 7 & 10 & 21 & 14 & 11 \\ 3 & 6 & 15 & 12 & 9 \end{matrix}$

SAS code:

proc optmodel;
   num n = 5, k = 3, maxNumMoves = 50;
   set CELLS = 1..n cross 1..n;
   set MOVES = {<i,j> in CELLS: <i+k-1,j+k-1> in CELLS};
   set MOVES_cell {<i,j> in CELLS} = (i-k+1..i cross j-k+1..j) inter MOVES;
   
   var NumMoves {MOVES} >= 0 <= maxNumMoves integer;
   impvar CellValue {<i,j> in CELLS} = sum {<i2,j2> in MOVES_cell[i,j]} NumMoves[i2,j2];
   min TotalNumMoves = sum {<i,j> in MOVES} NumMoves[i,j];
   con alldiff(CellValue);

   solve;

   print NumMoves;
   print CellValue;
quit;
Improve this answer
$\endgroup$
5
$\begingroup$

Bidding starts at

43:
enter image description here
The nine subsquares, from top to bottom and left to right, are incremented 1, 1, 3, 7, 6, 9, 6, 1, and 9 times, respectively.
11 is missing, so there may be better, but further attempts at being methodical came out worse.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi! Can you comment on the method you used? $\endgroup$ Commented Aug 4 at 12:24
  • 1
    $\begingroup$ Manual fiddling in a Google Sheet, nothing more. The placement of 1-5 in the first row is intentional, but further plans to place small numbers didn't work the way I initially planned. $\endgroup$ Commented Aug 4 at 12:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.