Maximal sum in 5x5 Minesweeper

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

23332
xxxxx
35653
1xxx1
12321

I brute forced this answer using my minesweeper library at https://github.com/bradmarder/MSEngine

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)
            .Sum(x => x.AdjacentMineCount);
        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}");
    }
}