Now that's what I call a well-spent long weekend

[simont]

Over the past three days I've been putting together a Minesweeper clone to go in my puzzle collection. As of now, it seems to be pretty much playable.

To write yet another Minesweeper clone in this day and age, you have to have some pretty impressive added value to avoid accusations of gratuitous reinvention of the wheel. My added value is that I use sophisticated grid construction to ensure that all puzzles generated can be solved without needing to guess. No more getting to the last four squares and finding you have no choice but to take a 50-50 gamble.

What I hadn't realised before actually writing this and playing with it is that it permits much denser grids. The Windows ‘Expert’ level has a mine density of a bit over 1 in 5, and it's already sailing close to the limit: I've generally found it quite rare to get to the end of an Expert grid without having to take a nasty risk. If you tried getting any denser with random generation, you'd just have a vanishingly small chance of actually completing anything. But with my intelligent generation, you can raise the mine density by nearly another factor of two: I've successfully played games on the same size of grid (30x16) with 190 mines. At that density there are barely any blank areas to work round the edges of; almost the whole grid is taken up by fiddly work involving squares marked between 3 and 6, and there's no let-up. And it's fun.

Now I just need to find a way to go to sleep tonight without dreaming about Minesweeper…

Comments

[deliberateblank.livejournal.com]

Of course you're very first move always stands a chance of going boom. Unless you delay generation of the grid until after you know which 1 square has to be blank...

[simont]

Windows Minesweeper has always done this as far as I know; I was very surprised to find that other ones (Gnomine) didn't, and that instakills were possible. (I'm also constantly surprised that so many people have never noticed that it gives you the first click free!) Quick demonstration: set Windows Minesweeper to 9x9 with 64 mines. If first-click kills were possible you would expect to suffer one over half the time.

So yes; I delay grid generation until the first click, and I arrange that (a) that square is free of mines, (b) none of its immediate neighbours have any mines in either so that it opens up a whole area, and (c) starting from that area it is possible to solve the whole of the rest of the grid without needing to guess.

[feanelwa.livejournal.com]

It didn't in 95.

[simont]

Aah, that'd explain it. I'm not sure why I assumed that Windows Minesweeper wouldn't have needed much further development after it was written; after all, I can never leave things alone once I've written them so I've no idea why I assumed Microsoft could :-)

[damerell.livejournal.com]

Are you sure? The first click is free in Windows 3's minesweeper.

[feanelwa.livejournal.com]

I distinctly remember getting boomed on the first click several times on one of my father's computers. I can't quite remember if it was 95 or 98 that one had, but it was ninety-something.

[atreic.livejournal.com]

Does that mean you get given the first square too? Or is there still that really annoying first guess in the system?

[simont]

(See my reply to deliberateblank above.)

[fluffymormegil.livejournal.com]

.EXE! .EXE! .EXE!

[simont]

http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ as of now.

[deliberateblank.livejournal.com]

.SCR! .SCR! .SCR!

[teleute.livejournal.com]

I ust own this game!! I love minesweeper, and this sounds considerably better :-)

[teleute.livejournal.com]

I just played the one you linked to on your website. Is it the most recent version? I was getting killed on the first click, and found a couple of places were I did get down to a 2x2 grid where I had to guess. Also, if you could make the cleared squares and the uncleared squares different colours, I at least, would be very appreciative ;-)

[simont]

That sounds odd. First-click kills should never happen. If it happens again, can you note down the game ID given by the Game -> Specific menu item, and also the one given by the Game -> Random Seed menu item? Same if you have to guess.

[simont]

Oh, and it might also help to report the version number from the About box. Particularly if you want me to tell you if it's the latest version :-)

[simont]

The version now up on the website (r5879 or better) should use slightly different background colours for covered and uncovered squares. I found it looked really weird if I made them any more different, but I hope it's helpful anyway.

Have you had any more trouble with instakills or guessing?

[teleute.livejournal.com]

I've just been playing r5936, which seems not to be having problems with instakills. I don't know whether it's just my computer, but I'm really not seeing any difference in the colours of covered and uncovered tiles. Looking at the M$ minesweeper, I notice that the covered and uncovered tiles are uniformly a medium grey, but that the uncovered tiles are framed more strongly than in your version. Possibly it's this difference which is confusing me.

