Neighboring sums 4x4 game

Here is an interesting game. You start with an empty 4x4 grid. At each turn you can 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?

• Could you ask grid 5x5? Commented Dec 3, 2020 at 12:22
• Commented Dec 3, 2020 at 12:58

The best solution my computer found is

41

I suspect this is optimal.

  1  1  2  1
5  4  3  1
5  9 26 27
5 14 14 41

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

• "as you can simply choose the squares according to the increasing order of the numbers." This doesn't seem to be true to me. In particular, I suspect which 5 you place first matters a lot. Commented Dec 4, 2020 at 6:22
• Well done! I have verified that this is the optimal answer. There is another solution that achieves the same score, but uses a slightly different path that does not involve number 27. Commented Dec 4, 2020 at 6:53
• Is there a way to find the solution without using a computer? Commented Jun 9, 2023 at 0:47

38

as here

the order is as below

My first 3 tries, in the order of increasing score:

Score 20. Simply going row-wise, which produces a part of Pascal's triangle:

1  1  1  1
1  2  3  4
1  3  6  10
1  4  10 20

Score 32. An approach similar to the above, but placing ones at (1,3) and (3,1) first to boost the middle:

1  2  1  1
2  4  5  6
1  5  10 16
1  6  16 32

Score 37. An approach that utilizes Fibonacci sequence. Place the numbers in this order

1  3  4  5
16 2  6  7
15 14 10 8
13 12 11 9

which gives this:

1  2  2  2
37 1  3  5
35 22 8  5
13 13 13 5

• Love your work! This puzzle turned out more interesting than I realized :) Commented Dec 3, 2020 at 4:52
• Damn, I just got the same result, then looked up to see that you'd just posted this :-(
– lxop
Commented Dec 3, 2020 at 4:52

I found three solutions that all achieve the following score, with more or less the same chain but finishing in different positions:

41

corner:

 41 27  1  1
14 26  3  2
14  9  4  1
5  5  5  1

edge:

 14 41  1  1
14 26  3  2
14  9  4  1
5  5  5  1

interior:

 14 15  1  1
14 41  3  2
14  9  4  1
5  5  5  1

A computer search determined that this score is optimal.

• Nice work! I haven't seen the interior solution before. Commented Dec 6, 2020 at 1:53