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!
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityI 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.
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
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}");
}
}