8
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Isn't this an open-ended question? $\endgroup$ Dec 3, 2020 at 14:22
  • 2
    $\begingroup$ @zixuan: there's provably an upper bound. I don't have quite enough math, but it's certainly lower than 67108864 = 2^26, which would require each new square to double the last square that was entered 25 times, which is clearly impossible (if for no other reason than there must be at least two "1" squares). $\endgroup$
    – minnmass
    Dec 3, 2020 at 17:58
  • 3
    $\begingroup$ A helper for trying this puzzle: jsfiddle.net/9ebu8v02 $\endgroup$
    – tsh
    Dec 4, 2020 at 9:44
  • 1
    $\begingroup$ @tsh this is awesome, thank you! I wish I knew JavaScript - it would really help with making little visual prototypes. $\endgroup$ Dec 4, 2020 at 12:14

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ @TigerTV.ru That would easily overflow the long integer type, so it would take a bit of work to adapt my program. It would also highly likely not get anywhere even close to optimal in a reasonable time since the number of possibilities are so astronomically huge. $\endgroup$ Dec 3, 2020 at 16:49
  • 1
    $\begingroup$ For your interest my best solution for 7x7 is 214548. I could only reach it once, so it is probably not optimal. It is an interesting solution, because the largest number does not lie on the edge. $\endgroup$ Dec 4, 2020 at 7:20
  • 2
    $\begingroup$ @DmitryKamenetsky I get the same answer for 7x7, but picked a solution with the largest number in a corner. $\endgroup$ Dec 4, 2020 at 8:16
  • 2
    $\begingroup$ @TigerTV.ru On 3x3 you can reach 10: (1,2,1)(2,4,5)(1,5,10). Interesting that my solutions for 5x5-7x7 all fill in a 3x3 corner first, but don't reach 10. $\endgroup$ Dec 4, 2020 at 10:10
  • 1
    $\begingroup$ The best progress is made if high numbers are combined as much as possible. So zigzagging on some band will give the best asymptotic exponential growth. I thought that a band of width two would be optimal, with the golden ratio's gain of 61.8% per 2 cells. However each turn has a cost. It turns out that the asymptotic gains (rounded) per cell are 27.2%, 31.0%, 30.3% and 28.6% for width 2,3,4,and 5 bands respectively. It remains to get the best start, and to minimize the cost of turning, but e.g. on a 100*100 square, using 32 bands of 3 and 1 band of 4 might be close to optimal. $\endgroup$
    – Retudin
    Dec 5, 2020 at 9:31
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ how!! my code got me 189 :think: $\endgroup$ Dec 3, 2020 at 13:40
  • 1
    $\begingroup$ @OmegaKrypton: I just tried to keep the high numbers near the middle. I have a new answer now... solution to follow... $\endgroup$
    – musefan
    Dec 3, 2020 at 13:45
  • $\begingroup$ ah my code is still burning ig, may yield something higher than that, hopefully. anyways, gj! $\endgroup$ Dec 3, 2020 at 13:49
1
$\begingroup$

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)

enter image description here

$\endgroup$
2
  • $\begingroup$ This is not optimal for $n=3$. What does it yield for $n=7$? $\endgroup$
    – RobPratt
    Dec 4, 2020 at 16:25
  • $\begingroup$ I stand corrected ; only 142069 (if I calculated correctly) $\endgroup$
    – Retudin
    Dec 4, 2020 at 17:05
0
$\begingroup$

So... no 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;
}

```  
$\endgroup$
4
  • 4
    $\begingroup$ 25! is a large number... $\endgroup$ Dec 3, 2020 at 14:14
  • 1
    $\begingroup$ Just 25!=15511210043330985984000000 $\endgroup$
    – TigerTV.ru
    Dec 3, 2020 at 16:21
  • 1
    $\begingroup$ It's not "just"... As nowadays computer may take 1,000,000,000 operations in one second, maybe you want to wait for 3,000,000,000 years to finish this... $\endgroup$
    – athin
    Dec 3, 2020 at 16:42
  • 2
    $\begingroup$ @athin, Often maths helps when computer can't. $\endgroup$
    – TigerTV.ru
    Dec 3, 2020 at 17:10

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.