Only on Ubuntu, in which the first click must be "0". On Windows it could for example be "2" and then you have to guess which of the adjacent 8 cells are the 2 mines...
That's not what's being discussed here; the above comments talk about whether it's guaranteed that the first click is not a mine, not that it's not adjacent to a mine. As far as I'm aware, just about every version guarantees that the first click is not a mine, but many (such as the Windows original) allow the first click to be adjacent to a mine.
There are some variants without luck. For example there was one which guaranteed that you never get a mine when you have to guess, but always get one when you guess in a situation where you can still open another field safely.
You generate the game map once it's known where the player clicked. During generation you take into account that the first clicked cell has to be mine-free. In general, when distributing mines, the algorithm has to take into account already that there must be N mines in the field, so avoid instances where it assigns two mines to the same field twice. You treat the starting field as just another "mine" whose position is hardcoded.
A simple algorithm would be to re-do the map generation until there is no mine collision, but with larger numbers of mines, the collision chance increases, so your runtime will go up superlinearly. A simple but very effective improvement is to keep the positions of the mines up until the collision and then only change the seed for subsequent mines. Then your algorithm should in fact scale much better. You can also use different methods, like assigning indices in a certain way so that invalid states are avoided completely. A bit more complicated but way "cleaner".
There is an even simpler approach: for maps with K total cells there would be always K-1 unclicked cells and a single clicked cell after the first click, so you can generate K-1 cells and insert a "gap" corresponding to the first clicked cell. This works because every unclicked cell has an equal probability to become a mine.
Well you have all the cells in an array so that's easy enough. Pick a cell at random until you find an empty one, which won't take long. There's no regeneration, just moving one mine to an easy to find place.
This is what actually happens in the Windows original (it doesn't look for a random empty square, it tries them in reading order starting from the top left).
I have written one for that years ago in Java. It generates a map according to my first "click" and solves it deterministically. If it reaches a state in which it has to guess, it regenerates the map, and tries again.
It happens so fast behind the scenes that the user isn't aware of it, and it makes sure I won't have to guess anything when I play. Purely skill, no random.
I tried zooming out - Firefox let's you zoom out to 30% - but still couldn't get close to seeing the whole thing. At this zoom level the browser becomes pretty unresponsive anyway...
This reminded me of Tim Urban's article about numbers: [From 1 to 1,000,000](https://waitbutwhy.com/2014/11/from-1-to-1000000.html). In that article he has an image with a million tightly packed dots - that should give you an idea of how big this Minesweeper game is!
Hahahaha apologies for the reddit-like comment but I laughed so hard.. when scrolling (for a while) on the "1 million dots" portion of the page (big portion), after the loooooong image the author writes "Sorry. A million dots is a lot of dots."
I was once in Copernic Science Centre (Warsaw, Poland), and they had some cylinders with tiny plastic spheres (imagine 1-2mm diameter each sphere). One of the cylinders was supposed to have 100k? 1m? spheres (or some similarly crazy number) and only 1 red sphere, and I remember I was rotating that cylinder for a couple of minutes (it is not tightly packed to the spheres can move around) and eventually I saw the red sphere.
Ps: on the URL of the parent.. I could not find the red dot.. I gave up after a couple of minutes. I will though try the following (later tonight). Save the image, take it to Photoshop, pick the "black color", use that to erase all the similarly colored (black) dots, and the red one will remain behind for me to easily spot.
It's blowing my mind to think that all these dots are actual living human beings... and that you'd need over seven thousand of these million-dots images to count all of them.
It took me about 30 seconds to find the red dot, entirely by visual scan. I am awed at the parallel power of our visual system, our "GPU". Doing the task serially would take days if not weeks!
considering that many mine sweeper boards come down to luck (ex: you're left with a 2x2 unopened area where you know 2 of the cells are mines, could be either of the north/south pairs. this would just be that many times over.
One implementation that famously doesn't suffer that problem is in Simon Tatham's puzzle collection (yes, he of putty fame). Available on almost as many platforms as Doom.
Right click to clear cells works for me. Right click, place flags, right click numbers and it clears (but you die if you missed a flag in teh cleared area).
"The first square you open is guaranteed to be safe, and (by default) you are guaranteed to be able to solve the whole grid by deduction rather than guesswork. (Deductions may require you to think about the total number of mines.)"
It would be really cool if the algorithm is able to generate all possible instances that can be solved purely by deduction.
I do wish that it allowed me to pick a higher fraction of mines. I found the pure skill minesweeper a lot more challenging (and therefore satisfying) when I increased the fraction from 20% (30 mines on 10x15) to 33.3% (50 mines).
There's already been MMO minesweeper games which are essentially infinite in all directions, similar to panning in Google maps.
IMO these solve the problem at the start of the game, because there's already an exposed edge you can work from. Someone, somewhere, had to make the first click; but from that point on every other player has a choice to avoid that experience.
You can get something similar by clicking the location flag with the 8 alphanumeric coordinates in the upper right; that provides a full-screen maximally-zoomed-out map. I agree that it would be cool to be able to zoom out further than currently allowed to see more of the fractal map. The current zoomed-out view is something like Dynmap for Minecraft, I'd also be curious to see the equivalent of something more like Chunkbase that can show millions of cells at a time.
That said, I don't think the concept of "the entire map" makes sense. I expect it's functionally infinite, probably capable of scrolling to 2^32 or 2^64 cells, only allocating new regions in the database as people scroll there and start working. On that scale, you probably wouldn't see any activity at all.
According to the landing page "If every cell on the game field was as small as a speck of dust it would take 17 billion years at the speed of light to travel the width of the board." 17 billion light years is 1.608×10^26 metres, while the size of dust specks varies but is roughly around 10^-6 metres. That's a big field.
I wonder if you could represent the game as a collection of "islands" and render them in WebGL. So, initially the entire field is one island drawn as a single sprite with a repeating texture, then you add a "1" and now you split the island into 5 different such islands having the same texture. It's an also interesting problem to know how many such distinct islands you can actually have, I assume the number mostly depends on the number of mines.
57 comments
[ 4.0 ms ] story [ 117 ms ] threadWhether you lose on move 1 or move 2 due to bad luck is not a big difference
A simple algorithm would be to re-do the map generation until there is no mine collision, but with larger numbers of mines, the collision chance increases, so your runtime will go up superlinearly. A simple but very effective improvement is to keep the positions of the mines up until the collision and then only change the seed for subsequent mines. Then your algorithm should in fact scale much better. You can also use different methods, like assigning indices in a certain way so that invalid states are avoided completely. A bit more complicated but way "cleaner".
It happens so fast behind the scenes that the user isn't aware of it, and it makes sure I won't have to guess anything when I play. Purely skill, no random.
I feel like you've forgotten the purpose of a hobby.
Edit: just played it a bit.. nice.. need to keep the balance on stock, unsold inventory, etc..
This reminded me of Tim Urban's article about numbers: [From 1 to 1,000,000](https://waitbutwhy.com/2014/11/from-1-to-1000000.html). In that article he has an image with a million tightly packed dots - that should give you an idea of how big this Minesweeper game is!
I was once in Copernic Science Centre (Warsaw, Poland), and they had some cylinders with tiny plastic spheres (imagine 1-2mm diameter each sphere). One of the cylinders was supposed to have 100k? 1m? spheres (or some similarly crazy number) and only 1 red sphere, and I remember I was rotating that cylinder for a couple of minutes (it is not tightly packed to the spheres can move around) and eventually I saw the red sphere.
Ps: on the URL of the parent.. I could not find the red dot.. I gave up after a couple of minutes. I will though try the following (later tonight). Save the image, take it to Photoshop, pick the "black color", use that to erase all the similarly colored (black) dots, and the red one will remain behind for me to easily spot.
And if so, if you can make the generation efficient (polynomial time).
I should have asked that in the Pure Skill Minesweeper thread [1], but only thought of it more recently.
[1] https://news.ycombinator.com/item?id=24181772
"The first square you open is guaranteed to be safe, and (by default) you are guaranteed to be able to solve the whole grid by deduction rather than guesswork. (Deductions may require you to think about the total number of mines.)"
I don't know about the runtime though.
I do wish that it allowed me to pick a higher fraction of mines. I found the pure skill minesweeper a lot more challenging (and therefore satisfying) when I increased the fraction from 20% (30 mines on 10x15) to 33.3% (50 mines).
IMO these solve the problem at the start of the game, because there's already an exposed edge you can work from. Someone, somewhere, had to make the first click; but from that point on every other player has a choice to avoid that experience.
Here's one such implementation: https://m3o.xyz/
That said, I don't think the concept of "the entire map" makes sense. I expect it's functionally infinite, probably capable of scrolling to 2^32 or 2^64 cells, only allocating new regions in the database as people scroll there and start working. On that scale, you probably wouldn't see any activity at all.
The first Twitch Plays you can play with... your mouse!
We can go up to 10k cells max, but you can sweep mines with friends.
---
[1] https://www.twitch.tv/bzh314
(5 hours later) that user is me.