I have implemented in Python an algorithm for solving the game 'Minesweeper'. The program works as follows:
Say that the solver clicks a square named 'a'. For sake of example let the number thus revealed equal 2. The neighbours of the square which are as yet unclicked are (again by way of example) named 'b' and 'c'. The program then associates the square with the expression [2, {'b', 'c'}], and strips 'a' from all other expressions. The deduction of which squares are mines and which are not proceeds by pairwise simplification of such expressions under two circumstances.
If the squares in one expression are a subset of the squares of the other expression:
[2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}]If all the squares in one expression are established to be mines:
[2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}]
Then, for some expression X, if X[0] == 0, we are free to click all squares named in X[1], and if X[0] == len(X[1]), then we can flag them.
I am, however, struggling to identify which pairs of expressions to attempt to simplify. My current approach is to maintain a stack of squares; whenever a square is clicked, or has its expression successfully simplified, it is added to the stack (if it is not already there). When a square is popped from the stack, simplification is attempted between its expression (X), and any other expressions Y such that X[1] & Y[1] != set(). The algorithm terminates when the stack is depleted. Currently however, though this works quite well, it is not capable of correctly solving all unambiguous configurations, and how well it performs on a given board changes significantly if I replace the stack with a queue, or use some algorithm to determine which square to pop!
I would be very much appreciative for any examples of precedent to my approach, or avenues of potential exploration.
