Jump and fill my square

Hello Math Fun
The aim of this challenge is to fill a square with integers (square that has a 0 --zero-- in its upper-left corner). The best square is the one with the lowest sum of the said integers.

Here is my personal best for the 2 x 2 square (sum = 11):

0.1

6.4

... my best 3 x 3 has sum 63:

0.1.20

6.8.10
4.2.12

In order to fill a square, you have to start on the zero cell and jump: 
   a) over zero cell (you land on 1 of the 4 adjacent cells –  diagonal jumps are forbidden)
   b) from there, over 1 cell (you always have the choice to jump up, right, down or left if the landing cell is empty)
   c) from there, over 2 cells (same rules as above)
   d) from there, over 3 cells (same rules – at every step the size of the jump is increased by 1).
etc.

Here is my path two fill the 2 x 2 square, starting on 0 (R=right, D=down, U=up and L=left; the size of the jump is increased by 1 at every step, the 1st jump being of size zero):

R D D U R L



Here is my path to fill the 3 x 3 square -- same convention:


R D R L D U L R L R U D L R D U D U R L



(the above illustration also shows my attempt for a 4 x 4 square built on the 3 x 3)


     0. 1.20.18
     6. 8.10.16
     4. 2.12.14
    38.40.42.44
The total sum for this 4 x 4 square is 275.
Can you beat my personal records? And find records for bigger squares?
(forgive me if this is old hat)
Best, É.
____________________
May 20, 2019 update

Tom Karzes was quick to beat my attempts. Here is the mail he sent to Math Fun:

I slapped together a quick-and-dirty search program, and was able to find optimal solutions up to 6x6. Note that for sizes 2x2, 4x4, 5x5, and 6x6, it was able to find solutions that remain within the square for the first n-1 moves, and thereafter bounce out of and into the square every other move, making it trivial to verify their optimality. No such solution exists for the 3x3 case, and I suspect it doesn't for 7x7 either (I started a search on 7x7 but eventually killed it). Anyway, here are optimal solutions for 2x2 through 6x6:

Size: 2x2   Sum: 9    Moves: RUDRL

           0.1
           5.3

Size: 3x3   Sum: 59   Moves: RDLRDURLRLUDLDRU

           0.1.16
          10.8. 6
          12.2. 4

Size: 4x4   Sum: 198   Moves: RRDRLRLRLDUDULRUDLRLRDURLDU

           0. 1.27. 2
          13.15.25.23
          11.17.19.21
           9. 7. 5. 3


Size: 5x5   Sum: 510   Moves: RDRLDULRLRUDUDRLRLUDLRLRLRLRDURLDUDULRDURLRL

           0. 1.44.42.40
           6. 8.10.36.38
           4. 2.12.34. 3
          18.16.14.32.30
          20.22.24.26.28


Size: 6x6   Sum: 1095   Moves: RDRLRUDRLRLUDLRLRUDRLRLRLRLRLDDULRUDLRDUDULRDULRLRDURLRLRLUDRLRL
           0. 1.59.57.55.53
          65.63.61.47.49.51
           4. 2.43.45. 3. 5
          33.35.41.11. 9. 7
          31.37.39.13.15.17
          29.27.25.23.21.19

Bravo Tom!
I will submit this sequence to the OEIS – we will see if it is accepted.
____________________


Commentaires

Posts les plus consultés de ce blog

Confingame, 3e étape

Square my chunks and add

Triples for the new year