[cjwatson]

Ooh, you bastard. ETIMEDISAPPEARINGDOWNPLUGHOLE.

Although, if I may report a bug via LJ, it throws lots of compile warnings on Debian powerpc; it looks like mostly the plain char-ness of grid, since adding -fsigned-char. You should be able to reproduce them elsewhere using -funsigned-char.

mines.c: In function `known_squares':
mines.c:581: warning: comparison is always false due to limited range of data type
mines.c:587: warning: comparison is always true due to limited range of data type
[...]

[simont]

Chris Emerson was an hour ahead of you and had a patch. Try r5871 or better.

[timeplease.livejournal.com]

(Excellent implementation, by the way. But...)

There's an annoying UI difference between your version and the Windows version. I'm in the habit of pressing both mouse buttons while pointing at a number to clear the surrounding squares if there are already the appropriate number of mines marked; this is required by the original Windows implementation, a left-click on its own does nothing. In the original, if the number of marked mines is incorrect it 'presses' the surrounding squares down. In yours, this happens when the left mouse button is pressed, but they pop up again when the right button is pressed; the observed behaviour therefore depends on whether the intended simultaneous button press was actually left-right or right-left.

[simont]

It was a deliberate choice to require only the left button to do this: on my preferred type of trackball left-and-right-clicking is annoyingly unwieldy, and my Minesweeper solution time has dropped by about 30% just from this one UI change. (The trackballs are fantastic for most things, but the traditional Minesweeper UI seems to be the one common thing they're not good at :-)

Mouse handling is done centrally in my puzzle framework, and as you observe the pressing down of one mouse button fabricates a button-up event for any previously pressed one. This is usually a good thing, though I concede that it isn't ideal for Mines. Feel free to submit a patch :-) The relevant function is midend_process_key() in midend.c. All it'd take would be a bit of configurability in that function and a set of flag bits provided by the individual game.

[simont]

Actually, that turned out to be quite easy to fix. r5888 should be fine.

[timeplease.livejournal.com]

Excellent, that appears to do the trick.

Next bug report: click in the window, outside the puzzle area (under Linux):

mines: mines.c:1295: mineopen: Assertion `x >= 0 && x < ctx->w && y >= 0 && y < ctx->h' failed.

(More generally, clicking outside the puzzle results in strange "you've lost" states.)

[naath.livejournal.com]

When I played the big grid it had one square totally surrounded by mines (a corner as it happens) - one is sovable, two is not (unless both are the same). Just to check that it won't be unsolvable in that way.

Also the 'solvability' algorithm appears to have eliminated the need for several sorts of thinking about the correct answer though I may be wrong - it seems too easy.

[simont]

Indeed, if there are any completely unreachable squares then they should always be all the same, and their state can be deduced from the overall mines-remaining count. The solver actually does this deduction while laying out the grid, so I'm reasonably confident that it's possible.

It is true that verifying the grids with a solver restricts the required reasoning during play to only those things the solver was capable of. This is unfortunate, but it's that or have your perfectly good Expert game be destroyed on the final click by an unavoidable 50-50 guess; and there are plenty of implementations which provide the latter, so I thought I'd try something different. If you really want Mines to go back to being an ordinary Minesweeper you can always disable the intelligent generation.

[deliberateblank.livejournal.com]

Specific: 30x16:16,11,mf6d0d8c9cacdcc9bc9f7d860e2e3e6f0e6e6f9e8aba8ecafeefbb0f152a258191a499df69fdb63e06a69d465a66628696a727c4d2f6b717139f06e25
Seed: 30x16n99#683298348361933

1) Keyboard shortcuts don't appear to work. Specifically, when choosing the Specific... and Random Seed... options it would be nice to be able to just Ctrl-A Ctrl-C to copy the data, but that just beeps. Undo and Redo (which I noticed under Solo) would also be usefully bound to Ctrl-Z and Ctrl-Y. (I suppose even better would be to have a menu option to copy a complete game description - including code revision level I guess - to the clipboard for reporting poiposes.)

2) Is this intended to be solvable purely by logical inference? I'm down to the bottom left corner having started in the middle somewhere. Unless I'm missing something there are several choices from this position which don't result in a contradiction:

[ptc24.livejournal.com]

