Maximize board score

Question

The board is a simple 31 by 31 chess-like grid.

• Up to a single piece can be placed on each square (so technically up to 961 pieces)
• Pieces grant [16 - taxicab_distance_from_middle_square] score (can't go below 0 score)
• But each piece loses 1/24th of its score times every other piece that is inside a 5 by 5 square centered around the piece
  • So a completely surrounded piece grants exactly no points
  • And a piece surrounded by 12 other pieces grants exactly half its original score
• The goal is of course, to find the arrangement of pieces that yields the highest score

I've tried running a program that places one piece at a time in any place that would give the highest score, but since each placement affects the score of other pieces, the result is obviously not even close to optimal.

What would be the best way to find (or at least get close to) the board state with the highest score?

Answer 1

It seems like good solutions have an interesting kind of structure. Here's a solution with value 879.25:

0000000000000001000000000000000
0000000000000011100000000000000
0000000000000001000000000000000
0000000000001001001000000000000
0000000000011111111100000000000
0000000000001001001000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000111111111111111110000000
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0001111111111111111111111111000
0000000000000000000000000000000
0000000000000000000000000000000
1111111111111111111111111111111
0111111111111111111111111111110
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0000011111111111111111111100000
0000000000000000000000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000001111111111111000000000
0000000000000000000000000000000
0000000000001001001000000000000
0000000000001111111000000000000
0000000000000011000000000000000
0000000000000001000000000000000
0000000000000001000000000000000

I found this solution, and 7 rotations and reflections of it, by simulated annealing.

If you "guess" that the middle bunch of rows are as above, you get manageably small subproblems above and below said bunch of rows. You could find the optimal solutions to these subproblems by dynamic programming, for instance.