3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great explanation! $\endgroup$ – Dmitry Kamenetsky Sep 18 at 23:37
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}");
    }
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.