Get this book -> Problems on Array: For Interviews and Competitive Programming
Many may think Minesweeper is a random game but it is infact a strategy game and you can win it everytime if you know the rules involved in building it and the proven strategies to play Minesweeper.
From a computational point of view, this is an NP-Complete problem that is it will take a Computer exponential number of steps to calculate the winning move in a Minesweeper of a given size. Note that it is possible to win always but it will take some time.
Minesweeper is a very popular single player strategy game. In this article, we're going to look at the all the rules of this game and few strategies to win against it.
Minesweeper game is all about finding the patterns and making decisions processing all the elimination chances.
The goal of the player is to clear a rectangular board containing hidden "mines" or bombs without detonating any of them, with help from clues about the number of neighboring mines in each cell.
Here is how the game follows-
In the first step, the player has to click on a random square and just hope it's not a bomb.
If the player clicks on a safe area, the square will either open up to be blank (which is mine) or will contain a number from 1 to 8.
These numbers specify the number of bombs that are adjacent to that square, i.e. n means there are n bombs adjacent to that square.
This way the player needs to go ahead with calculating which square can contain the bombs. These calculations are to be performed based on multiple squares which can determine the probability of a square having bombs.
If the player clicks on a unsafe square which contains bomb, the game gets over.
Minesweeper algorithm and NP completeness:
Minesweeper game, being a decision making problem based on the given constraints/obstacles, is a backtracking problem to an extent. After every move, the player has to estimate the risk factor of next move by measuring all the possibilities and the porbability fator of the risks. So the algorithm/computition is NP-complete for a consistent boad if we analyse the complexity. A NP- complete problem can be solved by bruteforce search algorithms in polynomial time on a non-deterministic turing machine, which is true for consistent Minesweeper board. If there is inconsistent board, the player need infinite time to cover the baord, hence not NP-complete because one can search through all the possibilities but that will take very a long time (~infinite) to do!
Let's look at few strategies and tips to play better-
As the first pick is completely random, it would be better idea to select a square close to middle as the corner squares provides less info as some sides get blocked.
If a mine, i.e blank square is found, all the adjacent sqaures are safe.
The first thing to recognize is that if there is an inside corner, there is a mine. Second, a 1,2,1 pattern always has the mines on the 1’s.
The more you play, the better you get at the pattern recognition.
Luck plays a huge role in this game, so have good luclk! :p
If you want to build a simple Minesweeper game, check this article: Build a simple Minesweeper game using Vanilla JS
- Some Minesweeper Configurations (PDF) (bham.ac.uk) by Richard Kaye, The University of Birmingham, Birmingham
- Minesweeper is NP-Complete research paper (snu.ac.kr) by Richard Kaye