mines.py is a Minesweeper (and picma squared) solver I wrote for fun. It is
geometry-agnostic, so if you want it to solve minesweeper on a hexagonal grid,
the surface of a cube, or a 4-dimensional grid, it's got you covered (although
you'll have to do a little bit of work to translate the data into the right
form). The solver can be used to verify that at least one solution to a
minesweeper configuration exists, while determining the identity of any unknown
squares that it can.

It can also calculate the probablity of each square containing a mine, and the
number of possible arrangements, for each square about which it has some
information. (In a normal game of minesweeper, the total number of mines is
known, meaning the solver has some information about all the squares. If no
information is available for some squares, those squares have a 50/50 chance
of containing a mine, but the solver will not bother to report this, or account
for them when calculating the total number of arrangements. If this is really
needed, it's trivial to add.)

The solver can also solve monochrome puzzles from Picma Squared, a related game:
http://kaetheryan-chronicles.com/picma2


Command-line operation
----------------------

To solve a minesweeper board, run:
$ python mines.py mines <width> <height> <total mines>

Then enter the current board state.

For example:
$ python mines.py mines 5 5 10
02m--
02m--
12---
-----
-----

A "-" indicates that no information is known about a space.
An "m" indicates that the space is a mine.
A digit indicates that the space is not a mine, and it defines the number of
mines in the space surrounding that space.

The previous example results in the following output:

001--
001--
000--
--0--
-----
Information(spaces=frozenset([(3, 2), (3, 1), (3, 3), (3, 0), (3, 4), (4, 4), (1, 4), (4, 3), (0, 4), (4, 2), (4, 1), (2, 4), (4, 0)]), count=7)
Information(spaces=frozenset([(0, 3), (1, 3)]), count=1)
total possible arrangements: 3432
(0, 3) 0.5
(1, 3) 0.5
(0, 4) 0.538461538462
(1, 4) 0.538461538462
(2, 4) 0.538461538462
(3, 0) 0.538461538462
(3, 1) 0.538461538462
(3, 2) 0.538461538462
(3, 3) 0.538461538462
(3, 4) 0.538461538462
(4, 0) 0.538461538462
(4, 1) 0.538461538462
(4, 2) 0.538461538462
(4, 3) 0.538461538462
(4, 4) 0.538461538462

The first part of the output is a map showing which squares have a known value
and the value of each known square. The squares marked with a 1 are mines, and
the squares marked with a 0 are not mines. It cannot be determined whether the
squares marked with a - are mines with the information given.

The second part of the output contains the information that is known about those
squares whose identity cannot be determined, in a simplified form. The first
Information() line shows that there are 7 mines among the squares in the bottom
row and rightmost two columns. The other line shows that there are is 1 mine in
the two remaining unknown squares. I'm aware that this isn't very readable, and
I included it mostly for debugging purposes.

This is followed by the number of total arrangements of mines that satisfy the
given constraints and the probability of each unknown square being a mine,
sorted from least to greatest.

If a given configuration is unsolveable, the output is much simpler:

$ python mines.py mines 5 5 10
02m--
02m--
11---
-----
-----
This configuration has no solutions.

The program can similarly be used to solve picma squared puzzles, with the
following command line:
$ python mines.py picma <width> <height>

Because picma squared does not include a way to mark mines, the m character
cannot be used there.


Programming interface
---------------------

To use the solver in python, a program should create a Solver object, add all of
the currently known information, call the solve method, and optionally call the
get_probabilities method.

The Solver constructor takes a single argument that defines the set of valid
space identifiers. This will normally be a tuple coordinate pair (x,y), but
it could be any immutable, hashable object with an equality operation consistent
with its hash function. What makes sense for your program will depend on the
geometry it is using.

For a simple 2D grid, I create it this way:

spaces = set((x,y) for x in range(width) for y in range(height))
solver = Solver(spaces)

You can add information to the solver in two ways. If you know the identity of
a space, you can use the add_known_value function:

solver.add_known_value((x, y), value)

Again, (x,y) is your space identifier and doesn't necessarily have to be a
tuple in the form (x,y). Value must be either 0 (for no mine) or 1 (for a mine).

If you know how many mines are in a set of spaces (such as the spaces
surrounding a particular square), you must create an Information object
expressing that knowledge, then add that object to the solver.

The Information constructor takes two arguments: a frozen set of space
identifers and the total number of mines in that set of spaces. The first
argument MUST be a frozen set, and it MUST be a subset of the space identifiers
that were originally passed to the Solver constructor.

The following code informs the solver that there are 36 total mines on the
board:

info = Information(frozenset(spaces), 36)
solver.add_information(info)

Once you have added all the information you wish to use to a solver, call its
solve method:

solver.solve()

If there are no possible solutions for the information you've given, the solve
method raises an UnsolveableException. After this happens, the state of the
solver is invalid, and it can no longer be used.

As long as there is at least one possible solution, solve will return None.

To extract information from the solver, use the solved_spaces and information
attributes. solver.solved_spaces is a dictionary mapping space identifiers to
values (0 for no mine, 1 for a mine). solver.information is a set of Information
objects that contain the rest of the solver's knowledge. This will usually
not be the same set of Information objects that was given to the solver
originally.

After solver.solve has returned, you may use the get_probabilities method to
calcualte the total number of possible arrangements and the probability of each
unknown space being a mine. It is used like so:

solver.solve()
probabilities, total = solver.get_probabilities()

After this code executes, probabilities is a dictionary mapping space
identifiers to the total number of possible arrangements in which that space
is a mine. Only space identifiers whose identities are not known and about which
some information is known will be included in the probabilities dictionary. The
other value, total, is the total number of possible arrangements. To determine
the probability of a space being a mine, divide its value in the probabilities
dictionary by total.

Once solve() has returned, it is perfectly valid to add more information and
call solve (and, optionally, get_probabilities) again. This is faster than
creating a new solver.

There is no reliable way to remove information once it has been added because
that information may have already been used to draw some conclusions. If you
need to do this, you should make a copy of the solver using the copy method,
and add the new information to the copy. 

As for the other methods and attributes of Solver, I might change them without
warning. Use them at your own risk.


Support
-------

For the latest and greatest version go to: https://github.com/madewokherd/mines

Email me (madewokherd) through github if you have questions, comments, patches,
etc.

And if you do something interesting with this code, please drop me a line.