Maître Minesweeper de l'épreuve de qualification du Google Code Jam(2014)

Question

Il s'agit d'un problème issu du tour de qualification du Google Code Jam (qui est maintenant terminé). Comment résoudre ce problème ?

Note : Si vous avez une méthode différente de celles présentées dans les réponses, veuillez la partager afin que nous puissions élargir nos connaissances sur les différentes façons de résoudre ce problème.

Énoncé du problème :

Minesweeper est un jeu d'ordinateur qui est devenu populaire dans les années 1980 et qui est toujours inclus dans certaines versions du système d'exploitation Microsoft Windows. Ce problème a une idée similaire, mais il ne suppose pas que vous ayez joué au Minesweeper.

Dans ce problème, vous jouez à un jeu sur une grille de cellules identiques. Le contenu de chaque cellule est initialement caché. Il y a M mines cachées dans M cellules différentes de la grille. Aucune autre cellule ne contient de mines. Vous pouvez cliquer sur n'importe quelle cellule pour la révéler. Si la cellule révélée contient une mine, le jeu est terminé et vous perdez. Sinon, la cellule révélée contiendra un chiffre compris entre 0 et 8 inclus, qui correspond au nombre de cellules voisines qui contiennent des mines. Deux cellules sont voisines si elles partagent un coin ou un bord. De plus, si la cellule révélée contient un 0, alors tous les voisins de la cellule révélée sont automatiquement révélés aussi, de manière récursive. Lorsque toutes les cellules qui ne contiennent pas de mines ont été révélées, le jeu se termine et vous gagnez.

Par exemple, une configuration initiale du tableau peut ressembler à ceci ('*' indique une mine, et 'c' est la première cellule cliquée) :

*..*...**.
....*.....
..c..*....
........*.
..........

Il n'y a pas de mines adjacentes à la cellule cliquée, donc lorsqu'elle est révélée, elle devient un 0, et ses 8 cellules adjacentes sont également révélées. Ce processus se poursuit, ce qui donne le tableau suivant :

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

À ce stade, il y a encore des cellules non révélées qui ne contiennent pas de mines (indiquées par les caractères "."), le joueur doit donc cliquer à nouveau pour continuer le jeu.

Vous voulez gagner la partie le plus rapidement possible. Il n'y a rien de plus rapide que de gagner en un clic. Compte tenu de la taille du plateau (R x C) et du nombre de mines cachées M, est-il possible (bien que peu probable) de gagner en un seul clic ? Vous pouvez choisir où vous cliquez. Si c'est possible, imprimez toute configuration de mine valide et les coordonnées de votre clic, en suivant les spécifications de la section Sortie. Sinon, imprimez "Impossible".

Ma solution éprouvée :

Pour la solution, vous devez donc vous assurer que chaque nœud non miné se trouve dans une matrice 3x3 avec d'autres nœuds non minés, ou une matrice 3x2 ou 2x2 si le nœud se trouve sur un bord de la grille ; appelons cela une matrice 0. Ainsi, tout nœud dans une matrice 0Matrix a tous les voisins non mineurs.

Premièrement, vérifiez si moins de mines sont nécessaires, ou moins de nœuds vides.

