Solving Minesweeper with Set Theory

[@andrewhubbard4043]

I wonder, can your algorithm find the safe cell in: x 3 x ? x 2 ? ? ? x 2 ? ? 5 x x 2 2 x x It's not too hard to solve by hand, but requires looking at 4 sets

[@wilfwaldron]

That is a really fantastic example, I don't think it can solve it! imgur.com/Wm0ABwP Here is a diagram explaining why for anyone interested Essentially we need to see that 2 cells contain at least one mine, forcing a safe cell somewhere else. But because of how the sets are created initially (around each number), the only set that contains these 2 mine cells also contains the safe cell. I imagine that there would be some way to enhance the method by changing the logic so it also looks for situations where it can combine sets (since at the moment all new sets are subsets of existing ones) Really really nice example.

[@schazz3929]

Replace your 5 with a 6 and you have a better example, because in this position, after clearing the safe tile and marking the guaranteed mine, you have a 50/50 situation, whereas if it was a 6 you would have a guaranteed win :)

[@andrewhubbard4043]

​@schazz3929 Quite the opposite, with a 6, you have 5 mines around it in the rightmost 2 columns. You flag the mine and can't go further. With a 5, you know the tile above it is safe, and you know whether the tile in the top row is safe. If it is, you can solve the 2x2 as well as whatever is off the example toward the top right. If not, you have to guess anyway. Maybe I forgot to mention, but that example is a subset of a ~80% completed board.

[@schazz3929]

@@andrewhubbard4043 You are correct, my mistake My brains must've temporarily leaked out at the time I wrote this comment, I apologize.

[@chappuis73]

Wow, this was a really cool and well-explained video! I thought I was watching someone with like 50-100k subscribers, my jaw dropped when I saw the actual subscribers/views count

[@zetsubou-san8390]

Have you played the game Bombe before? It basically plays just like this. Instead of discovering the mines with the clues given, you're writing formal rules that specify what those clues logically dictate.

[@clementbarbara7741]

What an amazing game

[@antibehroz7304]

There are some minesweeper variations that generate boards that guarantee that no situation comes up where you must guess if you go about the board logically, I usually play one called "Mines from Simon Tatham's Portable Puzzle Collection"

[@MarkWiemer]

High quality vid! I love Minesweeper as a testbed for math stuff. I was so excited when I learned it was NP-hard, maybe one day we'll truly solve it ;)

[@LesslyPoint]

This is excellent! Very cool applications of set theory. I usually see trial and error based approaches with mine sweeper, so this is a great change of pace

[@Akronymus_]

Makes me think of the game "Bombe" which is a minesweeper where you only solve them via making rules.

[@ninam6826]

Very cool! Nicely formated presentation as well!

[@gurchyy]

I believe this method can also solve situations that require knowing the number of remaining mines, if you create a set that covers every remaining cell on the board, with number of mines equal to the number remaining.

[@ouzoloves]

Very nicely explained and excellent algorithm, I had to stop and work out how it knew the 2 clear cells next to the 1 in the top left corner of the intermediate. Though I think in normal play, the clearing of the nearby cells would easily result in knowing where the bomb touching the 1 was, it was interesting to see that it can be logically worked out at that stage. Do you find yourself recogising any of the more advanced patterns at all when playing?

[@wilfwaldron]

Yes that surprised me as well. As for seeing patterns, sort of, you can make your own judgement with this video: kzbin.info/www/bejne/sH_Jn5aLhLyni8U It is just me solving and explaining some of it.

[@sinom]

People have already mentioned it but you can implement a way of solving similar to this in bombe (+ a bunch of other stuff) These "groups" you're talking about are called "regions" in that game, any hint generates base regions and you can define rules that then act on the regions to either generate more regions or reveal a cell

[@gavinkleinebecker3672]

Now I want to see how you calculate probabilities with set theory!

[@ThomasEdits]

"thats pretty cool in my opinion, hope you enjoyed, bye bye" love people just sharing their random fascinations

[@Flourish38]

If you want to get cheeky with your hash function for the groups, you might be able to make it something like index of center cell + bit mask indicating the shape of the group. It doesn’t seem like you’re struggling with performance, though :P

[@hans-edwardjaquegranstrom3486]

Would you be ok with sharing the source code? Fun to play around with and learn from :)

[@wilfwaldron]

Go for it! There is a deployment/code here. aosuk.github.io/MS/index.html there are instructions on the page itself. Though, good luck if you are on mobile... I want to warn and apologize to you about the code, I made the entire clone JUST to test if this set idea worked, so it is incredibly rushed, I am not proud of it. This might be more useful to read, it just talks about how the board is stored, and what operations are done on sets. pastebin.com/8gLsQAee I would like to make this very cleanly in java, and run simulations to collect data about the exact strength of the solver.

[@hans-edwardjaquegranstrom3486]

​@@wilfwaldron Awesome, thank you! No need to apologize for the code. I'd rather look at rushed code than no code :D If you end up rewriting it in Java I'd love to see that code as well, no pressure! :D

[@quantumsoul3495]

I would have prefered a bigger pointer

[@cipeman3498]

interesting! i wonder how endgame total mine counting techniques could be applied in this framework? i also wonder if these ideas could apply to any of the variants from 14 minesweeper variants 1 or 2

[@hhhhhh0175]

just the other day i was looking at that combinations example on minesweeper online and was like "there's obviously still logic here" e.g. the 1 in the top right corner reduces the 3 on the left into a 1, which reduces the 2 below into a 1, which reduces the 2 below and to the left to a 1, which combines with the 3 below to give a safe square and a mine

[@vilkillian]

Basically a convolution

[@nyphakosi]

this sounds a lot like how the game Bombe on steam works!

[@Patashu]

@@wilfwaldron Join us Bombe players and stare into the abyss :D

[@GoldenArbiter01]

Now you just need it to click the green boxes for you

[@serverinvihatuin2654]

Epic