Since I taught Pearls in chat these days how do use the covering sets method, I might as well post here too:
Minesweeper is, fundamentally speaking, a constraint satisfaction problem. It means there are two approaches to solve them, which while seemingly completely different, are actually equivalent:
1. Suppose a random cell's empty/flagged. If it ends up with a contradiction at the end, the cell must be in the other state. Rinse and repeat.
This is the typical approach used by most people, which transforms the problem into a simple depth-first search problem (simple as in, brute force is dumb but it will always work
).
2. Transform every clue into their relevant
covering sets. Merge and subtract covering sets to get more covers until covers of "
n tiles contain (0 or n) mines"
appear, whose state can be immediately determined.
Actually lots of people who've played enough Minesweeper has vague ideas about this in their mind, but never actually realize that they're using it. It's actually a very powerful tool.
Let's look at a simple example:
Suppose I haven't told you how many mines are there. There is nothing we can immediately solve without taking assumptions!
Or is it? Let's look at it this way:
Click here to view the secret text
×
We see that the red 1 covers the 2 red tiles, which means there's a covering set of 1 mine on those 2 tiles. Similarly, the blue 1 gives another covering set of 1 mine on the 3 tiles.
Then we subtract the red set off the (bigger) blue set, and get the green set. The mines total is 1-1 = 0. So we've proven that the green set has no mines!
Similarly, let's look at the 2:
Click here to view the secret text
×
The 2 spans a covering set of 2 mines that covers all tiles in this section besides 1 tile. This tells us that the total amount of mines must be 2 or 3, and the lone tile at the bottom left will be empty/flagged depending on this number.
Combining cover sets together is simple:
- Adding two non-overlapping covers adds the possible number of elements together, taking the largest possible range (e.g 1 to 2 mines + 3 to 5 mines = 4 to 7 mines)
- Subtracting a proper subset from a cover subtracts the possible numbers of elements, also taking the largest possible range (e.g 3 to 5 mines - 1 to 2 mines = 1 to 4 mines)
- Adding overlapping covers and subtracting non-proper subsets from another cover are slightly more complicated since it also depends on the the size of interesction and non-intersection, but it's still quite easy to derive the range of the result.
(Technically speaking it's the Cartesian product of two sets with the appropriate operator applied. Of course, in almost all situations in minesweeper the range is always consecutive, so you don't have to do this.)
That is the gist of this method. Now, why is it better when we can always brute-force, you say? To illustrate the point, let's try solve this with the 1st method:
Done? Now watch how the 2nd method can perform deduction without all the blind guesses:
Click here to view the secret text
×
This set-theoretic approach is the basis of the obscure "
sledgehammer technique"
in Sudoku mentioned above,(Sudoku is a special form of Minesweeper where covers can only have 0 or 1 member). It is sort of equivalent of using an integer linear programming solver but it's not exactly a very common technique: the only notable place I've seen is
in a Hexcells solver. Of course, Minesweeper is still NP-hard with this covering sets approach, since the amount of power sets is exponential in respect to number of elements.
There are several advantages of covering set approach over brute-forcing:
1. In hard levels there can easily be 20 to 30 unknown tiles at once. Are you going to try that many combinations randomly until it works?
On the other hand, there could only be (usually) a maximum of 10 covers for 20-30 unknown tiles.
2. It clearly tells you which covers are needed to derive a specific tile's state. And you can work on the minimal covers that can derive that state. or determine if there are redundant hints. This allows you to tighten your puzzles to make really brutal levels (yes, people have done that with the assistence of Sixcells in Hexcells custom levels). You cannot obtain this information with the 1st approach.
3. It encodes the dreaded chains (like a line of 2s) neatly, and also
all branches of assumptions that you'd make in method 1 by ranges, which is much easier to keep track of. Instead of doing "
assume these 2 tiles have 0, 1 or 2 mines"
and search for each sub-case, you just say the cover has 0-2 mines, and then do covering set methods with it, so it's cleaner IMO.
4. This method generalizes to other forms of constraint problems very easily, and will instantly give you the basic patterns in those problems as well; e.g all known Sudoku techniques featured in
Sudokuwiki are applications of the sledgehammer.
All that said, method 1 is still useful for its simplicity and it can help verify your covering set Cartesian product is done correctly (doing this on non-proper subsets are not trivial). But for the advanced puzzle in Tametsi, it's very hard to make progress to even mid-game levels without extensive use of method 2. After finishing the entire game I can truly say I've kinda mastered how to do covering sets, and it's a good skill to have.
[Last edited by uncopy2002 at 03-27-2019 02:27 AM]