“Привет Мир” - TDD путь?

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

Вы можете определить свой набор бомб, где каждая ячейка может быть 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;
        }
    }
}