Re: gnomines possible improvement

["Richard Hoelscher" <rah rahga com>]

Callum McKenzie said:
> The only major reason I can see for not including the patch might be if it
> made the game too easy (I wouldn't have an option, removing pure guessing
> is desirable).

As far as desirability goes, I don't know if removing the guessing is a
good thing. I think a bit of the fun comes from the fact that Minesweeper
is NP-Complete. In short, it can be really hard to determine if a square
is safe to click or if you just need to guess. To illustrate this, just
use the solver from games-list December 2004 and run it on 'hard'. While
most results will be returned in a second or two, others take 30 seconds,
a minute... One of them took 11 minutes on my laptop.

Using the solver, I ran tests to see how often guessing would be needed to
solve a puzzle. After the cascade click, about 9 out of 10 'easy' games
were solvable without guessing , compared to only 1 out of 25 'hard'
games. (I only used small samples in testing... there are about 151
billion 'Easy' minefields.)

> Do you have an algorithm in mind? I recall considring this once and
> finding it quite tricky and I have the vague memory I could concoct a
> situation where rearrangement wouldn't solve the problem. Having said
> that, even something that only minimised the bad positions will be good.

Perhaps we should just ensure that the first click is not adjacent to any
mines, reducing the number of dud games quite a bit... nobody counts those
anyway. :)

-Richard Hoelscher
http://rahga.com/svg/