Somewhat OT... Computer playing Minesweeper

Paul Rubin http
Tue Jul 13 23:22:16 CEST 2004

Heiko Wundram <heikowu at> writes:
> I've let this little program run to check the average number of "solvable" 
> games on an 8x8 field, with 10 mines (this is the easy setting of any 
> Minesweeper clone), and I get a number in the range 55-65%.
> Now, if I let KMines get the solvability rate for a field of this size, it 
> spits out a number of 80%...
> So, I guess, either my algorithm is wrong (or suboptimal), or KMines
> algorithm for solving a field is wrong (taking information into
> account which it may not).
> If anybody here knows more about game-theory than I do, I'd be happy
> if he/she could enlighten me...

Determining whether a given minefield is solvable is in general
NP-hard.  So, there are only better and worse approximations.  I found
a Windows minesweeper solver written in Turbo Pascal a while back and
its solution rate at the expert setting was maybe 1/3.  I don't remember
trying it on the beginner setting.

More information about the Python-list mailing list