if(# mines required < 1/3 of total grid size)
    // Initialize the grid to all clear nodes and populate the mines
    foreach (Node A : the set of non-mine nodes)
        foreach (Node AN : A.neighbors)
            if AN forms a OMatrix with it's neighbors, continue
            else break;
        // If we got here means we can make A a mine since all of it's neighbors 
        // form 0Matricies with their other neighbors
    // End this loop when we've added the number of mines required

else
    // We initialize the grid to all mines and populate the clear nodes
    // Here I handle grids > 3x3; 
    // For smaller grids, I hard coded the logic, eg: 1xn grids, you just populate in 1 dimension

    // Now we know that the # clear nodes required will be 3n+2 or 3n+4
    // eg: if a 4x4 grid need 8 clear nodes : 3(2) + 2

    For (1 -> num 3's needed)
        Add 3 nodes going horizontally
        When horizontal axis is filled, add 3 nodes going vertically
           When vertical axis is filled, go back to horizontal then vertical and so on.

    for(1 -> num 2's needed)
        Add 2 nodes going horizontally or continuing in the direction from above
        When horizontal axis is filled, add 2 nodes going vertically

Par exemple, si nous avons une grille de 4x4 nécessitant 8 nœuds propres, voici les étapes à suivre :

// Initial grid of all mines
* * * *
* * * *
* * * *
* * * *

// Populating 3's horizontally
. * * *
. * * *
. * * *
* * * *     

. . * *
. . * *
. . * *
* * * *    

// Populating 2's continuing in the same direction as 3's
. . . *
. . . *
. . * *
* * * *        

Autre exemple : Grille 4x4 avec 11 nœuds clairs nécessaires ; sortie :

. . . .
. . . .
. . . *
* * * * 

Autre exemple : Grille 4x4 avec 14 nœuds clairs nécessaires ; sortie :

// Insert the 4 3's horizontally, then switch to vertical to insert the 2's
. . . .
. . . .
. . . .
. . * *  

Nous avons maintenant une grille qui est entièrement remplie et qui peut être résolue en un clic si nous cliquons sur (0, 0).

Ma solution fonctionne pour la plupart des cas, mais elle n'a pas passé la soumission (j'ai vérifié un fichier de sortie entier de 225 cas), donc je suppose qu'elle a quelques problèmes, et je suis presque sûr qu'il y a de meilleures solutions.

Answer 1

Algorithme

Définissons d'abord N le nombre de cellules non mineures :

N = R * C - M

Une solution simple consiste à remplir une zone de N les cellules non minées, ligne par ligne, de haut en bas. Exemple pour R=5 , C=5 , M=12 :

c....
.....
...**
*****
*****

C'est-à-dire :

• Commencez toujours par le coin supérieur gauche.
• Remplir N / C des rangs avec des non-mines de haut en bas.
• Remplissez la ligne suivante avec N % C non-mines de gauche à droite.
• Remplissez le reste avec des mines.

Il n'y a que quelques cas particuliers dont vous devez vous préoccuper.

Non-mine simple

Si N=1 toute configuration est une solution correcte.

Une seule ligne ou une seule colonne

Si R=1 il suffit de remplir le formulaire N non minées de gauche à droite. Si C=1 , remplir N rangs avec une (seule) non-mine.

Trop peu de non-mines

Si N est pair, il doit être >= 4.

Si N est impair, il doit être >= 9. Aussi, R y C doit être >= 3.

Sinon, il n'y a pas de solution.

Impossible de remplir les deux premières rangées

Si N est pair et que vous ne pouvez pas remplir au moins deux rangées avec des non-mines, alors remplissez les deux premières rangées avec des N / 2 non-mines.

Si N est impair et que vous ne pouvez pas remplir au moins deux rangées avec des non-mines et une troisième avec 3 non-mines, alors remplissez les deux premières rangées avec (N - 3) / 2 non-mines et la troisième rangée avec 3 non-mines.

Une seule non-mine dans la dernière rangée

Si N % C = 1 déplacez le dernier non-mine de la dernière rangée complète à la rangée suivante.

Exemple pour R=5 , C=5 , M=9 :

c....
.....
....*
..***
*****

Résumé

Il est possible d'écrire un algorithme qui met en œuvre ces règles et renvoie une description du champ de mines résultant en O(1) . Le dessin de la grille prend O(R*C) bien sûr. J'ai également écrit une implémentation en Perl basée sur ces idées qui a été acceptée par le juge du Code Jam.

Answer 2

Il existe une solution plus générale à ce problème qui réussit à la fois les petits et les grands scénarios de test. Elle évite d'avoir à penser à tous les cas particuliers, elle ne se soucie pas des dimensions de la carte et ne nécessite aucun retour en arrière.

ALGORITHME

L'idée de base est de commencer avec une grille pleine de mines et de les enlever en commençant par la cellule {0, 0} jusqu'à ce qu'il y ait le nombre correct de mines sur le plateau.

Il est évident qu'il faut trouver un moyen de déterminer quelles mines retirer ensuite et quand il est impossible de retirer le nombre correct de mines. Pour ce faire, nous pouvons conserver un int[][] qui représente le plateau. Chaque cellule contenant une mine contient -1 et celles sans mines contiennent un nombre entier qui est le nombre de mines adjacentes à la cellule, comme dans le jeu réel.

Définissez également le concept de "frontière", c'est-à-dire toutes les cellules non minées qui ne sont pas nulles, c'est-à-dire les cellules avec des mines adjacentes.

Par exemple la configuration :

c . *
. . *
. . *
* * *

Serait représenté comme :

 0  2 -1
 0  3 -1
 2  5 -1
-1 -1 -1

Et la frontière contiendrait les cellules avec des valeurs : 2, 3, 5, 2

Pour enlever les mines, la stratégie est la suivante :

• Trouver une case dans la frontière qui a la même valeur que le nombre restant de mines à enlever. Ainsi, dans l'exemple ci-dessus, s'il nous restait 5 mines à enlever, les cellules de valeur 5 sur la frontière seraient choisies.
• Dans le cas contraire, on choisit la plus petite cellule frontière. Donc l'un ou l'autre des 2 dans l'exemple ci-dessus.
• Si la valeur de la case choisie est supérieure au nombre de mines restant à enlever, alors il est impossible de construire ce plateau, donc retournez false.
• Sinon, retirer toutes les mines entourant la cellule frontière choisie.
• Répétez jusqu'à ce que le nombre correct de mines soit présent sur le tableau - les contraintes du problème ont été respectées.

En java, cela ressemble à :

// Tries to build a board based on the nMines in the test case
private static boolean buildBoard(TestCase t) throws Exception {
    if (t.nMines >= t.Board.rows() * t.Board.cols()) { 
        return false;
    }
    // Have to remove the cell at 0,0 as the click will go there
    t.Board.removeMine(0, 0);
    while (!t.boardComplete()) {
        Cell c = nextCell(t);
        // If the value of this cell is greater than what we need to remove we can't build a board
        if (t.Board.getCell(c.getRow(), c.getCol()) > t.removalsLeft()) {
            return false;
        }
        t.Board.removeNeighbourMines(c.getRow(), c.getCol());
    }

    return true;
}

// Find frontier cell matching removals left, else pick the smallest valued cell to keep things balanced
private static Cell nextCell(TestCase t) {
    Cell minCell = null;
    int minVal = Integer.MAX_VALUE;
    for (Cell c : t.Board.getFrontier()) {
        int cellVal = t.Board.getCell(c.getRow(), c.getCol());
        if (cellVal == t.removalsLeft()) {
            return c;
        }
        if (cellVal < minVal) {
            minVal = cellVal;
            minCell = c;
        }
    }
    if (minCell == null) {
        throw new NullPointerException("The min cell wasn't set");
    }
    return minCell;
}

PREUVE / INTUITION

Tout d'abord, un conseil est défini comme valide si elle peut être résolue par un seul clic, même s'il n'y a qu'une seule cellule sur le plateau où ce clic peut se produire. Par conséquent, pour qu'un tableau soit valide, toutes les cellules non minées doivent être adjacentes à une cellule ayant la valeur 0, si ce n'est pas le cas, la cellule est définie comme inaccessible . En effet, nous savons avec certitude que toutes les cellules adjacentes à une cellule 0 ne sont pas des mines, elles peuvent donc être révélées en toute sécurité et le jeu le fera automatiquement pour le joueur.

Un point clé à prouver pour cet algorithme est qu'il est toujours nécessaire de retirer toutes les mines entourant la plus petite cellule frontière afin de garder le plateau dans une cellule frontière. valide l'état. Il suffit pour s'en convaincre de dessiner un tableau (comme celui ci-dessus) et de choisir la case de valeur la plus faible (dans ce cas, la case 2 en haut à droite). Si une seule mine est retirée, le tableau n'est pas valide, il se trouve dans l'un de ces deux états :

 0  1  1
 0  2 -1
 2  5 -1
-1 -1 -1

ou

 0  1 -1
 0  2  2
 2  5 -1
-1 -1 -1

qui ont tous deux inaccessible cellules.

Il est donc maintenant vrai que le fait de toujours choisir la plus petite cellule frontière maintient la carte dans un état valide et mon premier réflexe était de penser qu'en continuant à choisir ces cellules, on passerait par tous les états valides, mais ce n'est pas le cas. Ceci peut être illustré par un cas de test tel que 4 4 7 (il y a donc 9 cellules non minées). Considérons ensuite le tableau suivant :

 0  2 -1 -1
 2  5 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

En continuant à choisir la plus petite cellule frontière, l'algorithme peut faire ce qui suit :

 0  2 -1 -1
 0  3 -1 -1
 0  3 -1 -1
 0  2 -1 -1

Ce qui signifie qu'il est maintenant impossible de retirer une seule mine pour compléter le tableau dans ce cas. Cependant, le choix d'une case frontière correspondant au nombre de mines restantes (s'il en existe une) garantit que les 5 auraient été choisies, ce qui donne un carré 3x3 de non-mines et une solution correcte au cas test.

À ce stade, j'ai décidé d'essayer l'algorithme sur tous les cas de test dans la gamme suivante :

0 < R < 20
0 < C < 20
0 ≤ M < R * C

et constaté qu'il a réussi à identifier correctement toutes les configurations impossibles et à construire ce qui ressemblait à sensible des solutions aux configurations possibles.

L'intuition supplémentaire derrière la raison pour laquelle le choix de la cellule frontière avec la même valeur que le nombre restant de mines (s'il existe) est correct est qu'il permet à l'algorithme de trouver des configurations pour les solutions nécessitant une étrange le nombre de non-mines.

Lors de l'implémentation initiale de cet algorithme, j'avais l'intention d'écrire une heuristique qui construisait la zone non minée dans une disposition carrée. En considérant la 4 4 7 le test de cas à nouveau, il finirait par faire ceci :

 0  0  2 -1
 0  1  4 -1
 2  4 -1 -1
-1 -1 -1 -1

remarquez comment nous avons maintenant un 1 sur la frontière qui ferait en sorte que la dernière cellule enlevée complète le carré à donner :

c . . *
. . . *
. . . *
* * * *

Cela signifie que l'heuristique change légèrement pour :

• Choisir la plus petite cellule frontière
• En cas d'égalité, choisir la première cellule ajoutée à la liste des frontières.

Cela pourrait être mis en œuvre en gardant une file d'attente FIFO des cellules frontières, mais j'ai rapidement réalisé que c'est plus délicat qu'il n'y paraît. Cela est dû au fait que les valeurs des cellules frontières sont interdépendantes et qu'il faut donc veiller à maintenir la collection de cellules frontières dans le bon état et à ne pas utiliser la valeur des cellules dans une quelconque valeur de hachage, etc. Je suis sûr que cela pourrait être fait, mais en réalisant que l'ajout d'une heuristique supplémentaire pour choisir toutes les cellules avec des valeurs égales aux suppressions restantes fonctionnait, cela semblait être l'approche la plus facile.

Answer 3

C'est mon code . J'ai résolu en prenant différents cas comme si number of rows=1 o number of columns=1 ou si number of mines=(r*c)-1 et quelques autres cas.

La position sur la mise en page à cliquer est placée à a[r-1][c-1] ('0' indexé) à chaque fois.

Pour cette question, j'avais fait quelques tentatives erronées et chaque fois, je trouvais un nouveau cas. J'ai éliminé quelques cas dans lesquels la solution n'est pas possible en utilisant goto et le laisser sauter à la fin où il imprime impossible. Une solution très simple (on peut en effet dire que c'est une solution de force brute puisque j'ai codé pour différents cas possibles individuellement). Ceci est un éditorial pour mon code. Et sur github .

Answer 4

J'ai utilisé la recherche avec backtracking, mais je n'ai pu résoudre que la petite entrée.

En gros, l'algorithme part d'un tableau rempli de mines et essaie de retirer les mines de manière à ce que le premier "clic" résolve le tableau. Le problème est que pour permettre à un "clic" de s'étendre à une autre cellule, l'expansion proviendra d'une autre cellule dont toutes les autres cellules voisines doivent également être déminées. Parfois, pour s'étendre à une autre cellule, il faut enlever d'autres mines et se retrouver avec moins de mines que nécessaire. L'algorithme fera marche arrière s'il atteint une telle position.

Il est peut-être plus simple de faire l'inverse. Commencez par un plateau vide et ajoutez chaque mine de manière à ne pas empêcher l'"expansion" du clic initial.

Le code Python complet est ci-dessous :

directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1,  -1],  [1, 0],  [1, 1],
]

