Neighboring sums 5x5 game

Question

You start with an empty 5x5 grid. At each turn you choose an empty cell and place a value in it. The placed value is given by the following rules:

• If the chosen cell has no neighboring (horizontal or vertical) values then the placed value is 1.
• Otherwise the placed value is the sum of all neighboring (horizontal or vertical) values.

What is the largest value that you can achieve in this game?

Here is the same puzzle for the 4x4 grid: Neighboring sums 4x4 game

Answer 1

The best solution my computer found is

448

I suspect this is optimal.

  8   8   8   1   1
 23  15   7   3   2
 42  19   4   4   1
 42  61 168 172 173
 42 103 103 275 448

I won't list the order, as you can simply choose the squares according to the increasing order of the numbers.

The computer program I used started with choosing the 25 locations in any order. It then tried swapping the order of two randomly chosen locations around to see if that improved the score, and if so accept that swap. Repeat those swap attempts a large number of times, so that it has (probably) found a local maximum. It then does all this many times, keeping track of the best local maximum so far, hopefully eventually finding the global maximum.

Edit:
For fun I tried 6x6:

Score: 8815

  19   19   19    4    4    1
  53   34   15    7    3    2
  53   95    8    8    1    1
 148   95  737  745 3895 8815
 148  243  634 1379 3149 4919
 148  391  391 1770 1770 1770

and 7x7:

Score: 214548

 42   42   42    8     8      1      1
118   76   34   15     7      3      2
118  213   19   19     4      4      1
331  213 2857 2876 24751  24755  24756
331  544 2625 5501 21871  46626  71382
331  875 2081 7582 16370 134378  71382
331 1206 1206 8788  8788 143166 214548

and 8x8:

Score: 8203779

     1      1      8       8      42      42     213     213
     2      3      7      15      34      76     171     384
     1      4      4      19      19      95      95     479
 36313  36312  36308    7314    7295    1627    1532     479
101615  65302  28990   12963    5649    2585     958     479
182944  81329  16027   16027    3064    3064     479     479
182944 264273 727517  743544 1937369 1940433 5072106 5072585
182944 447217 447217 1190761 1190761 3131194 3131194 8203779

Edit: Dmitry Kamenetsky got a better 8x8:

Score: 9008465

     95      95      95      19      19      4      4      1
    266     171      76      34      15      7      3      2
    266     479      42      42       8      8      1      1
    745     479    3714    3756   19631  19639  99570  99571
    745    1224    3193    6949   15867  35506  79930 179501
    745    1969    1969    8918    8918  44424  44424 223925
5571135 5570390 2131091 2129122  813965 805047 268349 223925
9008465 3437330 3437330 1306239 1306239 492274 492274 223925

These larger squares are less likely to be optimal.

Answer 2

The highest I have gotten without the aid of a computer is:

397

Solution:

1 ,2 ,1 ,177 ,397
3 ,2 ,101 ,176 ,220
3 ,5 ,98 ,75 ,44
8 ,5 ,18 ,31 ,44
8 ,13 ,13 ,13 ,13

Order of input:

1 ,3 ,2 ,23 ,25
5 ,4 ,21 ,21 ,24
6 ,7 ,20 ,19 ,18
9 ,8 ,13 ,15 ,17
10 ,11 ,12 ,14 ,16

Strategy:

Have to start with a 1,2,1 combination of some sort just to get the ball rolling. I figured it's best to get one of the 1s in a corner, out of the way. Then snaking down the left side allowed me to keep the 5 next to the centre square. As I then snaked across the bottom I realised the mistake in my first attempt was to not keep the 31 near the middle. So I changed this and continued to work around the edge. This time instead of going all the way up the right side, I moved into the middle. This allowed for a greater number to finish in the top-right.

---

First Attempt:

209

1 , 2 , 1 , 166 , 49
3 , 2 , 119 , 116 , 49
3 , 5 , 209 , 67 , 49
8 , 5 , 18 , 18 , 49
8 , 13 , 13 , 31 , 31

Order of input:

1 ,3 ,2 ,23 ,22
5 ,4 ,24 ,21 ,20
6 ,7 ,25 ,19 ,18
9 ,8 ,13 ,14 ,17
10 ,11 ,12 ,15 ,16

My strategy here was to try and work towards finishing on the centre cell, so I tried to keep the larger numbers towards the middle.

Answer 3

Note: My suggestion below is disproved.

Not an answer, but regarding being open ended: I do expect that the following generalization holds as optimal solution for any odd square grid. And that might be provable optimal. (even though I do not see how to do that)

Answer 4

So... no no-computer so...

These are the solutions that yield highest of 189. For each pair of lines, the first line are the 25 numbers. The second line is the order in which they are filled.

1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 75 189 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 18 24 23 22 17 16 15 20 21
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 189 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 18 24 23 22 17 16 15 21 20
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 189 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 18 24 23 22 17 16 21 15 20
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 189 74 71 25 15 114 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 18 24 23 22 17 16 21 20 15
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 75 189 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 24 18 23 22 17 16 15 20 21
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 189 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 24 18 23 22 17 16 15 21 20
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 75 74 71 25 15 189 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 24 18 23 22 17 16 21 15 20
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 189 74 71 25 15 114 114 40 40 15
---0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 24 18 23 22 17 16 21 20 15

Anyways, i guess my compiler is too (insert poop) to take 25! permutations. So here is my C++ code. If anyone manages to reach higher with this code please kindly comment!

#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
int order[25];
int grid[25];
int max_val = 189;
//order[0] means the first processed grid
bool nw = false;
int find_val(int place){
    int sum = 0;
    if (place > 4){
        sum += grid[place-5];
    }
    if (place < 20){
        sum += grid[place+5];
    }
    if (place % 5 != 0){
        sum += grid[place-1];
    }
    if (place % 5 != 4){
        sum += grid[place+1];
    }
    if (sum == 0){
        sum = 1;
    }
    if (sum >= max_val){
        max_val = sum;
        nw = true;
    }
    return sum;
}

void fill(){
    for(int i=0;i<25;i++){
        grid[order[i]] = find_val(order[i]);
    }
}

int main(){
    int input;
    cin>>input;
    cout<<"im here"<<endl;
    for (int i=0;i<25;i++){
        order[i]=i;
        grid[i]=0;
    }
    cout<<"init done"<<endl;
    do{
        nw = false;
        for (int i=0;i<25;i++){
            grid[i]=0;
        }
        fill(); 
        for (int i=0;i<25 & nw;i++){
            cout<<grid[i]<<' ';
        }
        if (nw) cout<<endl;
        if (nw) cout<<"---";
        for (int i=0;i<25 & nw;i++){
            cout<<order[i]<<' ';
        }
        if (nw) cout<<endl;
    } while (next_permutation(order, order + 25)); 
    return 0;
}

```