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 kommentar(er)