def solve(R, C, M):
    def neighbors(i, j):
        for di, dj in directions:
            if 0 <= (i + di) < R and 0 <= (j + dj) < C:
                yield (i + di, j + dj)

    def neighbors_to_clear(i, j, board):
        return [(ni, nj) for ni, nj in neighbors(i, j) if board[ni][nj] == "*"]

    def clear_board(order):
        to_clear = R * C - M - 1
        board = [["*" for _ in range(C)] for _ in range(R)]
        for i, j in order:
            board[i][j] = "."
            for ni, nj in neighbors_to_clear(i, j, board):
                to_clear -= 1
                board[ni][nj] = "."
        return board, to_clear

    def search(ci, cj):
        nodes = []
        board = []
        to_clear = 1
        nodes.append((ci, cj, []))
        while nodes and to_clear > 0:
            i, j, order = nodes.pop()
            board, to_clear = clear_board(order)
            neworder = order + [(i, j)]
            if to_clear == 0:
                board[ci][cj] = "c"
                return board
            elif to_clear > 0:
                for ni, nj in neighbors_to_clear(i, j, board):
                    board[ni][nj] = "."
                    nodes.append([ni, nj, neworder])

    for i in range(R):
        for j in range(C):
            board = search(i, j)
            if board:
                for row in board:
                    print "".join(row)
                return

    print "Impossible"
    return

T = int(raw_input())
for i in range(1, T + 1):
    R, C, M = map(int, raw_input().split(" "))
    print("Case #%d:" % i)
    solve(R, C, M)

Answer 5

Ma stratégie était très similaire à la vôtre et j'ai réussi les petits et les grands examens. Avez-vous pensé aux cas ci-dessous ?

• R * C - M = 1

• Il n'y a qu'une seule ligne

• Il n'y a que deux rangées

---

J'ai inversé R et C quand R > C.