Minesweeper

[Jedo the Jedi]

Alright, so I've been on this minesweeper kick recently and I started thinking. Does anyone know how the program works? Like, how does it generate a different puzzle every time? And how does it determine the placement of the mines?

After I had beaten the game quite a few times and improved my scores, (Currently 10 on beginner, 65 on intermediate, and 183 on expert. Yes, I'm a little rusty.) this thought came to mind: What is the maximum number of mines that can be in the puzzle without making it total blind chance that you would win? In other words, how many mines can you have where it is still possible to use strategy to solve the puzzle?

Just some thoughts I had. I don't know if the questions can be answered, but if they can, I'd like to know the answers.

[Courk]

Isn't always a bit of blind chance? You're not given anything to start with and have to clear a space in order to see any numbers. Should that space be a bomb, you've already lost. Obviously, the fewer mines there are, the better your chances of getting to actually play. To me it seems that half the total number of squares is the most bombs you can have without it being pure blind luck. Anything above that number, the odds are that you will probably hit a bomb.

[Courk]

Oh, and BTW, 4 seconds.

[Dread Pirate Westley]

If you have at least 6 mines on the board, it is possible to arrange them in such a way that they force a guess: a 4x4 square with mines at each corner and 2's on each edge; there are two mines in the middle 4 squares, diagonal from each other, but it's impossible to know which two. I have no idea how concentrated you'd need to make the mines to force a guessing situation, however.

Courk, I just ran 20 trials with 667 mines in a 24x30 grid (all max it would allow). 92.6% of all squares are mines, and in my first 20 games I did not once lose until my second click at the earliest (once I got as high as 4). Witha 7.4% chance of randomly selecting a non-mine square with each pick, the odds of making such a run are 1 in 4.6*10^22 (against). I'd say it is a safe guess that you're not ever going to lose on your first click.

[Courk]

Jiminy, I think you're right. It must... cheat somehow. But in your favor. It's been a while since I've played. Losing on your second click still makes for a pretty crappy game.

[Persona]

The degenerate answer is, of course, is that if every square were mined, you'd win just by right-clicking the entire board.

I can't think of the typical uncertainty patterns right now, but I seem to remember that it only takes two or three mines to get into a position where one can't be placed definitively.

[Courk]

You wouldn't even need to mark the whole board. Once you clear all non-bomb squares, you win. Marking bombs is just for when you're figuring it out.

[Antrax]

You're never going to lose on your first click - the game generates the puzzle after you click a square, forcing that square to be empty.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[kevinatilusa]

Here's an unsolvable position with 3 mines (the two X's and one of the ?'s), assuming it occurs in the lower left corner of the board

[Leptonn]

The older versions of minesweeper generated the board before the first click. I'm referring to the Win3.1 era.

It seems to me that it is also possible for a board to be randomly generated which would located all the bombs after the first click. Perhaps if all the bombs were on the outer walls. I'm sure we'd know about this "bug" if it existed, so there's evidence for at least a little bit of intelligence in the board setup.

[GH]

It would be easy for the game to generate the board, keeping track of the locations of all the bombs and one empty square. Then, when you make your first click, if there's a bomb there, it just moves it to the one empty spot.

[L'lanmal]

Yeah, in the old versions of minesweeper it would generate the board first. If you clicked a mine on the first click, it would move the mine to the first available open location.

So one particular corner would be mined much more often than the others. Unless you picked it to begin with, in which case you were more likely to have a mine on the next square over.

The thing I can't remember is which corner it was. Upper-left? If you have a moderate number of mines on the board, it's not too hard to notice after a few games if you are looking for it.

They also had a maximum number of mines you could have on the board (which was substantually less than the total number of squares). So you couldn't put in 99 mines on a 10x10 board, and guarantee winning in one click. You could however place 10 mines on a very large board, and have a good shot of winning after one click.

[Lucky Wizard]

According to http://www.maa.org/mathland/mathtrek_5_3_99.html , it was the upper-left corner.

And when I first read Jedo's post, I interpreted it as being the problem in this thread: http://www.greylabyrinth.com/discussion/viewtopic.php?t=3222 . But now I see what he means. (BTW, reading a few other VSP threads from around that time while looking for this got me nostalgic!)

Jedo, you're a bit faster than me; my best times are 18, 62, and 232.

[Jedo the Jedi]

It's nice to know that I'm faster than someone at this game. Of course, it's all I've been playing recently and I've only beaten the expert category about three times. *goes to improve his times*

[Jedo the Jedi]

I've been playing this as I pack for my trip to Brazil (Yes, I do need frequent breaks.) and I have decided that the smiley at the top makes me think of Courk. I don't know why (could be that smiley write-up she did a while back) but it does. I think this is a sign that I need to crawl in bed.

[MatthewV]

I believe the windows minesweeper also forces you to click atleast twice. Just make the board as large as possible and put the lowest number of mines in it.

The old Mac minesweeper had the goal of connecting the upper left corner with the lower right corner. You didn't have to solve the whole board.

[Samadhi]

[Chuck]

My records are:
61
999
Never won

[Lepton]

I was planning to do this myself, but haven't yet found the time.

The sourceforge has open-source versions of several Linux-based minesweeper imitations. It shouldn't be too hard to look inside the code and figure out how it ticks.

[CrystyB]

[Neo]

[Samadhi]

Screenshot?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[warpdragon]

Firefox Extension
http://clav.mozdev.org/#minesweeper

Lets you have hex tiles and the option to have no mines on the borders.

[austinap]

I havn't proved it, but I think the most mines you can have on the board and have it garanteed to be a no-guess game is 1, and even in this case the board has to be at least a certain size. If you have two mines arranged in such a way that your first click is right between them, then you have 8 choices and only two mines. You chances are good, but I think this still counts as a guessing situation because you'll lose 25% of the time it comes up.