Find no of possible formations of explosive mines in a 2D matrix where some cells contain info about even/odd mines are adjacent to them

Question

I am trying to make game involving 2D grid where given some hints a player can avoid cells containing explosive mines. I have come upon a particular scenario where given certain hints, i want to know how many formations of mines are possible.

Let there be a 2D matrix. Each cell may be empty or may contain explosive mine. Each cell has some information. If the value of cell is

• 'E': it means even no of cells adjacent to this cell contain mines.
• 'O': it means odd no of cells adjacent to this cell contain mines.
• 'N': it means absence of values of 'E' or 'O'. It tells nothing about its surrounding as well as itself.

Example for 2d matrix given below:
N N
N N
no of all possible formations are 16.
O N
O N
O E
no of all possible formations are 4.

These are my hand calculated values. I am stuck at making an efficient program for calculating no of all possible formations where grid dimension

Answer 1

Cute problem. Sounds like a programming contest style problem. Hint:

Represent this as a linear algebra problem over GF(2) (i.e., with arithmetic modulo 2), then use Gaussian elimination.

Hint:

If we are given a matrix A and a vector b, could you count the number of solutions to the equation $Ax=b$? How?

Answer 2

Turns out this shouldn't be too bad to brute-force, at least if your board isn't too large.

You can define your set of bombs where each cell can be Present, Not Present, or Unexplored, where Unexplored means that there may or may not be a bomb there. You can then write a method which takes your board and this set of bombs, and determines whether the board is definitely invalid, or may be valid depending on the actual value of any Unexplored cells.

Then you start walking the board. Set the first cell to Present, and see if that results in a board which could be valid (or is definitely invalid). If it could be valid, set recurse onto the next cell. Then set the first cell to NotPresent and see if that could be valid, and if it is recurse onto the next cell.

This pruning of boards which have a small area which is invalid should significantly cut down the search space compared to a full-blown brute force.

When you're checking whether the board could be valid, you can optimize by only checking the cells in a square around the cell you changed, as those are the only ones that could be affected.

This isn't full-on dynamic programming, and would probably benefit from some memoization: if there's a combination of bombs in the bottom right which is invalid (the bottom right being the last area explored), it will keep trying them again and again with different (valid) combinations of bombs elsewhere.

This will also get bogged down if your board has a big open area, as there will be a large number of combinations and this will meticulously explore each one.

I threw together some C# to illustrate my idea. It's not neat or particularly clear (and for that I apologize - I ran out of time to tidy it up), but it finds the 4 solutions for your second example.

This is written using recursion, so will blow the stack with larger boards. Rewrite it to be iterative.

class Program
{
    static void Main(string[] args)
    {
        var board = new Board(new CellState[,]
        {
            { CellState.Odd, CellState.None },
            { CellState.Odd, CellState.None },
            { CellState.Odd, CellState.Even }
        });

        var bombs = new BombState[board.Height, board.Width];
        int numSolutions = 0;

        Explore(board, bombs, 0, 0, ref numSolutions);
    }

    private static void Explore(Board board, BombState[,] bombs, int x, int y, ref int numSolutions)
    {
        int nextX = x + 1;
        int nextY = y;
        if (nextX >= board.Width)
        {
            nextX = 0;
            nextY++;
        }

        bombs[y, x] = BombState.Present;
        if (board.DetermineValidity(bombs, x, y))
        {
            if (nextY >= board.Height)
                numSolutions++;
            else
                Explore(board, bombs, nextX, nextY, ref numSolutions);
        }

        bombs[y, x] = BombState.NotPresent;
        if (board.DetermineValidity(bombs, x, y))
        {
            if (nextY >= board.Height)
                numSolutions++;
            else
                Explore(board, bombs, nextX, nextY, ref numSolutions);
        }

        bombs[y, x] = BombState.Unexplored;
    }
}

public enum CellState
{
    Odd,
    Even,
    None,
}

public enum BombState
{
    Unexplored,
    Present,
    NotPresent,
}

public class Board
{
    private readonly CellState[,] cells;
    public int Width { get; }
    public int Height { get; }

    public Board(CellState[,] cells)
    {
        this.cells = cells;
        this.Width = cells.GetLength(1);
        this.Height = cells.GetLength(0);
    }

