Maximal sum in 5x5 Minesweeper

How can you place 8 mines on a 5x5 Minesweeper grid such that the sum of the produced numbers is maximal? Are there multiple solutions?

Good luck with this!

I got this:

46

12332
1****
35653
****1
23321

With these also producing the same total:
23332
*****
35653
1***1
12321

12332
1****
24664
1****
12332

By the way, my technique for solving:

The best thing is for a mine to be placed next to 8 open spaces, giving you +8. So the best score is 64, but obviously that can't be done. I counted how many "deductions" from a perfect score I could get and tried to minimize those. You can get this far with no deductions:

.....
.*.*.
.....
.*.*.
.....

Now if you place a mine next to an existing mine, you should deduct 2 points for every existing mine it touches (-1 for the mine you place losing 1 spot and -1 for the other mine losing a spot). If you place a mine on the edge, deduct 1 point for every out of bounds neighbor. With this in mind, the two next best spots are (-4 deductions each):
.....
.***.
.....
.***.
.....
(-8 score)

After that, each of the edge spots on the same row as the existing two rows deducts -5 points, so you can pick any combination of 2 of them, giving a final score of -18 deductions, which is 64-18 = 46.

• Great explanation! Sep 18, 2019 at 23:37

I can get

42:
12321
2XXX2
X565X
2XXX2
12321

Moving the two mines on the border closer to center (so that all mines form a square) gives 40, and moving the two mines in the middle of 3s further from center (so that all mines form a rhombus) gives 38, so doesn't look very promising.

23332
xxxxx
35653
1xxx1
12321

It took only 83952 iterations to find an answer with a sum of 46. I also made an attempt to find an answer with a sum > 46, but stopped after 5m+ iterations. Finding a board that satisfies the criteria isn't too rare. I roughly calculated that 10 solutions appear every ~2m iterations. So if you picked a random board, you would have a significantly better chance of winning this puzzle than the lottery.

Here is the snippet of code I used.

private static void Test()
{
var watch = System.Diagnostics.Stopwatch.StartNew();
var iteration = 0;
var max = 0;

while (true)
{
var board = Engine.Instance.GenerateBoard(5, 5, 8);
var localMax = board.Tiles
.Where(x => !x.HasMine)
max = Math.Max(max, localMax);

if (max == 46)
{
var failBoard = BoardStateMachine.GetFailedBoard(board);
Console.WriteLine(GetBoardAsciiArt(failBoard));
break;
}

Interlocked.Increment(ref iteration);
Console.SetCursorPosition(0, Console.CursorTop);
Console.Write(\$"CurrentMax = {max}, Iteration = {iteration}, and ellapsed MS = {watch.ElapsedMilliseconds}");
}
}