![]() or determine if there are redundant hints. And you can work on the minimal covers that can derive that state. It clearly tells you which covers are needed to derive a specific tile's state. ![]() 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.Ģ. In hard levels there can easily be 20 to 30 unknown tiles at once. There are several advantages of covering set approach over brute-forcing:ġ. 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. 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. 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). 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:ĭone? Now watch how the 2nd method can perform deduction without all the blind guesses: ![]() Of course, in almost all situations in minesweeper the range is always consecutive, so you don't have to do this.) (Technically speaking it's the Cartesian product of two sets with the appropriate operator applied. 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. 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 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) 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. The 2 spans a covering set of 2 mines that covers all tiles in this section besides 1 tile. ![]() There is nothing we can immediately solve without taking assumptions! Suppose I haven't told you how many mines are there. 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.Īctually 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. Transform every clue into their relevant covering sets. 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 ).Ģ. If it ends up with a contradiction at the end, the cell must be in the other state. It means there are two approaches to solve them, which while seemingly completely different, are actually equivalent:ġ. Minesweeper is, fundamentally speaking, a constraint satisfaction problem. Since I taught Pearls in chat these days how do use the covering sets method, I might as well post here too:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |