13
$\begingroup$

As most of you know minesweeper is a logic game where mines are hidden in a grid of squares. The object is to open all safe squares in the quickest time possible. Each number tells you how many mines touch the square. You are the game master and putting mines into the grids.

As a game master, you can put as many mines as possible and you decided to find the highest possible summation of the numbers given as a hint in the game.

So What is the highest possible summation of the numbers given as a hint in original 9x9 grid?

$\endgroup$
  • 2
    $\begingroup$ I guess this needs clarification: is it intended to be the maximum sum of numbers given from a single initial mouse click (as I was thinking and Bass's answer also seems to be thinking), or can it be from an arbitrary number of clicks as Riley's answer requires? $\endgroup$ – Daniel Schepler Mar 29 '18 at 19:34
  • 1
    $\begingroup$ @DanielSchepler I deleted that part not to create any misunderstanding. the game is just putting mines and getting numbers out of them. You are not gonna play it anyway. it is just Riley's answer actually. but it would be another interesting puzzle to be honest. $\endgroup$ – Oray Mar 29 '18 at 19:36
  • $\begingroup$ This is equivalent to finding a max cut in the graph of minesweeper cells, where adjacent cells (including corner adjacencies) are connected by an edge. The sides of the cut correspond to mines and non-mines. Unfortunately, max-cut is NP-hard, and I'm pretty sure the graph is nonplanar, so planar max-cut algorithms are inapplicable. $\endgroup$ – user2357112 Mar 29 '18 at 20:47
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Apr 3 '18 at 17:50
9
$\begingroup$

My answer is:

200:

 2 3 3 3 3 3 3 3 2 
 X X X X X X X X X 
 4 6 6 6 6 6 6 6 4 
 X X X X X X X X X 
 4 6 6 6 6 6 6 6 4 
 X X X X X X X X X 
 4 6 6 6 6 6 6 6 4 
 X X X X X X X X X 
 2 3 3 3 3 3 3 3 2

This was found:

Using a brute force search that assumed the solution would be symmetric (both horizontally and vertically). So there could be room for improvement, but only if the real solution is asymmetric. Code here.

$\endgroup$
  • $\begingroup$ Symmetry is a reasonable assumption, but it's quite possible that the optimal solution has only a diagonal line of symmetry. $\endgroup$ – Mark Mar 29 '18 at 20:25
  • 2
    $\begingroup$ There must be an optimal solution satisfying your assumptions. The top half of the grid can be flipped and copy-pasted onto the bottom to produce the same pattern of mine/non-mine adjacencies on the bottom, and likewise horizontally. The score of an answer corresponds directly to the number of mine/non-mine adjacencies. An asymmetric solution with more such adjacencies on one side can be improved by the above symmetrization operation, and an asymmetric solution with an equal number of adjacencies on each side will be no worse after symmetrization. $\endgroup$ – user2357112 Mar 29 '18 at 20:54
7
$\begingroup$

Just for fun, after reading Riley's answer, I decided to modify it into a simulated annealing optimization program. The basic idea here is: suppose you want a ball to find the lowest point in a terrain. In order to avoid finding the bottom of a shallow depression (local minimum), you allow the ball to bounce at random by a gradually decreasing amount. So, if the ball is bouncing in one of the shallow depressions with a deeper depression nearby, then eventually the "bounce amount" will nudge the ball out of the shallow depression, but to a point where it can no longer escape the deeper depression.

The exact formulation I'm using is roughly based on thermodynamics (where the term "simulated annealing" originated, I think, from a metallurgy technique "annealing" to create good alloys by a similar process of heating first, then gradually cooling). In my particular case, I was using "energy" as negative of a board's score, since simulated annealing minimizes an energy function whereas I wanted to find a maximum score.

Code:

#include <random>
#include <bitset>
#include <cmath>
#include <iostream>
#include <functional>
#include <unistd.h>
#include <time.h>
#include <boost/range/irange.hpp>

class Board {
public:
    Board() = delete;
    Board(std::mt19937& randGen) : m_randGen{randGen} { }
    Board(const Board&) = default;
    Board(Board&&) = default;
    Board& operator=(const Board&) = default;
    Board& operator=(Board&&) = default;
    ~Board() = default;

    int score() const {
        int result = 0;
        for (int r : boost::irange(0, board_height)) {
            for (int c : boost::irange(0, board_width)) {
                if (cell(r, c))
                    continue;
                for (int dr : boost::irange(-1, 2)) {
                    for (int dc : boost::irange(-1, 2)) {
                        if (checkedCell(r + dr, c + dc))
                            result++;
                    }
                }
            }
        }
        return result;
    }

    void mutate() {
        std::uniform_int_distribution<> dist { 0, board_size - 1 };
        int slot = dist(m_randGen.get());
        m_board.flip(slot);
    }

private:
    static constexpr int board_height = 9;
    static constexpr int board_width = 9;
    static constexpr int board_size = board_height * board_width;
    using internal_type = std::bitset<board_size>;

    internal_type m_board;

    std::reference_wrapper<std::mt19937> m_randGen;

    bool cell(int r, int c) const {
        return m_board[r * board_width + c];
    }

    bool checkedCell(int r, int c) const {
        return (r >= 0 && r < board_height && c >= 0 && c < board_width) &&
            cell(r, c);
    }

    friend std::ostream& operator<<(std::ostream& os, const Board& b) {
        for (int r : boost::irange(0, board_height)) {
            for (int c : boost::irange(0, board_width)) {
                if (b.cell(r, c))
                    os << '*';
                else {
                    int nbrCount = 0;
                    for (int dr : boost::irange(-1, 2)) {
                        for (int dc : boost::irange(-1, 2)) {
                            if (b.checkedCell(r + dr, c + dc))
                                nbrCount++;
                        }
                    }
                    os << char('0' + nbrCount);
                }
            }
            os << '\n';
        }
        return os;
    }
};

int main() {
    std::mt19937 randGen;
    std::seed_seq sseq{int(getpid()), int(time(nullptr))};
    randGen.seed(sseq);

    std::uniform_real_distribution<> probDist;

    Board bestBoardSoFar{randGen}, currBoard{randGen};
    int bestScoreSoFar = 0, currScore = 0;

    [[maybe_unused]] constexpr double startTemp = 1000.0;
    constexpr double stepTemp = 0.001;
    constexpr int numTempSteps = 1000000;

    for (int i : boost::irange(0, numTempSteps)) {
        double temp = stepTemp * (numTempSteps - i);
        Board newBoard = currBoard;
        newBoard.mutate();

        int newScore = newBoard.score();

        if (newScore > bestScoreSoFar) {
            bestBoardSoFar = newBoard;
            bestScoreSoFar = newScore;
        }

        // Naively, we would do:
        // double currBoardProb = std::exp(currScore / temp);
        // double newBoardProb = std::exp(newScore / temp);
        //
        // However, at low temperatures, this could cause both to be
        // inf values.  To avoid this, we scale both down by the same
        // factor of std::exp(currScore / temp)
        double currBoardProb = 1.0;
        double newBoardProb = std::exp((newScore - currScore) / temp);

        if (probDist(randGen) > currBoardProb / (currBoardProb + newBoardProb)) {
            currBoard = newBoard;
            currScore = newScore;
        }
    }

    std::cout << "Found solution with score " << bestScoreSoFar << '\n';
    std::cout << bestBoardSoFar;

    return 0;
}

Some sample outputs:

Found solution with score 183
*4*4*4*4*
*6*6*6*5*
*6*5**5*3
*4*45*6*3
355*5*6*3
****6*6*4
3545**5**
*4*5*6*53
*4*4*4*3*

Found solution with score 196
2*4*4*4*2
3*6*6*6*3
3*6*6*6*3
3*6*6*6*4
3*6*6*5**
3*6*6*654
3*6*5****
3*6*54664
2*4*3****

Found solution with score 200
*********
466666664
*********
466666664
*********
466666664
*********
466666664
*********
It's interesting that even when it doesn't find an optimal solution, the solutions sort of look like they have multiple "crystalization domains" which are locally of the form from the solutions with score 200.

.

So, given that it pretty consistently gets close to 200 (the worst run so far was 183) and hasn't yet beaten 200 in the several times I've run it, this would seem to be (weak) evidence that 200 could indeed be the global maximum.

$\endgroup$
4
$\begingroup$

I wrote a program that will loop through the cells and replace a clue with a mine whenever that will increase the sum.

Here is what I have:

 * * * * * * * * * 
 * 8 * 8 * 8 * 8 * 
 * * * * * * * * * 
 * 8 * 8 * 8 * 8 * 
 * * * * * * * * * 
 * 8 * 8 * 8 * 8 * 
 * * * * * * * * * 
 * 7 * 7 * 7 * 7 * 
 * 4 * 4 * 4 * 4 *
 

.

By getting the program to iterate again replacing mines with numbers when it increases the sum, we get a better arrangement:

.

 * 4 * 4 * 4 * 4 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 4 * 4 * 4 * 4 * 
 

.

This yields sum 200. Although it looks like @wolfram42 beat me to this exact arrangement. Here is my C++ code:

#include <iostream>

using namespace std;

#define N 9

int arr[N][N]; // number of adjacent mines
bool mine[N][N]; // whether or not a cell is a mine
int m[] = {2, 3, 4}; // for corner/edge/center: how many adjacent mines when replacing with a mine/clue is beneficial.

// 0 = corner, 1 = edge, 2 = center. index of m array
int getType(int x, int y) {
  if((x == 0 || x == N - 1) && (y == 0 || y == N - 1)) {
      return 0; //corner
  }else if((x == 0 || x == N - 1) || (y == 0 || y == N - 1)) {
      return 1; //edge
  }
  return 2;
}

int main(int argc, char **argv) {
  //initial values
  for(int i = 0; i < 9; i++) {
      for(int j = 0; j < 9; j++) {
          arr[i][j] = 0;
          mine[i][j] = false;
      }
  }

  //keep replacing things with mines greedily
  label:
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(!mine[i][j] && arr[i][j] < m[getType(i, j)]) {
                  mine[i][j] = true;
                  for(int k = i - 1; k <= i + 1; k++) {
                      for(int l = j - 1; l <= j + 1; l++) {
                          if((k != i || l != j) && k >= 0 && k < N && l >= 0 && l < N) {
                              arr[k][l]++;
                          }
                      }
                  }
                  goto label;
              }
          }
      }

  //keep replacing mines with numbers greedily
  label2:
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(mine[i][j] && arr[i][j] > m[getType(i, j)]) {
                  mine[i][j] = false;
                  for(int k = i - 1; k <= i + 1; k++) {
                      for(int l = j - 1; l <= j + 1; l++) {
                          if((k != i || l != j) && k >= 0 && k < N && l >= 0 && l < N) {
                              arr[k][l]--;
                          }
                      }
                  }
                  goto label2;
              }
          }
      }

  //output final configuration
  int sum = 0;
  for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
          if(!mine[i][j]) {
              sum += arr[i][j];
              cout << arr[i][j] << " ";
          }else {
              cout << "* ";
          }
      }
      cout << endl;
  }
  cout << "SUM: " << sum;
}

