Although there are some places where your guess would be "1 out of 2" but maybe another spot would be "2 out of 3" , or maybe even as good as "7 out of 8" . So a guess shouldn't really be random out of all of the remaining tiles.
For more effective screensaving, you'll want to randomly offset the lines so they aren't in the same place every time. Possibly also lower the contrast. For LCD screens, you'll probably want a light theme, as white pixels are the "relaxed" state for LCDs (AFAIK). For OLED, you'll want a dark theme.
I knew someone who coded themselves out of games. This was around when Sudoku first became popular--he basically said "if I can fully solve Sudoku by programming a solver for it, I've effectively solved every Sudoku ever, and I never have to play the game again. Same for every other solvable game." (I assume he was at the time asked a lot if he played lol)
Except that sudoku is actually really hard to solve efficiently if you scale it up massively, unlike something like minesweeper which scales up linearly Sudoku is an NP problem as far as we humans know, like it's really difficult to solve massive boards of sudoku in any reasonable amount of time for a computer
@@paradox9551 solving a classic 9x9 board of Sudoku is a solved problem, and I'm pretty sure that's what the guy was referring to, not having an arbitrary board size.
@@paradox9551 I once made a sudoku solver, trying to solve it like a person would. Implementing my strategies was really hard, and it would get stuck on harder puzzles. Then I implemented a simple recursive algorithm that solved it insanely fast that was also easy to implement. It was very amusing, but also disheartening.
Yep... this is what I do. I have played a lot of Sudoku in the past, but then lost all interest in playing it, and only had interest in using lots of different programming techniques (simple backtracking, more advanced backtracking like Knuth's DLX algorithm, constraint programming, heuristics, evolutionary algorithms, swarm algorithms, neural nets, etc) to solve Sudoku boards and to analyze the mathematics of Sudoku. (I'm a combinatorial design theorist, and given that Sudoku is a great combinatorial design with many representations such as graph colourings, it was inevitable.) There's a great book, Taking Sudoku Seriously, which I recommend for anyone interested in the math of Sudoku. I dislike games that cannot be posed cleanly as combinatorial design problems, such as some of the "variants" of Sudoku.
To improve the style of the code, I have a few simple suggestions, you can improve the indentation wall by refactoring the if condition statement to if not condition return/continue. Also, the part that checks for nearby cells can be refactored to iterate over a delta vector and extract it into a function, which seems to be used in many places. Happy coding :)
@@HaveaLukeatthis instead of implementing a bunch of rules, you could calculate the chance of each square being a mine, then choose the square with the least chance. 1000 iq
@@redcrewmate1813 Huh... If only I didn't have too many projects on my hands :D I would love to see a real-time display of a solver with a color gradient filter over the board which shows which parts are the most risky at the moment. I would also be interested to see how reliable this method is, just for science.
@@redcrewmate1813 i know this is more for fun, but if they really wanted a screensaver that you are not supposed to play they could have just made the autosolver know where the bombs are so it cant fail tho this method probably looks more realistic
Sometimes, a minesweeper puzzle is actually unsolvable. If your solver finds one of these, I suggest having it cheat a little and give itself a hint, revealing a clear tile.
4:31 The solver appears to have revealed a 6, revealed a tile that was obviously a bomb as there were only 6 unrevealed tiles next to the 6, and then proceeded to flag another tile before the solver's failure fully registered.
I'm assuming the AI was guessing one of the tiles to the north of the 6 and then revealing all the other tiles based on the 2, either to the east or west of the unknowns, having two flags next to it. It hit the 6 first, but was still in the function to reveal all unmarked tiles, so it didn't realize the 6 showed that the guess was wrong. You'd have to code it to check the "standard" logic for each tile reveal caused by a guess, possibly reverting the initial guess in the process.
I sometimes played this game, but ultimately when I actually had the patience to try solve a hard board, I always ended up in a situation where I had to guess, and always got it wrong...
Code Bullet looked at the problem 4 years ago. His solving algorithm is a bit more fancy than yours. If it finds a case where 1 in 3 configurations has a bomb while its neighbors have bombs in 2 in 3 configurations, it will select the 1 in 3 location instead of the 2 in 3 locations reducing the likelihood of bombs going off.
I wanted to create my own puzzle solver engine for a puzzle game that I dont know the name for. its a grid of pipes and ends. all you can do is rotate the blocks in place to move the connections around. everything must connect to the center tile. I learned quickly that the edges should be solved first since all edge tiles cannot have a connection. so any "T" shape must always face inwards. allowing you to "lock" the tile and mark it as solved. I thought it would be a fun task to make a program that would solve the puzzles
For the logic around the 02:40 mark, it would make sense to pause the normal "iterating over a bunch of tiles to look for trivial solves" and to look specifically around the two cells forming an XOR and examine the surrounding cells with that characteristic in mind. That way you could blast through most cells very quickly and only apply advanced logic when needed.
yeah, the part at 2:30 is what I call the law of 1-2-1. Wherever you see that pattern, or anything that reduces to that pattern, then the flags go adjacent to the 1's and the center is cleared and depending on how you arrived at 1-2-1, you may also clear whatever is on the other side of those 1's.
What if you tried alternative tile shapes? Like hexagons or triangles? Maybe even alternative spacial geometries like the surface of a torus or a cube? That'd be cool, and probably a fun challenge to figure out lol
@@xdarin_ there's another problem: tile 2 above that 5 can't exist because there are 3 mines near it. And two upper 2s can't exist too, because they have only 1 bomb nearby.
@@fantastikboom1094 The 2 above the 5 is actually OK - the 5 is currently surrounded by 6 unrevealed tiles (one of which is flagged). The three tiles below the 5 are all bombs and the tile to the left of the 2 is also a bomb, the tile to the left of the 5 however is clear. As for the upper twos that is just the way I took the screenshot - the grid actually extends beyond the edges of this shot, sorry for the confusion!
At 2:23, there's a 3 along the left side that can't have 3 mines next to it. There are only two places to put mines next to it. The 2 along the left side isn't possible either.
I did the same thing with my Sudoku solver (which will also do puzzles that overlap/have common squares). I don't do the exhaustive search from the ComputerPhile videos (he did his in Python as well), but rather tried to articulate "what do I do when I solve?" into algorithmic checks of escalating complexity (Level 1, look for the obvious. Don't find any? Level 2, look for slightly harder to find things. Only make a few pencil marks? Level 3... etc. Every time an actual guess is made I drop all the way back to Level 1 complexity and start over until I've exhausted all techniques without any guesses or new pencil marks). It doesn't know advanced techniques because... well... neither do I hehehe nor could I articulate those techniques I don't think, but it does pretty well.
Okay, different angle on solving the maybe situation in plaintext: Until a new number is revealed, treat each cell as a rolling percentage of likelihood of a bomb. The first 2 knows that those two cells each have a 50% chance of being a bomb, so for the value of "likelihood of a bomb" set a value of 0.5, and move onto the next digit down the line. The next two adds up the values of all cells it sees to get the total likelihood of bombs placed, reading flagged bombs as a 1, and numbers, spaced, and unclicked cells as 0. It sees that the likely number of bombs placed is 1 (if it were somehow 1.25 or something, it would truncate at the ones place, and do the math from there) so it knows that in any 0 likelihood unclicked cells it sees, they must hold *number in cell* minus *bombs placed value* bombs. in this case there's only one 0 probability unclicked cell the number sees, so it puts all 1 bomb into that cells value. Then the logic decided if flags must be placed. Any cell who's probability of a bomb is one or greater, gets flagged as a bomb, so the cell directly in front of the 1 gets flagged. The logic then reverses the order of thinking and says "does this cause any number I'm touching to be maxed out?" If it finds more than one, that doesn't matter, but if it doesn't find any, the logic would have then continued down the line of numbers, erasing memory of values holding probability of a bomb, continuing to try and find a maxed out number. When it maxes out a number, that number flips all remaining unclicked cells to safe, then starts the process all over again. I'm the kind of guy who feels like he's good at talking out programming logic, but no good at actually writing it. I have no idea if that's a valuable skill, and I'm just hopeful that I made some level of sense, and all respect for having the knowledge to make that programming happen. I hope the idea helps get the juices flowing, should you want to try to make your code leaner.
I made a minesweeper screensaver a couple of years ago. I made mine scroll infinitely so it looks like an infinite minefield. I also cheated a little and let it choose a random safe tile to clear when it was stuck.
I played this obsessively when it first came out - so much so that I "used" it to think about other things, keeping the overactive part of my brain occupied. When it became too "easy," I stopped dropping bomb markers so that I had to rely just on the number patterns. It was especially satisfying to finish a board with no bomb markers in view. He left out that the original game displays a count of the total bomb markers remaining, which was one of the parameters for resetting the board. Getting to only 5 bombs left and 20 or 30 unmarked squares made it easier to guess safely. The original game "cheated" in that the very first square was ALWAYS NOT a bomb - which means the pattern couldn't be set until AFTER the players first move. (A few times, the first click revealed an 8, though, making the next click VERY risky! 😁
You can make it 100% solvable since you create the field and therefore know where the mines are. When your solver is stuck, "guess" any empty tile, or one that is next to an empty/number tile.
I have a suggestion for you, I'd implement it but I only have my work laptop atm and can't download anything executable. Make an infinite scrolling mineweeper solver, prioritise solving on the left of the screen, and when the whole let edge is solved move one over, repeat infinitely.
Fun fact, you actually only need the global flag on a variable if you want to set a variable from an outer scope. Python actually propagates outwards and finds the first scope with a matching reference. You only use global when you want to write to the highest form of a variable, usually a global. It's actually frowned upon to use globals usually, as it makes it difficult to see where a variable has been changed at, but that doesn't mean it has no use, obviously it's there for a reason. Anyways, thought I'd let you know about that, cheers!
If it gets to a point where a guess is required it just picks one at random and reveals it - if it happens to be a bomb then it will fail and start over with a new set of bombs
@@HaveaLukeatthis There are some minesweeper implementations where the generated boards are guaranteed to be fully solvable with no guessing required. I know Simon Tatham's version is like that for example.
At least at the mine density I always play for custom games (= ratio for expert game, or one mine per 4.8 tiles) I almost always end up with multiple 50/50 guesses unsolvable by logic so it becomes having to win (N) coin tosses.
by assigning entropy to each square is best method to solve minesweeper. like reveled square has entropy 0. distribute value of square to surrounding not reveled squares. like if there are 2 not reveled squares around '1' then give them 1/2 & 1/2 entropy. squares having entropy 1 is bomb.
You can use something like convolutions to solve this. Store a probability value for each unrevealed tile neighboring a revealed tile. For all revealed, numbered tiles, offset the probability values of their unrevealed neighbors so they add up to the value they show. When an unrevealed tile is neighbor to N revealed numbered tiles, average their offsets computed by their neighbors. Repeat this until convergence. Reveal the tile with the lowest probability. Repeat until all tiles with a probability less than 0.5 are revealed.
Oh snap. I might have to code this in c#. Years ago I got bored and coded reversi client server over tcp. That was fine and similar logic with checking neighbors.
The board at 3:39 is not possible IMO. The lower number 3 on the left being on the edge of the board implies that the two tiles to the right of it are explosives, as well as the tile directly beneath it. So the number 2 gets satisfied by the two tiles that were to the right of that number 3 - but then there has to be an explosive directly below the number 1 to the right of that number 3, which then means there are three explosives on the perimeter of that number 2. That number 2 should therefore be a 3. Or there must be more tiles to the left of that lower number 3 (it can’t be on the edge of the board).
I have been toying with the idea to make a solver, but the purpose is to create 100% solvable games, where if you play fully by logic you do not need random to finish it. One thing I see is that the opening move needs to be "pre played", ie one does not choose the first click.
could the board be created/populated AFTER player's first click, making the solver define as bomb-less the tile that the user decided to click when the game began?
all things considered this is really cool! though it defeats the main purpose of a screensaver, since there's many static elements that would burn into your screen
At 2:45, that board is not possible. Reasons being is that 1. Because we can clearly see that the two sides of the board both show borders, therefore the top 3 cannot be possible as there are only 2 mines surrounding it in an 3x3 area (excluding the border ones). Thus the top 3 cannot be possible. 2. The bottom 3 is possible as it shows that there are 3 mines surrounding it and that there are only 3 available tiles, however using that logic, the 2 beside it will also be clear, leaving the 2122 pattern being like: 3 * 2 1 2 2 * * * x x * * 2 As you can see the top right most 2 cannot be possible as there are 3 mines beside it based on the boards logic
I don't mean to nitpick, but the board at 5:11 had a tile that could have been confidently cleared, but the game guessed (and blew up.) In the top right, there is a 4 with an unflagged bomb below it. 2 tiles to the right of that bomb could have been cleared, given what was known at the time. My Python isn't very strong, so I doubt I can realistically dig up why the code didn't find that.
True, I could not make a configuration where the numbers shown remained valid if a bomb was in that square. How did you find it? I could not reason a logic except by guessing and trying to disprove it.
@@luizalbertolausdarosa6819 It's hard to explain tile locations in text, but let's take that unflagged bomb under the 4 as a starting place. Down, down, right of that is a 2. That 2 has a flagged mine and 2 untouched tiles. Exactly 1 of those 2 must be a mine. Above that 2 is a 3. Around it there is one flagged mine, the 2 untouched tiles from before (where we know 1 of those 2 is a mine), and 3 untouched above it. So, to satisfy this 3, we need: (1) the flagged mine, (2) 1 of those 2 from before (left and right of the 3), and (3) one of the 3 untouched tiles above it. So, exactly one of the 3 untouched tiles above the 3 is a mine. The last step is to look at the 4 that is up up left of the 3. It says that one of the 2 below it must be a mine. Well, if that's the case, then it would satisfy the (3) from before. Since the 4 wouldn't be satisfied with a mine sitting to the top right of the 3, there can't be a mine there. Did that explain?
Would there be any possible way you can make a dark mode version of this, and upload it Wallpaper Engine? I would like to have something like this as a Wallpaper Engine application.
You can download the python code from the description and configure it to run full screen but its not technically a screen saver at the moment - I'm looking into a couple of ways I might be able to turn it into an actual screen saver though
infinite scrolling mine sweeper, it tries to solve the top-most cells it can, it can't reveal anything about the bottom row of cells, every time a top row is cleared shift everything up and add random bombs, maybe keeping the top 3rd ish solved and slowly scrolling and adjusting the speed of the solver to keep about 2/3rds +/-5% of the cells solved at any given time
Amazing! Are there any situations where two hypotheses are required? like, assuming one tile is maybe cleared reveals some data but not enough, so you need to assume/guess about another tile inside the first assumption?
"When the autosolver is confused, it will guess and pick a random tile, usually failing"
Realistic.
Yeah
me too solver, me too
Although there are some places where your guess would be "1 out of 2" but maybe another spot would be "2 out of 3" , or maybe even as good as "7 out of 8" . So a guess shouldn't really be random out of all of the remaining tiles.
@@David__U usually i click random tiles when i don't get an opening at the start
Isn't it what a non-auto solver do as well? :J
For more effective screensaving, you'll want to randomly offset the lines so they aren't in the same place every time. Possibly also lower the contrast.
For LCD screens, you'll probably want a light theme, as white pixels are the "relaxed" state for LCDs (AFAIK). For OLED, you'll want a dark theme.
the line offset can be handled by randomizing board size
if the whole thing scrolled infinitely diagonally and just kept solving it would screensave better And be so so satisfying
Actual great hook, made me want to watch the entire video from the start.
Please make more videos!
Thanks! I've got a few more projects I'm working on at the moment so will hopefully have another video out soon
I knew someone who coded themselves out of games. This was around when Sudoku first became popular--he basically said "if I can fully solve Sudoku by programming a solver for it, I've effectively solved every Sudoku ever, and I never have to play the game again. Same for every other solvable game." (I assume he was at the time asked a lot if he played lol)
Except that sudoku is actually really hard to solve efficiently if you scale it up massively, unlike something like minesweeper which scales up linearly
Sudoku is an NP problem as far as we humans know, like it's really difficult to solve massive boards of sudoku in any reasonable amount of time for a computer
@@paradox9551 solving a classic 9x9 board of Sudoku is a solved problem, and I'm pretty sure that's what the guy was referring to, not having an arbitrary board size.
Minesweeper is also np
@@paradox9551 I once made a sudoku solver, trying to solve it like a person would. Implementing my strategies was really hard, and it would get stuck on harder puzzles. Then I implemented a simple recursive algorithm that solved it insanely fast that was also easy to implement. It was very amusing, but also disheartening.
Yep... this is what I do. I have played a lot of Sudoku in the past, but then lost all interest in playing it, and only had interest in using lots of different programming techniques (simple backtracking, more advanced backtracking like Knuth's DLX algorithm, constraint programming, heuristics, evolutionary algorithms, swarm algorithms, neural nets, etc) to solve Sudoku boards and to analyze the mathematics of Sudoku. (I'm a combinatorial design theorist, and given that Sudoku is a great combinatorial design with many representations such as graph colourings, it was inevitable.) There's a great book, Taking Sudoku Seriously, which I recommend for anyone interested in the math of Sudoku.
I dislike games that cannot be posed cleanly as combinatorial design problems, such as some of the "variants" of Sudoku.
To improve the style of the code, I have a few simple suggestions, you can improve the indentation wall by refactoring the if condition statement to if not condition return/continue. Also, the part that checks for nearby cells can be refactored to iterate over a delta vector and extract it into a function, which seems to be used in many places. Happy coding :)
Thanks for the suggestions, I'll have a look into this!
@@HaveaLukeatthis instead of implementing a bunch of rules, you could calculate the chance of each square being a mine, then choose the square with the least chance. 1000 iq
@@redcrewmate1813 Huh... If only I didn't have too many projects on my hands :D I would love to see a real-time display of a solver with a color gradient filter over the board which shows which parts are the most risky at the moment.
I would also be interested to see how reliable this method is, just for science.
@@redcrewmate1813 i know this is more for fun, but if they really wanted a screensaver that you are not supposed to play they could have just made the autosolver know where the bombs are so it cant fail
tho this method probably looks more realistic
I feel like CodeAesthetic has an influence here :)
Sometimes, a minesweeper puzzle is actually unsolvable. If your solver finds one of these, I suggest having it cheat a little and give itself a hint, revealing a clear tile.
When i get to ambiguous areas, i find probability analysis useful to increase my chances
You can always play a version that ensures solubility without guessing
@@vermilisix I actually like the ambiguous moments, it's a lot like life. Sometimes you gotta take a chance, and sometimes you screw up 🤣
Those areas can sometimes be solved by counting total bombs left
@@aierce Not always. If you're left with a 50/50 at the end with one bomb left, bomb count doesn't help, although it can solve some problems.
4:31 The solver appears to have revealed a 6, revealed a tile that was obviously a bomb as there were only 6 unrevealed tiles next to the 6, and then proceeded to flag another tile before the solver's failure fully registered.
Good catch. That shows the solver has flaws in it.
I'm assuming the AI was guessing one of the tiles to the north of the 6 and then revealing all the other tiles based on the 2, either to the east or west of the unknowns, having two flags next to it. It hit the 6 first, but was still in the function to reveal all unmarked tiles, so it didn't realize the 6 showed that the guess was wrong. You'd have to code it to check the "standard" logic for each tile reveal caused by a guess, possibly reverting the initial guess in the process.
I sometimes played this game, but ultimately when I actually had the patience to try solve a hard board, I always ended up in a situation where I had to guess, and always got it wrong...
Amazingly high quality for a channels second vid. I would gladly watch more videos of you coding things.
3:20 that 3 in the 3rd row on the left side is giving me so much anxiety
LOL. Good spot!
Code Bullet looked at the problem 4 years ago. His solving algorithm is a bit more fancy than yours. If it finds a case where 1 in 3 configurations has a bomb while its neighbors have bombs in 2 in 3 configurations, it will select the 1 in 3 location instead of the 2 in 3 locations reducing the likelihood of bombs going off.
Never wouldve guessed this was a small channel, amazing work
Thank you for explaining minesweeper in such a clear manner, I always had trouble figuring out what the numbers actually meant.
Underrated
I can't believe that you don't have 1k subscribers yet
I wanted to create my own puzzle solver engine for a puzzle game that I dont know the name for.
its a grid of pipes and ends. all you can do is rotate the blocks in place to move the connections around. everything must connect to the center tile.
I learned quickly that the edges should be solved first since all edge tiles cannot have a connection. so any "T" shape must always face inwards. allowing you to "lock" the tile and mark it as solved.
I thought it would be a fun task to make a program that would solve the puzzles
Years ago, I made my sister an automatic solitaire game, that played automatically. It was good, too. She didn't think it was as funny as I did.
For the logic around the 02:40 mark, it would make sense to pause the normal "iterating over a bunch of tiles to look for trivial solves" and to look specifically around the two cells forming an XOR and examine the surrounding cells with that characteristic in mind. That way you could blast through most cells very quickly and only apply advanced logic when needed.
yeah, the part at 2:30 is what I call the law of 1-2-1. Wherever you see that pattern, or anything that reduces to that pattern, then the flags go adjacent to the 1's and the center is cleared and depending on how you arrived at 1-2-1, you may also clear whatever is on the other side of those 1's.
241 subscribers? This video was amazing keep it going bro I believe in you
So that's why the 3D pipes screen saver was so popular!
I like this and I hope you get even more followers. Subscribed.
Bruh how tf does this only have 94 views. Very impressive stuff keep it up 👍
Thanks very much, I appreciate it!
Love the result. Very smart way at speeding it up, as well.
What if you tried alternative tile shapes? Like hexagons or triangles? Maybe even alternative spacial geometries like the surface of a torus or a cube? That'd be cool, and probably a fun challenge to figure out lol
Yes this is a cool idea!
I recommend the game "14 minesweeper variants" it has a built in SAT solver to procedurally generate puzzles that require complicated logic
3:56 Um, why this image is so wrong...
Wait... Oh yeah it's wrong
Number 5 tiles didn't exist in ms minesweeper, right?
@@xdarin_ there's another problem: tile 2 above that 5 can't exist because there are 3 mines near it. And two upper 2s can't exist too, because they have only 1 bomb nearby.
@@fantastikboom1094 The 2 above the 5 is actually OK - the 5 is currently surrounded by 6 unrevealed tiles (one of which is flagged). The three tiles below the 5 are all bombs and the tile to the left of the 2 is also a bomb, the tile to the left of the 5 however is clear.
As for the upper twos that is just the way I took the screenshot - the grid actually extends beyond the edges of this shot, sorry for the confusion!
At 2:23, there's a 3 along the left side that can't have 3 mines next to it. There are only two places to put mines next to it. The 2 along the left side isn't possible either.
He leaves it on screen for nearly ¼ of the video! 3:53
Also the 2 above the unsolved tile cannot be a 2 as the other adjacent tiles are all solved, leaving only 1 possible bomb
yeah that whole example was just wrong
"hi, i made a" is its own genre now. what a world.
Very cool! The original minesweeper had a maybe flag that I used extensively :-)
Awesome quality, keep up the good work
Dude this is awesome. Subscribed!
Only 12 subs? This channel is super underrated I will be the thirteenth sub
Thanks, appreciate it!
Looks great, you've earned a subscriber. Keep it up!
Chopin is a nice touch
Get the puzzle generator to talk directly with the puzzle solver and cut out that thing in the middle
I did the same thing with my Sudoku solver (which will also do puzzles that overlap/have common squares). I don't do the exhaustive search from the ComputerPhile videos (he did his in Python as well), but rather tried to articulate "what do I do when I solve?" into algorithmic checks of escalating complexity (Level 1, look for the obvious. Don't find any? Level 2, look for slightly harder to find things. Only make a few pencil marks? Level 3... etc. Every time an actual guess is made I drop all the way back to Level 1 complexity and start over until I've exhausted all techniques without any guesses or new pencil marks). It doesn't know advanced techniques because... well... neither do I hehehe nor could I articulate those techniques I don't think, but it does pretty well.
Okay, different angle on solving the maybe situation in plaintext: Until a new number is revealed, treat each cell as a rolling percentage of likelihood of a bomb. The first 2 knows that those two cells each have a 50% chance of being a bomb, so for the value of "likelihood of a bomb" set a value of 0.5, and move onto the next digit down the line. The next two adds up the values of all cells it sees to get the total likelihood of bombs placed, reading flagged bombs as a 1, and numbers, spaced, and unclicked cells as 0. It sees that the likely number of bombs placed is 1 (if it were somehow 1.25 or something, it would truncate at the ones place, and do the math from there) so it knows that in any 0 likelihood unclicked cells it sees, they must hold *number in cell* minus *bombs placed value* bombs. in this case there's only one 0 probability unclicked cell the number sees, so it puts all 1 bomb into that cells value.
Then the logic decided if flags must be placed. Any cell who's probability of a bomb is one or greater, gets flagged as a bomb, so the cell directly in front of the 1 gets flagged. The logic then reverses the order of thinking and says "does this cause any number I'm touching to be maxed out?" If it finds more than one, that doesn't matter, but if it doesn't find any, the logic would have then continued down the line of numbers, erasing memory of values holding probability of a bomb, continuing to try and find a maxed out number. When it maxes out a number, that number flips all remaining unclicked cells to safe, then starts the process all over again.
I'm the kind of guy who feels like he's good at talking out programming logic, but no good at actually writing it. I have no idea if that's a valuable skill, and I'm just hopeful that I made some level of sense, and all respect for having the knowledge to make that programming happen. I hope the idea helps get the juices flowing, should you want to try to make your code leaner.
I made a minesweeper screensaver a couple of years ago. I made mine scroll infinitely so it looks like an infinite minefield. I also cheated a little and let it choose a random safe tile to clear when it was stuck.
I played this obsessively when it first came out - so much so that I "used" it to think about other things, keeping the overactive part of my brain occupied. When it became too "easy," I stopped dropping bomb markers so that I had to rely just on the number patterns. It was especially satisfying to finish a board with no bomb markers in view.
He left out that the original game displays a count of the total bomb markers remaining, which was one of the parameters for resetting the board. Getting to only 5 bombs left and 20 or 30 unmarked squares made it easier to guess safely.
The original game "cheated" in that the very first square was ALWAYS NOT a bomb - which means the pattern couldn't be set until AFTER the players first move. (A few times, the first click revealed an 8, though, making the next click VERY risky! 😁
You can make it 100% solvable since you create the field and therefore know where the mines are. When your solver is stuck, "guess" any empty tile, or one that is next to an empty/number tile.
3:40 the top 3 is wrong, there are only two tiles in its vicinity and no flags
There are more wrong things with it as well. I stopped the video here, made this comment and left.
@@ookamiueru pretty sure this is just a cropped section of a whole board Einstein
Please put this on a webpage so I can make it my desktop wallpaper!
I have a suggestion for you, I'd implement it but I only have my work laptop atm and can't download anything executable.
Make an infinite scrolling mineweeper solver, prioritise solving on the left of the screen, and when the whole let edge is solved move one over, repeat infinitely.
Wow, I had the same idea over a year ago but had to abandon it due to horrible code base. Thanks for making this!
It would be nice if you would design an always beatable minesweeper. I’ve heard they’ve been programmed but never seen one.
This would make for a fantastic After Dark screensaver.
2:23 That's an odd number 3... On the edge, with 4 of 6 spaces revealed....
Now all we need is a dark version
Fun fact, you actually only need the global flag on a variable if you want to set a variable from an outer scope. Python actually propagates outwards and finds the first scope with a matching reference. You only use global when you want to write to the highest form of a variable, usually a global. It's actually frowned upon to use globals usually, as it makes it difficult to see where a variable has been changed at, but that doesn't mean it has no use, obviously it's there for a reason. Anyways, thought I'd let you know about that, cheers!
Luke, would you mind telling what happens if the algorithm stumbles on a 50/50 guess? I remember getting some 50/50 when I used to play the game.
If it gets to a point where a guess is required it just picks one at random and reveals it - if it happens to be a bomb then it will fail and start over with a new set of bombs
@barutaji that sounds cool, but sometimes the probability of the bomb does not change by the order of the square you open :(
@@HaveaLukeatthis There are some minesweeper implementations where the generated boards are guaranteed to be fully solvable with no guessing required. I know Simon Tatham's version is like that for example.
At least at the mine density I always play for custom games (= ratio for expert game, or one mine per 4.8 tiles) I almost always end up with multiple 50/50 guesses unsolvable by logic so it becomes having to win (N) coin tosses.
Counting the bombs also helps at dead-ends
you should make a 10-hour video of the robot solving it. maybe it could have music or something?
Wow I never considered an algorithm that solves via proof by contradiction. How quaint
It would be interesting to set this up to scroll infinitely
This made me want to play minesweeper
Liked for your sharing the code.
by assigning entropy to each square is best method to solve minesweeper. like reveled square has entropy 0. distribute value of square to surrounding not reveled squares. like if there are 2 not reveled squares around '1' then give them 1/2 & 1/2 entropy. squares having entropy 1 is bomb.
I feel called out by the intro lmao
wayy too underrated
This already looks better than may of those crappy screensavers in Linux's Xscreensaver :q
You can use something like convolutions to solve this. Store a probability value for each unrevealed tile neighboring a revealed tile. For all revealed, numbered tiles, offset the probability values of their unrevealed neighbors so they add up to the value they show. When an unrevealed tile is neighbor to N revealed numbered tiles, average their offsets computed by their neighbors. Repeat this until convergence. Reveal the tile with the lowest probability. Repeat until all tiles with a probability less than 0.5 are revealed.
Oh snap. I might have to code this in c#. Years ago I got bored and coded reversi client server over tcp. That was fine and similar logic with checking neighbors.
Wait this whole time its been "bombs in the surrouding 8 squares" and not "spaces away that the nearest bomb is"? Wow I've been playing wrong
The board at 3:39 is not possible IMO. The lower number 3 on the left being on the edge of the board implies that the two tiles to the right of it are explosives, as well as the tile directly beneath it. So the number 2 gets satisfied by the two tiles that were to the right of that number 3 - but then there has to be an explosive directly below the number 1 to the right of that number 3, which then means there are three explosives on the perimeter of that number 2. That number 2 should therefore be a 3. Or there must be more tiles to the left of that lower number 3 (it can’t be on the edge of the board).
What happened at 5:11? It looks like the solver hit a bomb next to a two tile? Why would it be guessing when the 2 is only touching 2 squares?
I have been toying with the idea to make a solver, but the purpose is to create 100% solvable games, where if you play fully by logic you do not need random to finish it. One thing I see is that the opening move needs to be "pre played", ie one does not choose the first click.
could the board be created/populated AFTER player's first click, making the solver define as bomb-less the tile that the user decided to click when the game began?
Man you need more than 30 subs
I guess all I can do is add 1
fr he has 31 subscriber
all things considered this is really cool! though it defeats the main purpose of a screensaver, since there's many static elements that would burn into your screen
At 2:45, that board is not possible. Reasons being is that
1. Because we can clearly see that the two sides of the board both show borders, therefore the top 3 cannot be possible as there are only 2 mines surrounding it in an 3x3 area (excluding the border ones). Thus the top 3 cannot be possible.
2. The bottom 3 is possible as it shows that there are 3 mines surrounding it and that there are only 3 available tiles, however using that logic, the 2 beside it will also be clear, leaving the 2122 pattern being like:
3 * 2 1 2 2 *
* * x x * * 2
As you can see the top right most 2 cannot be possible as there are 3 mines beside it based on the boards logic
The borders you can see in the image are not actually the edges of the grid, it's just the way I took the screenshot. Sorry for the confusion!
@@HaveaLukeatthis Ah okay! Sounds good haha, thought it was quite weird as you do seem pretty experienced in minesweeper haha
Maybe a Tetris solver will please your brain similarly
You should try to write a solver for SkiaLogic type puzzles.
Very well done!!! Why is it that our type of channels have so few subscribers? Is it that it's too niche? Too nerdy? Too complex?
I don't mean to nitpick, but the board at 5:11 had a tile that could have been confidently cleared, but the game guessed (and blew up.) In the top right, there is a 4 with an unflagged bomb below it. 2 tiles to the right of that bomb could have been cleared, given what was known at the time. My Python isn't very strong, so I doubt I can realistically dig up why the code didn't find that.
True, I could not make a configuration where the numbers shown remained valid if a bomb was in that square. How did you find it? I could not reason a logic except by guessing and trying to disprove it.
@@luizalbertolausdarosa6819 It's hard to explain tile locations in text, but let's take that unflagged bomb under the 4 as a starting place. Down, down, right of that is a 2. That 2 has a flagged mine and 2 untouched tiles. Exactly 1 of those 2 must be a mine. Above that 2 is a 3. Around it there is one flagged mine, the 2 untouched tiles from before (where we know 1 of those 2 is a mine), and 3 untouched above it. So, to satisfy this 3, we need: (1) the flagged mine, (2) 1 of those 2 from before (left and right of the 3), and (3) one of the 3 untouched tiles above it. So, exactly one of the 3 untouched tiles above the 3 is a mine. The last step is to look at the 4 that is up up left of the 3. It says that one of the 2 below it must be a mine. Well, if that's the case, then it would satisfy the (3) from before. Since the 4 wouldn't be satisfied with a mine sitting to the top right of the 3, there can't be a mine there.
Did that explain?
the highlighted tiles during the explanation are pretty hard to see
2:23 wait, how is there a 3 on the left with only 2 tiles close to it
whAT
really cool actually!
Would there be any possible way you can make a dark mode version of this, and upload it Wallpaper Engine? I would like to have something like this as a Wallpaper Engine application.
2:23 top left most three shouldnt be there, since only two spaces around it are undiscovered and none of the discovered spaces are bombs.
What is the time complexity of the solver?
very well made video!
wallpaper engine when?
Only 800 subs? Come on! Take mine!
It’s proof by contradiction!
Is their any way to turn this into an actual screen saver?
This is pretty nice!.. So, can i use it as a screensaver?
You can download the python code from the description and configure it to run full screen but its not technically a screen saver at the moment - I'm looking into a couple of ways I might be able to turn it into an actual screen saver though
@@HaveaLukeatthis .scr files are just exes so if you compile the python into one it should work as long it goes full screen by default
infinite scrolling mine sweeper, it tries to solve the top-most cells it can, it can't reveal anything about the bottom row of cells, every time a top row is cleared shift everything up and add random bombs, maybe keeping the top 3rd ish solved and slowly scrolling and adjusting the speed of the solver to keep about 2/3rds +/-5% of the cells solved at any given time
Can you make it infinitely scrolling?
Someone should port this to make it a Android live wallpaper or something
Amazing! Are there any situations where two hypotheses are required? like, assuming one tile is maybe cleared reveals some data but not enough, so you need to assume/guess about another tile inside the first assumption?
Did you model this with a Markov Model and/or a Bayes Net?
A game called MINEsweeper, but calls they bombs... I mean, I guess you're technically correct :/
remember me when you get big :)
ADHD nightmare
Now in 3d, pls.
Try generating a NG board.
Why is the very first guess never a bomb? ;-)
How do you only have 1k subscribers
nice