Ne trouvez aucune des formations possibles de mines explosives dans une matrice 2D où certaines cellules contiennent des informations sur les mines paires / impaires qui leur sont adjacentes

En gros, vous devez résoudre un système d'équations sur Z / 2. C'est en fait très similaire à jouer à un jeu appelé Lights Out. Prenons ce tableau par exemple.

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

Faisons des variables pour les différentes positions du tableau.

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

Nous obtenons des équations comme ça. Chaque O se transforme en une équation comme (somme des variables voisines) = 1 (mod 2) . Chaque E se transforme en une équation comme (somme des variables voisines) = 0 (mod 2) .

E E
E E

Utilisation Élimination gaussienne sur Z / 2 pour mettre ces équations sous la forme ligne échelonnée a >. Z / 2 est amusant car il n'y a aucune différence entre l'ajout et la soustraction. En un mot, nous choisissons à plusieurs reprises une variable qui apparaît dans une équation qui reste, ajoutons cette équation à toutes les autres équations qui contiennent cette variable et mettons cette équation de côté. Je vais vous démontrer.

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

Pour rendre les choses intéressantes, choisissons x21 dans x12 + x21 = 1 .

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

Notez que x21 + x21 et 1 + 1 se simplifient tous les deux en 0 , car nous travaillons mod 2 . Choisissons maintenant x22 dans x11 + x22 + x31 = 1 .

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

Toutes les variables des équations que nous n'ont pas été mis de côté sont distincts, donc les deux étapes suivantes sont ennuyeuses.

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

Nous avons 4 équations indépendantes, donc la réponse est 2 ^ (3 * 2 - 4) = 4 solutions (en général, 2 ^ (carrés du plateau - équations) ). Une sorte de résultat ennuyeux, mais c'est ce que c'est.

Deux choses intéressantes peuvent se produire lorsque nous réduisons des équations. Considérons le tableau suivant.

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

Nous obtenons les équations suivantes.

x11 x12
x21 x22
x31 x32

Maintenant, réduisons. P >

O N
O N
O E

Nous nous retrouvons avec deux équations dégénérées 0 = 0 . Cela signifie que nous avons reçu des informations redondantes et qu'elles ne comptent pas comme des équations indépendantes. La réponse ici est de nouveau 2 ^ (2 * 2 - 2) = 4 .

L'autre chose qui peut arriver est que nous obtenons une équation 0 = 1 . Dans ce cas, il n'y a pas de solution cohérente avec les astuces.

Il s'avère que cela ne devrait pas être trop mauvais pour la force brute, du moins si votre tableau n'est pas trop grand.

Vous pouvez définir votre ensemble de bombes où chaque cellule peut être Present code >, Non présent ou Unxplored , où Unxplored signifie qu'il peut y avoir ou non une bombe là-bas. Vous pouvez ensuite écrire une méthode qui prend votre carte et cet ensemble de bombes, et détermine si la carte est définitivement invalide, ou peut être valide en fonction de la valeur réelle de toute cellule Unxplored .

Ensuite, vous commencez à marcher sur la planche. Définissez la première cellule sur Present , et voyez si cela aboutit à un tableau qui pourrait être valide (ou qui est définitivement invalide). S'il peut être valide, définissez recurse sur la cellule suivante. Ensuite, définissez la première cellule sur NotPresent et voyez si cela pourrait être valide, et si elle est réitérée dans la cellule suivante.

Cet élagage des planches qui ont une petite zone qui n'est pas valide devrait réduire considérablement l'espace de recherche par rapport à une force brute à part entière.

Lorsque vous vérifiez si le tableau pourrait être valide, vous pouvez optimiser en vérifiant uniquement le cellules dans un carré autour de la cellule que vous avez modifiée, car ce sont les seules qui pourraient être affectées.

Ce n'est pas une programmation dynamique complète, et bénéficierait probablement d'une mémorisation: s'il y a une combinaison de bombes en bas à droite qui est invalide (le bas à droite étant la dernière zone explorée), il continuera à les essayer encore et encore avec différentes combinaisons (valides) de bombes ailleurs.

Cela s'enlisera également si votre planche a une grande zone ouverte, car il y aura un grand nombre de combinaisons et cela explorera méticuleusement chacune d'elles.

J'ai jeté ensemble quelques C # pour illustrer mon idée. Ce n'est pas net ou particulièrement clair (et pour cela je m'excuse - j'ai manqué de temps pour le ranger), mais il trouve les 4 solutions pour votre deuxième exemple.

Ceci est écrit en utilisant la récursivité, donc va soufflez la pile avec des planches plus grandes. Réécrivez-le pour qu'il soit itératif.

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

Joli problème. Cela ressemble à un problème de style de concours de programmation. Indice:

Représentez ceci comme un problème d'algèbre linéaire sur GF (2) (c'est-à-dire avec le module arithmétique 2), puis utilisez l'élimination gaussienne.

Indice:

Si on nous donne une matrice A et un vecteur b, pourrais-tu compter le nombre de solutions de l'équation $ Ax = b $? Comment?