Не найти возможных образований взрывчатых мин в 2D матрице, где некоторые ячейки содержат информацию о четных / нечетных минах, смежных с ними

Симпатичная проблема. Похоже, проблема стиля конкурса программирования. Подсказка:

Представьте это как задачу линейной алгебры над GF (2) (т.е. с арифметикой по модулю 2), затем используйте исключение Гаусса.

Подсказка:

Если нам дадут матрицу A и вектор b, не могли бы вы подсчитать количество решений уравнения $ Ax = b $ ? Как?

В основном вам нужно решить систему уравнений по Z / 2. На самом деле это очень похоже на игру под названием Lights Out. Давайте возьмем эту доску, например.

O N
O N
O E

Давайте сделаем переменные для разных позиций доски.

x11 x12
x21 x22
x31 x32

Мы получаем уравнения, как это. Каждый O превращается в уравнение, подобное (sum of neighbor variables) = 1 (mod 2). Каждый E превращается в уравнение, подобное (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)

Используйте исключение Гаусса над Z / 2, чтобы поместить эти уравнения в форму ряда строк . Z / 2 - это весело, потому что нет разницы между сложением и вычитанием. В двух словах, мы неоднократно выбираем переменную, которая появляется в каком-то оставшемся уравнении, добавляем это уравнение ко всем другим уравнениям, содержащим эту переменную, и отложим это уравнение в сторону. Я продемонстрирую.

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

Чтобы сделать вещи интересными, давайте выберем x21 в x12 + x21 = 1.

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

Обратите внимание, что x21 + x21 и 1 + 1 оба упрощаются до 0, так как мы работаем mod 2. Давайте теперь выберем x22 в x11 + x22 + x31 = 1.

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

Все переменные в уравнениях, которые мы не оставили в стороне, различны, поэтому следующие два шага скучны.

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

У нас есть 4 независимых уравнений, поэтому ответом является 2^(3*2 - 4) = 4 решения (в общем, 2^(board squares - equations)). Вроде скучный исход, но это то, что есть.

Когда мы сокращаем уравнения, могут произойти две интересные вещи. Давайте рассмотрим следующую доску.

E E
E E

Мы получаем следующие уравнения.

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

Теперь давайте уменьшим.

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

Мы получаем два вырожденных уравнения 0 = 0. Это означает, что мы получили избыточную информацию, и они не считаются независимыми уравнениями. Ответ здесь снова 2^(2*2 - 2) = 4.

Другая вещь, которая может случиться, - это то, что мы получаем уравнение 0 = 1. В этом случае нет решений, соответствующих подсказкам.

Оказывается, это не должно быть слишком плохо для грубой силы, по крайней мере, если ваша доска не слишком большая.

Вы можете определить свой набор бомб, где каждая ячейка может быть Present, Not Present или Unexplored, где Unexplored означает, что там может быть или не быть бомба. Затем вы можете написать метод, который берет вашу доску и этот набор бомб, и определяет, является ли доска недействительной или может быть действительной в зависимости от фактического значения любых Unexplored ячеек.

Тогда вы начинаете ходить по доске. Установите в первой ячейке значение Present и посмотрите, не приведет ли это к доске, которая может быть действительной (или определенно недействительной). Если это возможно, установите recurse на следующую ячейку. Затем установите для первой ячейки значение NotPresent и посмотрите, может ли это быть действительным, и рекурсивна ли она в следующую ячейку.

Эта обрезка досок, которые имеют небольшую площадь, которая является недействительной, должна значительно сократить пространство поиска по сравнению с полной грубой силой.

Когда вы проверяете, может ли доска быть действительной, вы можете оптимизировать ее, проверяя только ячейки в квадрате вокруг ячейки, которую вы изменили, поскольку это единственные ячейки, на которые можно повлиять.

Это не полноценное динамическое программирование, и, вероятно, выиграет от некоторого запоминания: если в правом нижнем углу есть комбинация бомб, которая недопустима (нижний правый является последней исследованной областью), она продолжит пробовать их снова и снова с различными (действительными) комбинациями бомб в других местах.

Это также застрянет, если у вашей доски большая открытая область, так как будет большое количество комбинаций, и это тщательно изучит каждую из них.

Я собрал немного C #, чтобы проиллюстрировать мою идею. Это не опрятно или не совсем ясно (и за это я прошу прощения - у меня не хватило времени, чтобы привести его в порядок), но он находит 4 решения для вашего второго примера.

Это написано с использованием рекурсии, поэтому взорвется стек с большими досками. Перепишите его, чтобы оно было итеративным.

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;
        }
    }
}