    // Takes a board of bombs, and the position of a bomb to inspect, and determines
    // whether that bomb position is definitely valid, or is unknown/invalid
    public bool DetermineValidity(BombState[,] bombs, int changedX, int changedY)
    {
        // We only need to consider the cells in a square around the cell which was just changed

        for (int x = Math.Max(0, changedX - 1); x < Math.Min(this.Width, changedX + 1); x++)
        {
            for (int y = Math.Max(0, changedY - 1); y < Math.Min(this.Height, changedY + 1); y++)
            {
                var cellState = this.cells[y, x];

                // If this is a "None", there's nothing to check
                if (cellState == CellState.None)
                    continue;

                // For each cell, check its neighbours... If they're all specified, get the number of boms
                int numBombs = 0;
                bool areAllSpecified = true;

                if (x > 0)
                    InspectNeighbour(bombs[y, x - 1], ref numBombs, ref areAllSpecified);
                if (areAllSpecified && x < this.Width - 1)
                    InspectNeighbour(bombs[y, x + 1], ref numBombs, ref areAllSpecified);
                if (areAllSpecified && y > 0)
                    InspectNeighbour(bombs[y - 1, x], ref numBombs, ref areAllSpecified);
                if (areAllSpecified && y < this.Height - 1)
                    InspectNeighbour(bombs[y + 1, x], ref numBombs, ref areAllSpecified);

                if (areAllSpecified && ((numBombs % 2) == 0) != (cellState == CellState.Even))
                    return false;
            }
        }

        return true;
    }


    private static void InspectNeighbour(BombState state, ref int numBombs, ref bool areAllSpecified)
    {
        switch (state)
        {
            case BombState.NotPresent:
                break;
            case BombState.Present:
                numBombs++;
                break;
            case BombState.Unexplored:
                areAllSpecified = false;
                break;
        }
    }
}

Answer 3

Basically you have to solve a system of equations over Z/2. It's actually very similar to playing a game called Lights Out. Let's take this board for instance.

O N
O N
O E

Let's make variables for the different board positions.

x11 x12
x21 x22
x31 x32

We get equations like so. Each O turns into an equation like (sum of neighbor variables) = 1 (mod 2). Each E turns into an equation like (sum of neighbor variables) = 0 (mod 2).

x12 + x21       = 1 (mod 2)
x11 + x22 + x31 = 1 (mod 2)
      x21 + x32 = 1 (mod 2)        x22 + x31 = 0 (mod 2)

Use Gaussian elimination over Z/2 to put these equations in row echelon form. Z/2 is fun because there's no difference between adding and subtracting. In a nutshell, we repeatedly pick a variable that appears in some equation that remains, add that equation to every other equation that contains that variable, and set that equation aside. I'll demonstrate.

x12 + x21 = 1
x11 + x22 + x31 = 1
x21 + x32 = 1
x22 + x31 = 0
----

To make things interesting, let's choose x21 in x12 + x21 = 1.

x11 + x22 + x31 = 1
(x21 + x32) + (x12 + x21) = (1 + 1) ==> x12 + x32 = 0
x22 + x31 = 0
----
x12 + x21 = 1

Note that x21 + x21 and 1 + 1 both simplify to 0, since we're working mod 2. Let's now choose x22 in x11 + x22 + x31 = 1.

x12 + x32 = 0
(x22 + x31) + (x11 + x22 + x31) = (0 + 1) ==> x11 = 1
----
x12 + x21 = 1
x11 + x22 + x31 = 1

All of the variables in the equations we haven't set aside are distinct, so the next two steps are boring.

----
x12 + x21 = 1
x11 + x22 + x31 = 1
x12 + x32 = 0
x11 = 1

We have 4 independent equations, so the answer is 2^(3*2 - 4) = 4 solutions (in general, 2^(board squares - equations)). Sort of a boring outcome, but it is what it is.

Two interesting things can happen when we're reducing equations. Let's consider the following board.

E E
E E

We get the following equations.

x12 + x21 = 1        x11 + x22 = 1
x11 + x22 = 1        x12 + x21 = 1

Now, let's reduce.

x12 + x21 = 1
x11 + x22 = 1
x11 + x22 = 1
x12 + x21 = 1
----

x11 + x22 = 1
x11 + x22 = 1
(x12 + x21) + (x12 + x21) = (1 + 1) ==> 0 = 0
----
x12 + x21 = 1

(x11 + x22) + (x11 + x22) = (1 + 1) ==> 0 = 0
0 = 0
----
x12 + x21 = 1
x11 + x22 = 1

We end up with two degenerate equations 0 = 0. This means we had redundant information given, and they don't count as independent equations. The answer here is 2^(2*2 - 2) = 4 again.

The other thing that can happen is that we get an equation 0 = 1. In this case, there are no solutions consistent with the hints.