$\endgroup$
  • 1
    $\begingroup$ you dont need any computer algorithm to find the optimal, but be my guest anyway. $\endgroup$ – Oray Mar 29 '18 at 19:34
4
$\begingroup$

Continuing from Riley's starting point we can iteratively replace mines with numbers.

 * 4 * 4 * 4 * 4 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 6 * 6 * 6 * 6 * 
 * 4 * 4 * 4 * 4 *
 
Which gives a total of (7*6 + 2*4) * 4 = 200

Inverting yields:
 2 * 4 * 4 * 4 * 2 
 3 * 6 * 6 * 6 * 3 
 3 * 6 * 6 * 6 * 3 
 3 * 6 * 6 * 6 * 3
 3 * 6 * 6 * 6 * 3
 3 * 6 * 6 * 6 * 3
 3 * 6 * 6 * 6 * 3
 3 * 6 * 6 * 6 * 3
 2 * 4 * 4 * 4 * 2
 
Which is also 200, in both cases every bomb continued to remove can yield at most 2 extra, but would remove at least 4 from the total. Replacing any number will yield at most 2 extra bomb counts. I have also attempted to shift entire rows over, but it resulted in a loss as well.

$\endgroup$
  • $\begingroup$ Hey, I was just working on that! I just got my program to output exactly the same thing as your first one. $\endgroup$ – Riley Mar 29 '18 at 19:55
  • $\begingroup$ I didn't downvote. I'm not mad. $\endgroup$ – Riley Mar 29 '18 at 19:57
  • $\begingroup$ @PaulSinclair I was the downvote: I posted the same answer ten minutes ago $\endgroup$ – Austin Weaver Mar 29 '18 at 19:57
  • $\begingroup$ @Riley - Sorry for the bad assumption on my part, based on the very short time interval and your comment. $\endgroup$ – Paul Sinclair Mar 29 '18 at 20:00
  • $\begingroup$ @AustinWeaver - only the second of the two solutions posted by wolfram42 is identical (though rotated) to yours, so this post still adds something, even if the total score is the same. $\endgroup$ – Paul Sinclair Mar 29 '18 at 20:01
3
$\begingroup$

First attempt:

 x x x x x x x x x    0
 x 5 3 3 3 3 3 5 x   25
 x 3 _ _ _ _ _ 3 x    6
 x 3 _ 1 1 1 _ 3 x    9
 x 3 _ 2 x 2 _ 3 x   10
 x 3 _ 3 x 3 _ 3 x   12
 x 3 _ 3 x 3 _ 3 x   12
 x 5 3 5 x 5 3 5 x   26
 x x x x x x x x x  + 0
                   ----
                    100

$\endgroup$
  • 1
    $\begingroup$ Why would there be blanks? Replacing a blank with a mine can only increase the sum. $\endgroup$ – Dason Mar 29 '18 at 20:07
  • 4
    $\begingroup$ @Dason I think he interpreted the problem as "what is the maximum sum of clues possible from a single click?" $\endgroup$ – Riley Mar 29 '18 at 20:11
  • 1
    $\begingroup$ @Riley Ok that makes sense. And after reading the question wording as it initially was I can see how one might interpret it that way. $\endgroup$ – Dason Mar 29 '18 at 20:14

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.