That 4 in the middle of the shot - it's adjacent to three mines already (* in the diagram below), and there must be one more in the two uncovered squares (# in the diagram below). Either position would satisfy the 2 below it, so the uncovered square south-west of the 2 (X in the diagram below) can be safely uncovered.


**1
#42
#2*
X22


[deliberateblank.livejournal.com]

Ah yes, so you can.

[simont]

Specifically, when choosing the Specific... and Random Seed... options it would be nice to be able to just Ctrl-A Ctrl-C to copy the data, but that just beeps.

Well, you're the Windows programming expert, you tell me how to fix it :-) I just instantiated a standard edit box and expected it to do the right thing. Is there some voodoo I have to apply to get standard keyboard shortcuts to start working? Or do I actually have to go through the sheer tedium of implementing them all myself?

Undo and Redo (which I noticed under Solo) would also be usefully bound to Ctrl-Z and Ctrl-Y.

Undo should already be on ^Z. I'd never noticed ^Y as a shortcut for redo before someone else mentioned it to me last week, but it's certainly not being used for anything else right now so I could perfectly well add it.

[(Anonymous)]

Re keyboard shortcuts: Tab, Ctrl-C works for me.

[sevenstring.livejournal.com]

Nice one. Winning UI, and solvability helps a lot.

Interestingly, I have a slight advantage over the built-in solver: I know that the grid is solvable and can use that to solve it. ;-)

[gerald_duck]

Oooh, fun! Good one; thanks.

Now, obviously, I'm a demon minesweeper player, and I never screw up, so this niggle is of absolutely no importance to me. But just supposing I were ever to make a mistake…

It would be nice if, when you stepped on a mine, some indication were given of where you went wrong. Ideally, at that stage, the following would be mutually distinguishable:

1. Empty areas successfully uncovered
   
2. Mines correctly discerned
   
3. Places you said contained a mine, which didn't
   
4. Mines you didn't find
   
5. Empty areas you didn't uncover
   
6. The mine you trod on

At the moment, 2 and 3 look identical, as do 4 and 5.

[simont]

It sounds as if you're describing the standard behaviour of Windows Minesweeper. Am I correct?

The thing about my Mines is, it has an undo feature, because that comes as standard when any game is implemented as part of my puzzle collection. I nearly arranged to make the undo feature optional (disabled or enabled by choice of each individual game) on the basis that it didn't seem to make much sense for Mines, but at the last minute I was persuaded to turn Undo into a feature rather than a bug.

Hence, when you step on a mine, you only get told about the one mine you stepped on, which means it hasn't spoiled the rest of the grid for you - so you can press Undo and carry on playing, and the game will keep track of how many times you died. I think this is a much better response to death than to declare the game completely over.

(In particular, I might have considered that mechanism in itself to be an adequate solution to the problem of 50-50 guess sections if I'd thought of it first. I'm glad I came up with the intelligent generation algorithm first instead.)

drswirly suggested at one point that perhaps there could be a limit on the number of times you were permitted to undo your own death - a lives counter, in fact - and after that limit was exhausted the full grid would be revealed à la Windows Minesweeper. Then I could set the limit to infinity (preserving the current Mines behaviour) and you could set it to 1 (reverting to Windows Minesweeper) and other people could set it to somewhere in between if they liked. However, that requires a general configurability interface for the puzzle suite as a whole, which I'm still resisting because it would be so much work...

If you do decide you want to see where the mines really were, there's always the "Solve" option on the game menu. It won't overlay that on your existing position, but you can Undo/Redo to switch back and forth between the two views and compare them.

[gerald_duck]

[Pops to fire up Windows Minesweeper for the first time in months…]

Yes, I'm describing Windows Minesweeper. And probably Minesweeper more generally.

If you don't want configurability, maybe "solve" could show a comparison between where you'd got to before giving up, and the full situation, in the way other Minesweepers do when you die. Then people could choose to see that comparison whenever seemed appropriate — at first failure, or never, or somewhere in between as the mood took them.


Incidentally, as a minor user interface consistency issue, I regard the pencil marks in Solo, locking in Net and flagging in Mines as essentially the same activity: the user making notes to themself while solving the puzzle. It feels just subtly wrong to me that this is achieved using the right-hand mouse button in Solo and Mines, but the middle mouse button in Net.