Somewhat OT... Computer playing Minesweeper

[Jeff Shannon]

Terry Reedy wrote:

>In particular, there are multiposition patterns which are only
>deterministic when considered together.  For instance, consider the
>patterns
>
>ooo   oooo
>121  1221
>???  ????
>
>where o is an unmined position (actual number not relevant).  Then ??? and
>???? must be xox (x=mined) and oxxo respectively and one can safely open or
>mark those three or four positions.  
>

With this in mind, I can envision an algorithm which, after exhausting 
all of the "obvious" mined and clear positions (as described by the 
initial algorithm), then proceeds to scan subsets of the grid for 
recognized patterns.  This pattern matching could become very complex -- 
at a minimum, it would need to look at subgrids of varying sizes (3x3, 
3x4 at minimum) being matched against four rotational-variations of each 
pattern.  If it finds a pattern, it can mark/discover the appropriate 
positions and then revert to the initial algorithm to check for newly 
"obvious" decisions.  You will have a hard time coming up with an 
exhaustive list of possible patterns, but even a fairly modest list 
should greatly improve your solvability percentage.

Jeff Shannon
Technician/Programmer
Credit International