http://www.perlmonks.org?node_id=688017


in reply to App::SweeperBot - Perl plays minesweeper, automatically.

pjf,
Very cool. I have often thought about writing a minesweeper solver since it is a tough problem (NP Complete). I just never got around to it. I did a 20 second scan over your source to see what strategies you used and didn't really see any other than:

I haven't read any minesweeper strategy guides, but I personally have more complex rules than above. For instance

??????? 121 Becomes ? B B ? 121 Because in order for the 2 to hold it would have to be one of the foll +owing ??BB??? 121 or ???BB?? 121 or ??B?B?? 121 And only the last one doesn't violate the rules of the "1" block.

Another strategy I use towards the end of the game when there are not that many unknown bombs remaining. For instance, you have X squares that have unsatisfied constraints, Y unflagged bombs, and Z unclicked/unflagged squares. If the total number of unsatisfied constraints of X squares accounts for all of the Y unflagged bombs then all of the Z unclicked/unflagged squares that are not adjacent to any of the X squares are not bombs.

My final strategy is when I have to guess. Rather than picking any square at random, I use a relationship to the number of unflagged/unclicked squares in an "area" to the number of bombs remaining. I choose areas where there is less of a chance of choosing a bomb. Of course, this strategy is probably not mathematically sound.

Have you considered incorporating any of these (or more advanced strategies)? I would be happy to contribute since that would be easier than developing my own code.

Cheers - L~R