Algorithme de largage de bombes

J’ai une masortingce nxm composée d’entiers non négatifs. Par exemple:

 2 3 4 7 1 1 5 2 6 2 4 3 4 2 1 2 1 2 4 1 3 1 3 4 1 2 1 4 3 2 6 9 1 6 4 

“Laisser tomber une bombe” diminue d’un chiffre le nombre de cellules cibles et de ses huit voisins, jusqu’à un minimum de zéro.

 xxxx X x xxx 

Qu’est-ce qu’un algorithme qui déterminerait le nombre minimum de bombes nécessaires pour réduire toutes les cellules à zéro?

Option B (parce que je ne suis pas un lecteur prudent)

En fait, la première version du problème n’est pas celle à laquelle je cherche une réponse. Je n’ai pas lu attentivement toute la tâche, il y a des contraintes supplémentaires, disons:

Qu’en est-il du problème simple, lorsque la séquence en ligne doit être non croissante:

8 7 6 6 5 est la séquence d’entrée possible

7 8 5 5 2 n’est pas possible puisque 7 -> 8 croissent dans une séquence.

Peut-être que trouver une réponse à un cas “plus facile” aiderait à trouver une solution pour un cas plus difficile.

PS: Je pense que lorsque nous avons plusieurs situations identiques, nous avons besoin de bombes minimum pour dégager la ligne supérieure, nous en choisissons une qui utilise la plupart des bombes du “côté gauche” de la rangée. Toujours une preuve qui pourrait être correcte?

Il existe un moyen de réduire cela à un sous-problème simple.

L’explication comprend deux parties, l’algorithme et la raison pour laquelle l’algorithme fournit une solution optimale. Le premier n’aura pas de sens sans le second, alors je vais commencer par le pourquoi.

Si vous songez à bombarder le rectangle (supposez un grand rectangle – pas encore de bordures), vous pouvez voir que la seule façon de réduire le rectangle creux des carrés sur le périmètre à 0 est de bombarder le périmètre ou de bombarder le rectangle creux de carrés juste à l’intérieur du périmètre. Je vais appeler la couche périmésortingque 1 et le rectangle à l’intérieur de la couche 2.

Un point important est qu’il n’ya pas de couche 1 de bombardement ponctuel, car le rayon d’explosion que vous obtenez est toujours contenu dans le rayon d’explosion d’un autre carré de la couche 2. Vous devriez pouvoir vous en convaincre facilement.

Donc, nous pouvons réduire le problème à trouver un moyen optimal pour bombarder le périmètre, alors nous pouvons répéter cela jusqu’à ce que tous les carrés soient à 0.

Mais bien sûr, cela ne trouvera pas toujours une solution optimale s’il est possible de bombarder le périmètre de manière moins optimale, mais en utilisant des bombes X supplémentaires, le problème de la réduction de la couche interne est simplifié par des bombes X>. Donc, si nous appelons la couche 1 du permitateur, si nous plaçons des bombes X supplémentaires quelque part dans la couche 2 (juste à l’intérieur de la couche 1), pouvons-nous réduire l’effort de bombarder la couche 2 par plus de X? En d’autres termes, nous devons prouver que nous pouvons être avides en réduisant le périmètre extérieur.

Mais nous soaps que nous pouvons être gourmands. Parce qu’aucune bombe dans la couche 2 ne peut jamais être plus efficace pour réduire la couche 2 à 0 qu’une bombe placée stratégiquement dans la couche 3. Et pour la même raison qu’auparavant – nous pouvons toujours placer une bombe dans la couche 3 qui affectera chaque case de la couche 2 qu’une bombe placée dans la couche 2 peut. Donc, il ne peut jamais nous nuire à être gourmand (dans ce sens de gourmandise).

Il suffit donc de trouver le moyen optimal de réduire le permit à 0 en bombardant la couche suivante.

Nous ne sums jamais blessés en bombardant d’abord le coin à 0, car seul le coin de la couche intérieure peut l’atteindre, donc nous n’avons vraiment pas le choix (et toute bombe sur le périmètre qui peut atteindre le coin a un rayon d’explosion contenu dans le rayon de souffle du coin de la couche interne).

Une fois cela fait, les carrés du périmètre adjacent au coin 0 ne peuvent être atteints que par 2 carrés de la couche interne:

 0 AB CXY DZ 

À ce stade, le périmètre est effectivement une boucle 1 dimension fermée, car toute bombe réduira 3 carrés adjacents. A part quelques étrangetés près des coins – X peut “toucher” A, B, C et D.

Maintenant, nous ne pouvons utiliser aucune astuce de rayon de souffle – la situation de chaque carré est symésortingque, sauf pour les coins étranges, et même là, aucun rayon d’explosion n’est un sous-ensemble d’un autre. Notez que s’il s’agissait d’une ligne (comme le dit Colonel Panic) au lieu d’une boucle fermée, la solution est sortingviale. Les points de fin doivent être réduits à 0, et cela ne vous empêche jamais de bombarder les points adjacents aux points d’extrémité, à nouveau parce que le rayon d’explosion est un sur-ensemble. Une fois que vous avez créé votre sharepoint terminaison 0, vous avez toujours un nouveau sharepoint terminaison, alors répétez l’opération (jusqu’à ce que la ligne soit tout 0).

Donc, si nous pouvons réduire de manière optimale un seul carré dans le calque à 0, nous avons un algorithme (car nous avons coupé la boucle et avons maintenant une ligne droite avec les points finaux). Je crois que le bombardement adjacent à la case avec la valeur la plus basse (vous donnant 2 options) de sorte que la valeur la plus élevée dans les 2 cases de cette valeur la plus basse soit le minimum possible (vous devrez diviser votre bombardement pour gérer cela) sera optimal mais je ne pas (encore?) avoir une preuve.

Pólya dit: “Si vous ne pouvez pas résoudre un problème, il existe un problème plus facile à résoudre: trouvez-le.”

Le problème le plus simple évident est le problème à une dimension (lorsque la grid est une seule ligne). Commençons par l’algorithme le plus simple – bombarder avec avidité la plus grande cible. Quand cela ne va pas?

Vu 1 1 1 , l’algorithme glouton est indifférent à quelle cellule il bombarde en premier. Bien sûr, la cellule centrale est meilleure – elle zéros les trois cellules à la fois. Cela suggère un nouvel algorithme A, “bombe pour minimiser la sum restante”. Quand cet algorithme va-t-il mal?

Étant donné 1 1 2 1 1 , l’algorithme A est indifférent entre le bombardement des 2ème, 3ème et 4ème cellules. Mais bombarder la 2ème cellule pour partir 0 0 1 1 1 vaut mieux que bombarder la 3ème cellule pour partir 1 0 1 0 1 . Comment réparer ça? Le problème avec le bombardement de la 3ème cellule est que cela nous laisse travailler à gauche et travailler à droite, ce qui doit être fait séparément.

Qu’en est-il de “bombarder pour minimiser la sum restante, mais maximiser le minimum à gauche (de l’endroit où nous avons bombardé) plus le minimum à droite”. Appelez cet algorithme B. Quand cet algorithme se passe-t-il mal?


Edit: Après avoir lu les commentaires, je suis d’accord sur le fait qu’un problème beaucoup plus intéressant serait que le problème à une dimension soit modifié pour que les fins se rejoignent. J’adorerais voir des progrès à ce sujet.

Je n’avais plus qu’une solution partielle puisque je n’avais plus de temps, mais j’espère que même cette solution partielle fournira des indications sur une approche potentielle pour résoudre ce problème.

Face à un problème difficile, j’aime trouver des problèmes plus simples pour développer une intuition sur l’espace problématique. Ici, la première étape a été de réduire ce problème 2D en un problème 1-D. Considérons une ligne:

 0 4 2 1 3 0 1 

D’une manière ou d’une autre, vous savez que vous devrez bombarder à 4 ou près du point 4 pour le ramener à 0. Comme il rest un nombre plus faible, il n’y a aucun avantage à bombarder le 0 ou le 4 2 . En fait, je crois (mais sans une preuve rigoureuse) que bombarder le 2 jusqu’à ce que le point 4 tombe à 0 est au moins aussi bon que toute autre stratégie pour ramener ce 4 à 0. On peut descendre la ligne de gauche à droite dans une stratégie comme celle-ci:

 index = 1 while index < line_length while number_at_index(index - 1) > 0 bomb(index) end index++ end # take care of the end of the line while number_at_index(index - 1) > 0 bomb(index - 1) end 

Quelques exemples de bombardements:

 0 4[2]1 3 0 1 0 3[1]0 3 0 1 0 2[0]0 3 0 1 0 1[0]0 3 0 1 0 0 0 0 3[0]1 0 0 0 0 2[0]0 0 0 0 0 1[0]0 0 0 0 0 0 0 0 4[2]1 3 2 1 5 3[1]0 3 2 1 5 2[0]0 3 2 1 5 1[0]0 3 2 1 5 0 0 0 3[2]1 5 0 0 0 2[1]0 5 0 0 0 1[0]0 5 0 0 0 0 0 0[5] 0 0 0 0 0 0[4] 0 0 0 0 0 0[3] 0 0 0 0 0 0[2] 0 0 0 0 0 0[1] 0 0 0 0 0 0 0 

L’idée de commencer avec un nombre qui doit suivre une voie ou une autre est attrayante car il devient soudain possible de trouver une solution qui, selon certains, est au moins aussi bonne que toutes les autres solutions.

La prochaine étape dans la complexité où cette recherche d’ au moins autant est toujours possible est sur le bord du tableau. Il est clair pour moi qu’il n’y a aucun avantage ssortingct à bombarder le bord extérieur; vous feriez mieux de bombarder le spot et d’obtenir trois autres espaces gratuitement. Compte tenu de cela, nous pouvons dire que bombarder l’anneau à l’intérieur du bord est au moins aussi efficace que bombarder le bord. De plus, nous pouvons combiner cela avec l’intuition que bombarder le bon à l’intérieur du bord est en réalité le seul moyen d’obtenir des espaces de bord à 0. Plus encore, il est sortingvial de trouver la stratégie optimale (en ce sens qu’elle est à moins bonne que toute autre stratégie) pour ramener les chiffres d’angle à 0. Nous rassemblons tout cela et pouvons nous rapprocher d’une solution dans l’espace 2D.

Compte tenu de l’observation des pièces de coin, nous pouvons affirmer que nous connaissons la stratégie optimale pour passer de n’importe quel tableau de départ à un tableau avec des zéros dans tous les coins. Ceci est un exemple d’un tel tableau (j’ai emprunté les numéros des deux tableaux linéaires ci-dessus). J’ai étiqueté certains espaces différemment et je vais vous expliquer pourquoi.

 0 4 2 1 3 0 1 0 4 xxxxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 

On remarquera que la rangée supérieure ressemble beaucoup à l’exemple linéaire que nous avons vu précédemment. Rappelant notre observation précédente selon laquelle le meilleur moyen de ramener la rangée supérieure à 0 est de bombarder la deuxième rangée (la rangée x ). Il n’y a aucun moyen d’effacer la rangée supérieure en bombardant l’une des deux lignes et sans avantage supplémentaire à bombarder la rangée supérieure au-dessus du bombardement de l’espace correspondant sur la rangée x .

On pourrait appliquer la stratégie linéaire d’en haut (bombarder les espaces correspondants sur la rangée x ), ne nous intéressant qu’à la rangée supérieure et à rien d’autre. Ça irait quelque chose comme ça:

 0 4 2 1 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 3 1 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 2 0 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 1 0 0 3 0 1 0 4 x[x]xxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 0 0 0 0 3 0 1 0 4 xxxxxx 4 2 yyyyyy 2 1 yyyyyy 1 3 yyyyyy 3 2 yyyyyy 2 1 yyyyyy 1 5 yyyyyy 5 0 4 2 1 3 0 1 0 

La faille dans cette approche devient très évidente dans les deux derniers bombardements. C’est clair, étant donné que les seuls sites de bombardement qui réduisent le chiffre 4 dans la première colonne de la deuxième ligne sont le premier x et le y . Les deux derniers bombardements sont nettement inférieurs à un simple bombardement des premiers x , ce qui aurait fait exactement la même chose (en ce qui concerne la première place dans la rangée du haut, que nous n’avons pas d’autre moyen de supprimer). Comme nous avons démontré que notre stratégie actuelle est sous-optimale, une modification de la stratégie est clairement nécessaire.

À ce stade, je peux faire un pas en arrière dans la complexité et me concentrer sur un seul coin. Considérons celui-ci:

 0 4 2 1 4 xya 2 z . . 1 b . . 

Il est clair que la seule façon d’obtenir des espaces de 4 à zéro consiste à bombarder une combinaison de x , y et z . Avec quelques acrobaties en tête, je suis à peu près sûr que la solution optimale consiste à bombarder trois fois, puis a puis b . Maintenant, il s’agit de savoir comment j’ai atteint cette solution et si elle révèle toute intuition que nous pouvons utiliser pour résoudre ce problème local. Je remarque qu’il n’y a pas de bombardement des espaces y et z . Tenter de trouver un coin où bombarder ces espaces est judicieux donne un coin qui ressemble à ceci:

 0 4 2 5 0 4 xya . 2 z . . . 5 b . . . 0 . . . . 

Pour celui-ci, il est clair pour moi que la solution optimale consiste à bombarder 5 fois et z 5 fois. Allons plus loin.

 0 4 2 5 6 0 0 4 xya . . . 2 z . . . . . 5 b . . . . . 6 . . . . . . 0 . . . . . . 0 . . . . . . 

Ici, il est tout aussi intuitif que la solution optimale consiste à bombarder a et b 6 fois, puis x 4 fois.

Maintenant, cela devient un jeu sur la façon de transformer ces intuitions en principes sur lesquels nous pouvons nous appuyer.

Espérons être continués!

Pour la question mise à jour, un algorithme simple gourmand donne un résultat optimal.

Déposez les bombes A [0,0] dans la cellule A [1,1], puis déposez A [1,0] bombes dans la cellule A [2,1] et poursuivez ce processus vers le bas. Pour nettoyer le coin inférieur gauche, déposez les bombes max (A [N-1,0], A [N-2,0], A [N-3,0]) dans la cellule A [N-2,1]. Cela va complètement nettoyer les 3 premières colonnes.

Avec la même approche, nettoyer les colonnes 3,4,5, puis les colonnes 6,7,8, etc.

Malheureusement, cela ne permet pas de trouver une solution au problème initial.


Le problème “plus grand” (sans contrainte “non croissante”) peut s’avérer être NP-difficile. Voici un croquis d’une preuve.

Supposons que nous ayons un graphe planaire de degré inférieur à 3. Trouvons une couverture minimale de sumt pour ce graphe. Selon l’article de Wikipedia, ce problème est NP-difficile pour les graphes planaires de degré jusqu’à 3. Cela pourrait être prouvé par la réduction de Planar 3SAT. Et dureté de Planar 3SAT – par réduction de 3SAT. Ces deux preuves sont présentées dans des conférences récentes sur “Algorithmic Lower Bounds” par le prof. Erik Demaine (conférences 7 et 9).

Si nous divisons des arêtes du graphique original (graphique de gauche sur le diagramme), chacune avec un nombre pair de noeuds supplémentaires, le graphique résultant (graphique de droite sur le diagramme) devrait avoir exactement la même couverture de sumt minimum pour les sumts originaux. Une telle transformation permet d’aligner les sumts des graphes sur des positions arbitraires sur la grid.

entrer la description de l'image ici

Si nous plaçons des sumts de graphes uniquement sur des lignes et des colonnes paires (de manière à ce que deux arêtes n’atteignent pas un angle aigu), insérez “des” là où il y a un bord et insérez des “zéros” à d’autres positions de la grid. Nous pourrions utiliser n’importe quelle solution pour résoudre le problème initial afin de trouver une couverture minimale de vertex.

Vous pouvez représenter ce problème en tant que problème de programmation d’entier . (Ceci est juste l’une des solutions possibles pour aborder ce problème)

Avoir des points:

 abcd efgh ijkl mnop 

on peut écrire 16 équations où pour le point f par exemple détient

 f <= ai + bi + ci + ei + fi + gi + ii + ji + ki 

minimisé sur la sum de tous les index et de la solution entière.

La solution est bien sûr la sum de ces index.

Cela peut être simplifié davantage en définissant tous les xi sur les limites 0, vous obtenez donc une équation de 4 + 1 dans cet exemple.

Le problème est qu'il n'y a pas d'algorhitm sortingvial pour résoudre de tels problèmes. Je ne suis pas expert en la matière, mais résoudre ce problème en tant que programmation linéaire est difficile.

Ceci est une réponse partielle, j’essaie de trouver une limite inférieure et une limite supérieure qui pourraient être le nombre possible de bombes.

Dans les cartes 3×3 et moins, la solution est sortingvialement toujours la plus grande cellule numérotée.

Dans les cartes plus grandes que 4×4, la première limite inférieure évidente est la sum des coins:

 *2* 3 7 *1* 1 5 6 2 2 1 3 2 *6* 9 6 *4* 

Cependant, il est impossible de nettoyer cette carte 4×4 avec moins de 2 + 1 + 6 + 4 = 13 bombes.

Il a été mentionné dans d’autres réponses que placer la bombe du deuxième au coin pour éliminer le coin n’est jamais pire que de placer la bombe sur le coin lui-même:

 *2* 3 4 7 *1* 1 5 2 6 2 4 3 4 2 1 2 1 2 4 1 3 1 3 4 1 2 1 4 3 2 *6* 9 1 6 *4* 

Nous pouvons éliminer les virages en plaçant des bombes du second au coin pour donner un nouveau tableau:

  0 1 1 6 0 0 3 0 5 1 2 1 1 1 0 2 1 2 4 1 0 0 0 0 0 0 0 0 0 0 0 3 0 2 0 

Jusqu’ici tout va bien. Nous avons besoin de 13 bombes pour dégager les coins.

Observez maintenant les chiffres 6, 4, 3 et 2 indiqués ci-dessous:

  0 1 1 *6* 0 0 3 0 5 1 2 1 1 1 0 *2* 1 2 *4* 1 0 0 0 0 0 0 0 0 0 0 0 *3* 0 2 0 

Il n’y a aucun moyen de bombarder deux de ces cellules en utilisant une seule bombe, de sorte que la bombe minimale a augmenté de 6 + 4 + 3 + 2, ajoutant ainsi au nombre de bombes que nous utilisions pour dégager les virages. nombre de bombes nécessaires pour cette carte est devenu 28 bombes. Il est impossible d’effacer cette carte avec moins de 28 bombes, c’est la limite inférieure de cette carte.

Vous pouvez utiliser un algorithme glouton pour établir une limite supérieure. D’autres réponses ont montré qu’un algorithme glouton produit une solution qui utilise 28 bombes. Comme nous avons prouvé plus tôt qu’aucune solution optimale ne peut avoir moins de 28 bombes, 28 bombes constituent donc une solution optimale.

Lorsque la méthode gourmande et la méthode pour trouver la limite minimale que j’ai mentionnée ci-dessus ne convergent pas, je suppose que vous devez recommencer à vérifier toutes les combinaisons.

L’algorithme pour trouver la limite inférieure est le suivant:

  1. Choisissez un élément avec le plus grand nombre, nommez-le P.
  2. Marquez toutes les cellules à deux pas de P et P elle-même comme non sélectionnable.
  3. Ajoutez P à la liste minimums .
  4. Répétez à l’étape 1 jusqu’à ce que toutes les cellules ne soient pas sélectionnables.
  5. Sommez la liste minimums pour obtenir la limite inférieure.

Ce serait une approche gourmande:

  1. Calculer une masortingce “score” d’ordre n X m, où score [i] [j] est la déduction totale des points dans la masortingce si la position (i, j) est bombardée. (Le score maximum d’un point est 9 et le score minimum est 0)

  2. En déplaçant la rangée, trouvez et choisissez la première position avec le score le plus élevé (dites (i, j)).

  3. Bombe (i, j). Augmente le nombre de bombes.

  4. Si tous les éléments de la masortingce d’origine ne sont pas nuls, passez à 1.

Je doute que ce soit la solution optimale.

Modifier:

L’approche Greedy que j’ai décrite ci-dessus, bien que cela fonctionne, ne nous a probablement pas fourni la solution optimale. Je pensais donc qu’il fallait y append des éléments de DP.

Je pense que nous pouvons convenir qu’à n’importe quel moment, l’une des positions ayant le «score» le plus élevé (score [i] [j] = déduction totale des points si (i, j) est bombardé) doit être ciblée. À partir de cette hypothèse, voici la nouvelle approche:

NumOfBombs (M): (renvoie le nombre minimum de bombardements requirejs)

  1. Étant donné une masortingce M d’ordre n X m. Si tous les éléments de M sont nuls, renvoyez 0.

  2. Calculez la masortingce “score” M.

    Soit les positions distinctes P1, P2, … Pk (1 <= k <= n * m), soit les positions dans M avec les scores les plus élevés.

  3. return (1 + min (NumOfBombs (M1), NumOfBombs (M2), …, NumOfBombs (Mk)))

    où M1, M2, …, Mk sont les masortingces résultantes si nous bombardons les positions P1, P2, …, Pk respectivement.

De plus, si nous voulons en plus l’ordre des positions, nous devrons suivre les résultats de «min».

Votre nouveau problème, avec les valeurs non décroissantes sur les lignes, est assez facile à résoudre.

Observez que la colonne de gauche contient les nombres les plus élevés. Par conséquent, toute solution optimale doit d’abord réduire cette colonne à zéro. Ainsi, nous pouvons effectuer un bombardement 1D sur cette colonne, réduisant chaque élément à zéro. Nous avons laissé les bombes tomber sur la deuxième colonne pour qu’elles causent un maximum de dégâts. Il y a beaucoup de messages ici traitant de l’affaire 1D, je pense, donc je me sens en sécurité pour sauter cette affaire. (Si vous voulez que je le décrive, je peux.) En raison de la propriété décroissante, les trois colonnes les plus à gauche seront toutes réduites à zéro. Mais, nous utiliserons ici un nombre minimum de bombes car la colonne de gauche doit être mise à zéro.

Maintenant, une fois que la colonne de gauche est mise à zéro, nous supprimons simplement les trois colonnes les plus à gauche qui sont maintenant mises à zéro et répétons avec la masortingce maintenant réduite. Cela doit nous donner une solution optimale car à chaque étape, nous utilisons un nombre minimum de bombes.

Il n’y a pas besoin de transformer le problème en sous-problèmes linéaires.

Utilisez plutôt une simple heuristique gourmande, qui consiste à bombarder les coins , en commençant par le plus grand.

Dans l’exemple donné, il y a quatre coins, {2, 1, 6, 4}. Pour chaque coin, il n’y a pas de meilleur mouvement que de bombarder la cellule en diagonale jusqu’au coin, donc nous soaps que nos premiers 2 + 1 + 6 + 4 = 13 bombardements doivent être dans ces cellules diagonales. Après avoir fait le bombardement, nous nous retrouvons avec une nouvelle masortingce:

 2 3 4 7 1 0 1 1 6 0 0 1 1 6 0 1 1 6 0 0 0 5 0 0 0 1 5 2 6 2 0 3 0 5 1 0 3 0 5 1 => 1 0 4 0 => 0 0 3 => 0 0 0 4 3 4 2 1 2 1 1 1 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 3 2 1 2 4 1 => 2 1 2 4 1 => 2 1 2 4 1 0 0 3 0 0 0 3 3 1 3 4 1 0 0 0 0 0 0 0 0 0 0 2 1 4 3 2 0 0 0 0 0 0 0 0 0 0 6 9 1 6 4 0 3 0 2 0 0 0 0 0 0 

Après les 13 premiers attentats, nous utilisons l’heuristique pour éliminer 3 0 2 via trois attentats à la bombe. Maintenant, nous avons 2 nouveaux coins, {2, 1} dans la 4ème ligne. Nous bombardons ces trois autres attentats. Nous avons réduit la masortingce à 4 x 4 maintenant. Il y a un coin, en haut à gauche. Nous bombardons ça. Maintenant nous avons 2 coins à gauche, {5, 3}. Le 5 étant le plus grand virage, nous bombardons le premier, 5 attentats à la bombe, puis bombardons le 3 dans l’autre coin. Le total est 13 + 3 + 3 + 1 + 5 + 3 = 28.

Cela fait une recherche approfondie du chemin le plus court (une série de bombardements) à travers ce “labyrinthe” de positions. Non, je ne peux pas prouver qu’il n’y a pas d’algorithme plus rapide, désolé.

 #!/usr/bin/env python M = ((1,2,3,4), (2,3,4,5), (5,2,7,4), (2,3,5,8)) def eachPossibleMove(m): for y in range(1, len(m)-1): for x in range(1, len(m[0])-1): if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] == m[y][x-1] == m[y][x] == m[y][x+1] == m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]): continue yield x, y def bomb(m, (mx, my)): return tuple(tuple(max(0, m[y][x]-1) if mx-1 <= x <= mx+1 and my-1 <= y <= my+1 else m[y][x] for x in range(len(m[y]))) for y in range(len(m))) def findFirstSolution(m, path=[]): # print path # print m if sum(map(sum, m)) == 0: # empty? return path for move in eachPossibleMove(m): return findFirstSolution(bomb(m, move), path + [ move ]) def findShortestSolution(m): black = {} nextWhite = { m: [] } while nextWhite: white = nextWhite nextWhite = {} for position, path in white.iteritems(): for move in eachPossibleMove(position): nextPosition = bomb(position, move) nextPath = path + [ move ] if sum(map(sum, nextPosition)) == 0: # empty? return nextPath if nextPosition in black or nextPosition in white: continue # ignore, found that one before nextWhite[nextPosition] = nextPath def main(argv): if argv[1] == 'first': print findFirstSolution(M) elif argv[1] == 'shortest': print findShortestSolution(M) else: raise NotImplementedError(argv[1]) if __name__ == '__main__': import sys sys.exit(main(sys.argv)) 

Il semble qu’une approche de programmation linéaire puisse être très utile ici.

Soit P mxn la masortingce avec les valeurs des positions:

Matrice de positions

Maintenant, définissons une masortingce de bombe B (x, y) mxn , avec 1 ≤ x ≤ m , 1 ≤ y ≤ n comme ci-dessous

Matrice de bombe

de telle sorte que

Valeurs de positions dans la matrice de bombes

Par exemple:

B (3, 3)

Donc, nous cherchons à une masortingce B mxn = [ b ij ] qui

  1. Peut être défini comme une sum de masortingces de bombe:

    B comme somme de matrices de bombe

    ( q ij serait alors la quantité de bombes qu’on tomberait en position p ij )

  2. p ij – b ij ≤ 0 (to be more succint, let us say it as P – B ≤ 0 )

Also, B should minimize the sum sum of quantities of bombs .

We can also write B as the ugly masortingx ahead:

B as a matrix of sum of quantities

and since P – B ≤ 0 (which means P ≤ B ) we have the following pretty linear inequality system below:

Relationship between number of bombs dropped and values in positions

Being q mn x 1 defined as

Vector of quantities

p mn x 1 defined as

Values of P distributed as a vector

We can say we have a system The system below represented as product of masortingces http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D being S mn x mn the masortingx to be reversed to solve the system. I did not expand it myself but I believe it should be easy to do it in code.

Now, we have a minimum problem which can be stated as

The system we have to solve

I believe it is something easy, almost sortingvial to be solved with something like the simplex algorithm (there is this rather cool doc about it ). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future…), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can’t go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.

(Special thanks for this amazing site to create pictures from LaTeX expressions )

This greedy solution seems to be correct :

As pointed in comments, it’ll fail in 2D. But maybe you may improve it.

For 1D:
If there is at least 2 numbers you don’t need to shoot to the leftmost one because shooting to the second is not worse . So shoot to the second, while first isn’t 0, because you have to do it. Move to the next cell. Don’t forget about last cell.

C++ code:

 void bombs(vector& v, int i, int n){ ans += n; v[i] -= n; if(i > 0) v[i - 1] -= n; if(i + 1< v.size()) v[i + 1] -= n; } void solve(vector v){ int n = v.size(); for(int i = 0; i < n;++i){ if(i != n - 1){ bombs(v, i + 1, v[i]); } else bombs(v, i, v[i]) } } 

So for 2D:
Again: you don't need to shoot in the first row (if there is the second). So shoot to the second one. Solve 1D task for first row. (because you need to make it null). Go down. Don't forget last row.

To minimize the number of bombs, we have to maximize effect of every bomb. To achive this, on every step we have to select the best target. For each point summing it and it’s eight neighbours – could be used as an efficiency quantity of bombing this point. This will provide close to optimal sequence of bombs.

UPD : We should also take number of zeros into account, becouse bombin them is inefficiently. In fact the problem is to minimize number of hitted zeros. But we can not know how any step gets us closer to this aim. I agree with idea that the problem is NP-complete. I sugest a greedy approach, which will give an answer close to real.

I believe that to minimize the amount of bombs you simply need maximize the amount of damage.. for that to happen need to check the area that has the strongest force.. so you first analyze the field with a 3×3 kernel and check where the sum is stronger.. and bomb there.. and do until the field is flat.. for this filed the answer is 28

 var oMasortingx = [ [2,3,4,7,1], [1,5,2,6,2], [4,3,4,2,1], [2,1,2,4,1], [3,1,3,4,1], [2,1,4,3,2], [6,9,1,6,4] ] var nBombs = 0; do { var bSpacesLeftToBomb = false; var nHigh = 0; var nCellX = 0; var nCellY = 0; for(var y = 1 ; ynHigh) { nHigh = nValue; nCellX = x; nCellY = y; } } if(nHigh>0) { nBombs++; for(var yy = nCellY-1;yy<=nCellY+1;yy++) { for(var xx = nCellX-1;xx<=nCellX+1;xx++) { if(oMatrix[yy][xx]<=0) continue; oMatrix[yy][xx] = --oMatrix[yy][xx]; } } bSpacesLeftToBomb = true; } } while(bSpacesLeftToBomb); alert(nBombs+'bombs'); 

Here is a solution that generalizes the good properties of the corners.

Let’s assume that we could find a perfect drop point for a given field, that is, a best way to decrease the value in it. Then to find the minimum number of bombs to be dropped, a first draft of an algorithm could be (the code is copy-pasted from a ruby implementation):

 dropped_bomb_count = 0 while there_are_cells_with_non_zero_count_left coordinates = choose_a_perfect_drop_point drop_bomb(coordinates) dropped_bomb_count += 1 end return dropped_bomb_count 

The challenge is choose_a_perfect_drop_point . First, let’s define what a perfect drop point is.

  • A drop point for (x, y) decreases the value in (x, y) . It may also decrease values in other cells.
  • A drop point a for (x, y) is better than a drop point b for (x, y) if it decreases the values in a proper superset of the cells that b decreases.
  • A drop point is maximal if there is no other better drop point.
  • Two drop points for (x, y) are equivalent if they decrease the same set of cells.
  • A drop point for (x, y) is perfect if it is equivalent to all maximal drop points for (x, y) .

If there is a perfect drop point for (x, y) , you cannot decrease the value at (x, y) more effectively than to drop a bomb on one of the perfect drop points for (x, y) .

A perfect drop point for a given field is a perfect drop point for any of its cells.

Here are few examples:

 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

The perfect drop point for the cell (0, 0) (zero-based index) is (1, 1) . All other drop points for (1, 1) , that is (0, 0) , (0, 1) , and (1, 0) , decrease less cells.

 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 

A perfect drop point for the cell (2, 2) (zero-based index) is (2, 2) , and also all the surrounding cells (1, 1) , (1, 2) , (1, 3) , (2, 1) , (2, 3) , (3, 1) , (3, 2) , and (3, 3) .

 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 

a perfect drop points for the cell (2, 2) is (3, 1) : It decreases the value in (2, 2) , and the value in (4, 0) . All other drop points for (2, 2) are not maximal, as they decrease one cell less. The perfect drop point for (2, 2) is also the perfect drop point for (4, 0) , and it is the only perfect drop point for the field. It leads to the perfect solution for this field (one bomb drop).

 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 

There is no perfect drop point for (2, 2) : Both (1, 1) and (1, 3) decrease (2, 2) and another cell (they are maximal drop points for (2, 2) ), but they are not equivalent. However, (1, 1) is a perfect drop point for (0, 0) , and (1, 3) is a perfect drop point for (0, 4) .

With that definition of perfect drop points and a certain order of checks, I get the following result for the example in the question:

 Drop bomb on 1, 1 Drop bomb on 1, 1 Drop bomb on 1, 5 Drop bomb on 1, 5 Drop bomb on 1, 5 Drop bomb on 1, 6 Drop bomb on 1, 2 Drop bomb on 1, 2 Drop bomb on 0, 6 Drop bomb on 0, 6 Drop bomb on 2, 1 Drop bomb on 2, 5 Drop bomb on 2, 5 Drop bomb on 2, 5 Drop bomb on 3, 1 Drop bomb on 3, 0 Drop bomb on 3, 0 Drop bomb on 3, 0 Drop bomb on 3, 0 Drop bomb on 3, 0 Drop bomb on 3, 4 Drop bomb on 3, 4 Drop bomb on 3, 3 Drop bomb on 3, 3 Drop bomb on 3, 6 Drop bomb on 3, 6 Drop bomb on 3, 6 Drop bomb on 4, 6 28 

However, the algorithm only works if there is at least one perfect drop point after each step. It is possible to construct examples where there are no perfect drop points:

 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 

For these cases, we can modify the algorithm so that instead of a perfect drop point, we choose a coordinate with a minimal choice of maximal drop points, then calculate the minimum for each choice. In the case above, all cells with values have two maximal drop points. For example, (0, 1) has the maximal drop points (1, 1) and (1, 2) . Choosing either one and then calcualting the minimum leads to this result:

 Drop bomb on 1, 1 Drop bomb on 2, 2 Drop bomb on 1, 2 Drop bomb on 2, 1 2 

Here’s another idea:

Let’s start by assigning a weight to each space on the board for how many numbers would be reduced by dropping a bomb there. So if the space has a non-zero number, it gets a point, and if any space adjacent to it has a non-zero number, it gets an additional point. So if there is a 1000-by-1000 grid, we have a weight assigned to each of the 1 million spaces.

Then sort the list of spaces by weight, and bomb the one with the highest weight. This is getting the most bang for our buck, so to speak.

After that, update the weight of every space whose weight is affected by the bomb. This will be the space you bombed, and any space immediately adjacent to it, and any space immediately adjacent to those. In other words, any space which could have had its value reduced to zero by the bombing, or the value of a neighboring space reduced to zero.

Then, re-sort the list spaces by weight. Since only a small subset of spaces had their weight changed by the bombing, you won’t need to resort the whole list, just move those ones around in the list.

Bomb the new highest weight space, and repeat the procedure.

This guarantees that every bombing reduces as many spaces as possible (basically, it hits as few spaces which are already zero as possible), so it would be optimal, except that their can be ties in weights. So you may need to do some back tracking when there is a tie for the top weight. Only a tie for the top weight matters, though, not other ties, so hopefully it’s not too much back-tracking.

Edit: Mysticial’s counterexample below demonstrates that in fact this isn’t guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn’t follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.

Mathematica Integer Linear Programming using branch-and-bound

As it has already been mentioned, this problem can be solved using integer linear programming (which is NP-Hard ). Mathematica already has ILP built in. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method." [see Constrained Optimization Tutorial in Mathematica.. ]

I’ve written the following code that utilizes ILP libraries of Mathematica. It is surprisingly fast.

 solveMasortingxBombProblem[problem_, r_, c_] := Module[{}, bombEffect[x_, y_, m_, n_] := Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}]; bombMasortingx[m_, n_] := Transpose[ Table[Table[ Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, m*n - 1}], {i, 0, m*n - 1}]]; X := x /@ Range[c*r]; sol = Minimize[{Total[X], And @@ Thread[bombMasortingx[r, c].X >= problem] && And @@ Thread[X >= 0] && Total[X] <= 10^100 && Element[X, Integers]}, X]; Print["Minimum required bombs = ", sol[[1]]]; Print["A possible solution = ", MatrixForm[ Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, c - 1}]]];] 

For the example provided in the problem:

 solveMasortingxBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5] 

Les sorties

entrer la description de l'image ici

For anyone reading this with a greedy algorithm

Try your code on the following 10x10 problem:

 5 20 7 1 9 8 19 16 11 3 17 8 15 17 12 4 5 16 8 18 4 19 12 11 9 7 4 15 14 6 17 20 4 9 19 8 17 2 10 8 3 9 10 13 8 9 12 12 6 18 16 16 2 10 7 12 17 11 4 15 11 1 15 1 5 11 3 12 8 3 7 11 16 19 17 11 20 2 5 19 5 18 2 17 7 14 19 11 1 6 13 20 8 4 15 10 19 5 11 12 

Here it is comma-seperated:

 5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12 

For this problem, my solution contains 208 bombs. Here's a possible solution (I was able to solve this in about 12 seconds).

entrer la description de l'image ici

As a way to test the results Mathematica is producing, see if your greedy algorithm can do any better.

Well, suppose we number the board positions 1, 2, …, nx m. Any sequence of bomb drops can be represented by a sequence of numbers in this set, where numbers can repeat. However, the effect on the board is the same regardless of what order you drop the bombs in, so really any choice of bomb drops can be represented as a list of nxm numbers, where the first number represents the number of bombs dropped on position 1, the second number represents the number of bombs dropped on position 2, etc. Let’s call this list of nxm numbers the “key”.

You could try first calculating all board states resulting from 1 bomb drop, then use these to calculate all board states resulting from 2 bomb drops, etc until you get all zeros. But at each step you would cache the states using the key I defined above, so you can use these results in calculating the next step (a “dynamic programming” approach).

But depending on the size of n, m, and the numbers in the grid, the memory requirements of this approach might be excessive. You can throw away all the results for N bomb drops once you’ve calculated all the results for N + 1, so there’s some savings there. And of course you could not cache anything at the cost of having it take a lot longer — the dynamic programming approach trades memory for speed.

If you want the absolute optimal solution to clean the board you will have to use classic backtracking, but if the masortingx is very big it will take ages to find the best solution, if you want an “possible” optimal solution you can use greedy algorithm, if you need help writing the algorithm i can help you

Come to think of it that is the best way. Make another masortingx there you store the points you remove by dropping a bomb there then chose the cell with maximum points and drop the bomb there update the points masortingx and continue. Exemple:

 2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3)) 1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4)) 1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2)) 

cell value +1 for every adjacent cell with a value higher than 0

Brute Force !

I know it is not efficient, but even if you find a faster algorithm, you can always test against this result to know how accurate it is.

Use some recursion, like this:

 void fn(tableState ts, currentlevel cl) { // first check if ts is all zeros yet, if not: // // do a for loop to go through all cells of ts, // for each cell do a bomb, and then // call: // fn(ts, cl + 1); } 

You can make this more efficient by caching, if different way lead to same result, you shouldn’t repeat the same steps.

Élaborer:

if bombing cell 1,3,5 leads to the same result as bombing cell 5,3,1 , then, you shouldn’t re-do all the next steps again for both cases, only 1 is enough, you should store somewhere all table states and use its results.

A hash of table stats can be used to do fast comparison.

  1. Never bomb border (unless square does not have nonborder neighbour)
  2. Zero corner.
  3. To zero corner, drop value of corner one square away diagonaly (the only nonborder neighbour)
  4. This will create new corners. Go to 2

Edit: did not notice that Kostek suggested almost same approach, so now I make stronger claim: If corners to clear are chosen to be always on outermost layer, then it is optimal.

In OP’s example: dropping 2 (as 1+1 or 2) on anything else than on 5 does not leads to hitting any square that dropping on 5 would hit. So we simply must drop 2 on 5 (and 6 on lower left 1 …)

After this, there is only one way how to clear (in top left) corner what was originaly 1 (now 0), and that is by dropping 0 on B3 (excel like notation). Etc.

Only after clearing whole A and E columns and 1 and 7 rows, start clearing one layer deeper.

Consider cleared only those intentionaly cleared, clearing 0 value corners costs nothing and simplifies thinking about it.

Because all bombs dropped this way must be dropped and this leads to cleared fields, it is optimal solution.


After good sleep I realized that this is not true. Considérer

  ABCDE 1 01000 2 10000 3 00000 4 00000 

My approach would drop bombs on B3 and C2, when dropping on B2 would be enough

Here’s my solution.. I won’t write it out in code yet since I don’t have time, but I believe this should produce an optimal number of moves each time – though I’m not sure how efficient it would be at finding the points to bomb.

Firstly, as @Luka Rahne stated in one of the comments, the order in which you bomb is not important- only the combination.

Secondly, as many others have stated, bombing 1-off the diagonal from the corners is optimal because it touches more points than the corners.

This generates the basis for my version of the algorithm: We can bomb the ‘1-off from the corners’ first or last, it doesn’t matter (in theory) We bomb those first because it makes later decisions easier (in practice) We bomb the point which affects the most points, while simultaneously bombing those corners.

Let’s define Points Of Resistance to be the points in the board with the most non-bombable points + largest number of 0’s around them

non-bombable points can be defined as points which don’t exist in our current scope of the board we’re looking at.

I’ll also define 4 bounds which will handle our scope: Top=0, Left=0, Bottom=k,right=j. (values to start)

Finally, I’ll define optimal bombs as bombs which are dropped on points that are adjacent to points of resistance and are touching (1) the highest valued point of resistance and (2) the largest number of points possible.

Regarding the approach- it’s obvious we’re working from the outside in. We will be able to work with 4 ‘bombers’ at the same time.

The first points of resistance are obviously our corners. The ‘out of bound’ points are not bombable (there are 5 points outside the scope for each corner). So we bomb the points diagonally one off the corners first.

Algorithme:

  1. Find the 4 optimal bomb points.
  2. If a bomb point is bombing a resistance point which is touching 2 bounds (ie a corner), bomb till that point is 0. Otherwise, bomb each until one of the points of resistance touching the optimal bomb point is 0.
  3. for each bound: if(sum(bound)==0) advance bound

repeat until TOP=BOTTOM and LEFT=RIGHT

I will try to write the actual code later

You could use state space planning. For example, using A* (or one of its variants) coupled with an heuristic f = g + h like this:

  • g: number of bombs dropped so far
  • h: sum over all values of the grid divided by 9 (which is the best result, meaning we have an admissible heuristics)

I got 28 moves as well. I used two tests for the best next move: first the move producing the minimum sum for the board. Second, for equal sums, the move producing the maximum density, defined as:

 number-of-zeros / number-of-groups-of-zeros 

This is Haskell. “solve board” shows the engine’s solution. You can play the game by typing “main”, then enter a target point, “best” for a recommendation, or “quit” to quit.

SORTIE:
*Main> solve board
[(4,4),(3,6),(3,3),(2,2),(2,2),(4,6),(4,6),(2,6),(3,2),(4,2),(2,6),(3,3),(4,3),(2,6),(4,2),(4,6),(4,6),(3,6),(2,6),(2,6),(2,4),(2,4),(2,6),(3,6),(4,2),(4,2),(4,2),(4,2)]

 import Data.List import Data.List.Split import Data.Ord import Data.Function(on) board = [2,3,4,7,1, 1,5,2,6,2, 4,3,4,2,1, 2,1,2,4,1, 3,1,3,4,1, 2,1,4,3,2, 6,9,1,6,4] n = 5 m = 7 updateBoard board pt = let x = fst pt y = snd pt precedingLines = replicate ((y-2) * n) 0 bomb = concat $ replicate (if y == 1 then 2 else min 3 (m+2-y)) (replicate (x-2) 0 ++ (if x == 1 then [1,1] else replicate (min 3 (n+2-x)) 1) ++ replicate (n-(x+1)) 0) in zipWith (\ab -> max 0 (ab)) board (precedingLines ++ bomb ++ repeat 0) showBoard board = let top = " " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n" chunks = chunksOf n board in putStrLn (top ++ showBoard' chunks "" 1) where showBoard' [] str count = str showBoard' (x:xs) str count = showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1) instances _ [] = 0 instances x (y:ys) | x == y = 1 + instances x ys | otherwise = instances x ys density a = let numZeros = instances 0 a groupsOfZeros = filter (\x -> head x == 0) (group a) in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros) boardDensity board = sum (map density (chunksOf n board)) moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]] bestMove board = let lowestSumMoves = take 1 $ groupBy ((==) `on` snd) $ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves)) in if null lowestSumMoves then (0,0) else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves) in fst $ head $ reverse $ sortBy (comparing snd) (map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves')) solve board = solve' board [] where solve' board result | sum board == 0 = result | otherwise = let best = bestMove board in solve' (updateBoard board best) (result ++ [best]) main :: IO () main = mainLoop board where mainLoop board = do putStrLn "" showBoard board putStr "Pt: " a <- getLine case a of "quit" -> do putStrLn "" return () "best" -> do putStrLn (show $ bestMove board) mainLoop board otherwise -> let ws = splitOn "," a pt = (read (head ws), read (last ws)) in do mainLoop (updateBoard board pt) 

There seems to be a nonbipartite matching substructure here. Consider the following instance:

 0010000 1000100 0000001 1000000 0000001 1000100 0010000 

The optimal solution to this case has size 5 since that’s the size of a minimum cover of the vertices of a 9-cycle by its edges.

This case, in particular, shows that the linear programming relaxation a few people have posted isn’t exact, doesn’t work, and all those other bad things. I’m pretty sure I can reduce “cover the vertices of my planar cubic graph by as few edges as possible” to your problem, which makes me doubt whether any of the greedy/hill-climbing solutions are going to work.

I don’t see a way to solve this in polynomial time in the worst case. There might be a very clever binary-search-and-DP solution that I’m not seeing.

EDIT : I see that the contest ( http://deadline24.pl ) is language-agnostic; they send you a bunch of input files and you send them outputs. So you don’t need something that runs in worst-case polynomial time. In particular, you get to look at the input !

There are a bunch of small cases in the input. Then there’s a 10×1000 case, a 100×100 case, and a 1000×1000 case. The three large cases are all very well-behaved. Horizontally adjacent ensortinges typically have the same value. On a relatively beefy machine, I’m able to solve all of the cases by brute-forcing using CPLEX in just a couple of minutes. I got lucky on the 1000×1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.

I’d bet you can use the structure of the input in a much more direct way than I did if you took a look at it; seems like you can just pare off the first row, or two, or three repeatedly until you’ve got nothing left. (Looks like, in the 1000×1000, all of the rows are nonincreasing? I guess that’s where your “part B” comes from? )

I can’t think of a way to calculate the actual number without just computing the bombing campaign using my best heuristic and hope I get a reasonable result.

So my method is to compute a bombing efficiency mesortingc for each cell, bomb the cell with the highest value, …. iterate the process until I’ve flattened everything. Some have advocated using simple potential damage (ie score from 0 to 9) as a mesortingc, but that falls short by pounding high value cells and not making use of damage overlap. I’d calculate cell value - sum of all neighbouring cells , reset any positive to 0 and use the absolute value of anything negative. Intuitively this mesortingc should make a selection that help maximise damage overlap on cells with high counts instead of pounding those directly.

The code below reaches total destruction of the test field in 28 bombs (note that using potential damage as mesortingc yields 31!).

 using System; using System.Collections.Generic; using System.Linq; namespace StackOverflow { internal class Program { // store the battle field as flat array + dimensions private static int _width = 5; private static int _length = 7; private static int[] _field = new int[] { 2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4 }; // this will store the devastation mesortingc private static int[] _mesortingc; // do the work private static void Main(ssortingng[] args) { int count = 0; while (_field.Sum() > 0) { Console.Out.WriteLine("Round {0}:", ++count); GetBlastPotential(); int cell_to_bomb = FindBestBombingSite(); PrintField(cell_to_bomb); Bomb(cell_to_bomb); } Console.Out.WriteLine("Done in {0} rounds", count); } // convert 2D position to 1D index private static int Get1DCoord(int x, int y) { if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1; else { return (y * _width) + x; } } // Convert 1D index to 2D position private static void Get2DCoord(int n, out int x, out int y) { if ((n < 0) || (n >= _field.Length)) { x = -1; y = -1; } else { x = n % _width; y = n / _width; } } // Compute a list of 1D indices for a cell neighbours private static List GetNeighbours(int cell) { List neighbours = new List(); int x, y; Get2DCoord(cell, out x, out y); if ((x >= 0) && (y >= 0)) { List tmp = new List(); tmp.Add(Get1DCoord(x - 1, y - 1)); tmp.Add(Get1DCoord(x - 1, y)); tmp.Add(Get1DCoord(x - 1, y + 1)); tmp.Add(Get1DCoord(x, y - 1)); tmp.Add(Get1DCoord(x, y + 1)); tmp.Add(Get1DCoord(x + 1, y - 1)); tmp.Add(Get1DCoord(x + 1, y)); tmp.Add(Get1DCoord(x + 1, y + 1)); // eliminate invalid coords - ie stuff past the edges foreach (int c in tmp) if (c >= 0) neighbours.Add(c); } return neighbours; } // Compute the devastation mesortingc for each cell // Represent the Value of the cell minus the sum of all its neighbours private static void GetBlastPotential() { _mesortingc = new int[_field.Length]; for (int i = 0; i < _field.Length; i++) { _metric[i] = _field[i]; List neighbours = GetNeighbours(i); if (neighbours != null) { foreach (int j in neighbours) _mesortingc[i] -= _field[j]; } } for (int i = 0; i < _metric.Length; i++) { _metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0; } } //// Compute the simple expected damage a bomb would score //private static void GetBlastPotential() //{ // _metric = new int[_field.Length]; // for (int i = 0; i < _field.Length; i++) // { // _metric[i] = (_field[i] > 0) ? 1 : 0; // List neighbours = GetNeighbours(i); // if (neighbours != null) // { // foreach (int j in neighbours) _mesortingc[i] += (_field[j] > 0) ? 1 : 0; // } // } //} // Update the battle field upon dropping a bomb private static void Bomb(int cell) { List neighbours = GetNeighbours(cell); foreach (int i in neighbours) { if (_field[i] > 0) _field[i]--; } } // Find the best bombing site - just return index of local maxima private static int FindBestBombingSite() { int max_idx = 0; int max_val = int.MinValue; for (int i = 0; i < _metric.Length; i++) { if (_metric[i] > max_val) { max_val = _mesortingc[i]; max_idx = i; } } return max_idx; } // Display the battle field on the console private static void PrintField(int cell) { for (int x = 0; x < _width; x++) { for (int y = 0; y < _length; y++) { int c = Get1DCoord(x, y); if (c == cell) Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4)); else Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4)); } Console.Out.Write(" || "); for (int y = 0; y < _length; y++) { int c = Get1DCoord(x, y); if (c == cell) Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4)); else Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4)); } Console.Out.WriteLine(); } Console.Out.WriteLine(); } } } 

The resulting bombing pattern is output as follows (field values on the left, mesortingc on the right)

 Round 1: 2 1 4 2 3 2 6 || 7 16 8 10 4 18 6 3 5 3 1 1 1 9 || 11 18 18 21 17 28 5 4 [2] 4 2 3 4 1 || 19 [32] 21 20 17 24 22 7 6 2 4 4 3 6 || 8 17 20 14 16 22 8 1 2 1 1 1 2 4 || 14 15 14 11 13 16 7 Round 2: 2 1 4 2 3 2 6 || 5 13 6 9 4 18 6 2 4 2 1 1 [1] 9 || 10 15 17 19 17 [28] 5 3 2 3 2 3 4 1 || 16 24 18 17 17 24 22 6 5 1 4 4 3 6 || 7 14 19 12 16 22 8 1 2 1 1 1 2 4 || 12 12 12 10 13 16 7 Round 3: 2 1 4 2 2 1 5 || 5 13 6 7 3 15 5 2 4 2 1 0 1 8 || 10 15 17 16 14 20 2 3 [2] 3 2 2 3 0 || 16 [24] 18 15 16 21 21 6 5 1 4 4 3 6 || 7 14 19 11 14 19 6 1 2 1 1 1 2 4 || 12 12 12 10 13 16 7 Round 4: 2 1 4 2 2 1 5 || 3 10 4 6 3 15 5 1 3 1 1 0 1 8 || 9 12 16 14 14 20 2 2 2 2 2 2 [3] 0 || 13 16 15 12 16 [21] 21 5 4 0 4 4 3 6 || 6 11 18 9 14 19 6 1 2 1 1 1 2 4 || 10 9 10 9 13 16 7 Round 5: 2 1 4 2 2 1 5 || 3 10 4 6 2 13 3 1 3 1 1 0 [0] 7 || 9 12 16 13 12 [19] 2 2 2 2 2 1 3 0 || 13 16 15 10 14 15 17 5 4 0 4 3 2 5 || 6 11 18 7 13 17 6 1 2 1 1 1 2 4 || 10 9 10 8 11 13 5 Round 6: 2 1 4 2 1 0 4 || 3 10 4 5 2 11 2 1 3 1 1 0 0 6 || 9 12 16 11 8 13 0 2 2 2 2 0 2 0 || 13 16 15 9 14 14 15 5 4 [0] 4 3 2 5 || 6 11 [18] 6 11 15 5 1 2 1 1 1 2 4 || 10 9 10 8 11 13 5 Round 7: 2 1 4 2 1 0 4 || 3 10 4 5 2 11 2 1 3 1 1 0 0 6 || 8 10 13 9 7 13 0 2 [1] 1 1 0 2 0 || 11 [15] 12 8 12 14 15 5 3 0 3 3 2 5 || 3 8 10 3 8 15 5 1 1 0 0 1 2 4 || 8 8 7 7 9 13 5 Round 8: 2 1 4 2 1 0 4 || 1 7 2 4 2 11 2 0 2 0 1 0 0 6 || 7 7 12 7 7 13 0 1 1 0 1 0 2 0 || 8 8 10 6 12 14 15 4 2 0 3 3 [2] 5 || 2 6 8 2 8 [15] 5 1 1 0 0 1 2 4 || 6 6 6 7 9 13 5 Round 9: 2 1 4 2 1 0 4 || 1 7 2 4 2 11 2 0 2 0 1 0 0 6 || 7 7 12 7 6 12 0 1 1 0 1 0 [1] 0 || 8 8 10 5 10 [13] 13 4 2 0 3 2 2 4 || 2 6 8 0 6 9 3 1 1 0 0 0 1 3 || 6 6 6 5 8 10 4 Round 10: 2 1 4 2 1 0 4 || 1 7 2 4 2 10 1 0 2 [0] 1 0 0 5 || 7 7 [12] 7 6 11 0 1 1 0 1 0 1 0 || 8 8 10 4 8 9 10 4 2 0 3 1 1 3 || 2 6 8 0 6 8 3 1 1 0 0 0 1 3 || 6 6 6 4 6 7 2 Round 11: 2 0 3 1 1 0 4 || 0 6 0 3 0 10 1 0 1 0 0 0 [0] 5 || 4 5 5 5 3 [11] 0 1 0 0 0 0 1 0 || 6 8 6 4 6 9 10 4 2 0 3 1 1 3 || 1 5 6 0 5 8 3 1 1 0 0 0 1 3 || 6 6 6 4 6 7 2 Round 12: 2 0 3 1 0 0 3 || 0 6 0 2 1 7 1 0 1 0 0 0 0 4 || 4 5 5 4 1 7 0 1 0 0 0 0 [0] 0 || 6 8 6 4 5 [9] 8 4 2 0 3 1 1 3 || 1 5 6 0 4 7 2 1 1 0 0 0 1 3 || 6 6 6 4 6 7 2 Round 13: 2 0 3 1 0 0 3 || 0 6 0 2 1 6 0 0 1 0 0 0 0 3 || 4 5 5 4 1 6 0 1 [0] 0 0 0 0 0 || 6 [8] 6 3 3 5 5 4 2 0 3 0 0 2 || 1 5 6 0 4 6 2 1 1 0 0 0 1 3 || 6 6 6 3 4 4 0 Round 14: 2 0 3 1 0 [0] 3 || 0 5 0 2 1 [6] 0 0 0 0 0 0 0 3 || 2 5 4 4 1 6 0 0 0 0 0 0 0 0 || 4 4 4 3 3 5 5 3 1 0 3 0 0 2 || 0 4 5 0 4 6 2 1 1 0 0 0 1 3 || 4 4 5 3 4 4 0 Round 15: 2 0 3 1 0 0 2 || 0 5 0 2 1 4 0 0 0 0 0 0 0 2 || 2 5 4 4 1 4 0 0 0 0 0 0 0 0 || 4 4 4 3 3 4 4 3 1 0 3 0 [0] 2 || 0 4 5 0 4 [6] 2 1 1 0 0 0 1 3 || 4 4 5 3 4 4 0 Round 16: 2 [0] 3 1 0 0 2 || 0 [5] 0 2 1 4 0 0 0 0 0 0 0 2 || 2 5 4 4 1 4 0 0 0 0 0 0 0 0 || 4 4 4 3 3 3 3 3 1 0 3 0 0 1 || 0 4 5 0 3 3 1 1 1 0 0 0 0 2 || 4 4 5 3 3 3 0 Round 17: 1 0 2 1 0 0 2 || 0 3 0 1 1 4 0 0 0 0 0 0 0 2 || 1 3 3 3 1 4 0 0 0 0 0 0 0 0 || 4 4 4 3 3 3 3 3 1 [0] 3 0 0 1 || 0 4 [5] 0 3 3 1 1 1 0 0 0 0 2 || 4 4 5 3 3 3 0 Round 18: 1 0 2 1 0 0 2 || 0 3 0 1 1 4 0 0 0 0 0 0 0 2 || 1 3 3 3 1 4 0 0 0 0 0 0 0 0 || 3 3 2 2 2 3 3 3 [0] 0 2 0 0 1 || 0 [4] 2 0 2 3 1 1 0 0 0 0 0 2 || 2 4 2 2 2 3 0 Round 19: 1 0 2 1 0 [0] 2 || 0 3 0 1 1 [4] 0 0 0 0 0 0 0 2 || 1 3 3 3 1 4 0 0 0 0 0 0 0 0 || 2 2 2 2 2 3 3 2 0 0 2 0 0 1 || 0 2 2 0 2 3 1 0 0 0 0 0 0 2 || 2 2 2 2 2 3 0 Round 20: 1 [0] 2 1 0 0 1 || 0 [3] 0 1 1 2 0 0 0 0 0 0 0 1 || 1 3 3 3 1 2 0 0 0 0 0 0 0 0 || 2 2 2 2 2 2 2 2 0 0 2 0 0 1 || 0 2 2 0 2 3 1 0 0 0 0 0 0 2 || 2 2 2 2 2 3 0 Round 21: 0 0 1 1 0 0 1 || 0 1 0 0 1 2 0 0 0 0 0 0 0 1 || 0 1 2 2 1 2 0 0 0 0 0 0 0 0 || 2 2 2 2 2 2 2 2 0 0 2 0 [0] 1 || 0 2 2 0 2 [3] 1 0 0 0 0 0 0 2 || 2 2 2 2 2 3 0 Round 22: 0 0 1 1 0 0 1 || 0 1 0 0 1 2 0 0 0 0 0 0 0 1 || 0 1 2 2 1 2 0 [0] 0 0 0 0 0 0 || [2] 2 2 2 2 1 1 2 0 0 2 0 0 0 || 0 2 2 0 2 1 1 0 0 0 0 0 0 1 || 2 2 2 2 2 1 0 Round 23: 0 0 1 1 0 0 1 || 0 1 0 0 1 2 0 0 0 [0] 0 0 0 1 || 0 1 [2] 2 1 2 0 0 0 0 0 0 0 0 || 1 1 2 2 2 1 1 1 0 0 2 0 0 0 || 0 1 2 0 2 1 1 0 0 0 0 0 0 1 || 1 1 2 2 2 1 0 Round 24: 0 0 0 0 0 0 1 || 0 0 0 0 0 2 0 0 0 0 0 0 0 1 || 0 0 0 0 0 2 0 0 0 [0] 0 0 0 0 || 1 1 [2] 2 2 1 1 1 0 0 2 0 0 0 || 0 1 2 0 2 1 1 0 0 0 0 0 0 1 || 1 1 2 2 2 1 0 Round 25: 0 0 0 0 0 [0] 1 || 0 0 0 0 0 [2] 0 0 0 0 0 0 0 1 || 0 0 0 0 0 2 0 0 0 0 0 0 0 0 || 1 1 1 1 1 1 1 1 0 0 1 0 0 0 || 0 1 1 0 1 1 1 0 0 0 0 0 0 1 || 1 1 1 1 1 1 0 Round 26: 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 [0] 0 0 0 0 0 0 || [1] 1 1 1 1 0 0 1 0 0 1 0 0 0 || 0 1 1 0 1 1 1 0 0 0 0 0 0 1 || 1 1 1 1 1 1 0 Round 27: 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 [0] 0 0 0 0 || 0 0 [1] 1 1 0 0 0 0 0 1 0 0 0 || 0 0 1 0 1 1 1 0 0 0 0 0 0 1 || 0 0 1 1 1 1 0 Round 28: 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 0 0 0 0 0 || 0 0 0 0 0 0 0 0 0 0 0 0 [0] 0 || 0 0 0 0 0 [1] 1 0 0 0 0 0 0 1 || 0 0 0 0 0 1 0 Done in 28 rounds 

This can be solved using a tree of depth O(3^(n)). Where n is the sum of all of the squares.

First consider that it is sortingvial to solve the problem with a tree of O(9^n), simply consider all of the possible bombing locations. For an example see Alfe’s implementation .

Next realize that we can work to bomb from the bottom up and still get a minimum bombing pattern.

  1. Start from the bottom left corner.
  2. Bomb it to oblivion with the only plays that make sense (up and to the right).
  3. Move one square to the right.
  4. While the target has a value greater than zero, consider each of the 2 plays that make sense (straight up or up and to the right), reduce the value of the target by one, and make a new branch for each possibility.
  5. Move another to the right.
  6. While the target has a value greater than zero, consider each of the 3 plays that make sense (up left, up, and up right), reduce the value of the target by one, and make a new branch for each possibility.
  7. Repeat steps 5 and 6 until the row is eliminated.
  8. Move up a row and repeat steps 1 to 7 until the puzzle is solved.

This algorithm is correct because

  1. It is necessary to complete each row at some point.
  2. Completing a row always requires a play either one above, one below, or within that row.
  3. It is always as good or better to choose a play one above the lowest uncleared row than a play on the row or below the row.

In practice this algorithm will regularly do better than its theoretical maximum because it will regularly bomb out neighbors and reduce the size of the search. If we assume that each bombing decreases the value of 4 additional targets, then our algorithm will run in O(3^(n/4)) or approximately O(1.3^n).

Because this algorithm is still exponential, it would be wise to limit the depth of the search. We might limit the number of twigs allowed to some number, X, and once we are this deep we force the algorithm to choose the best path it has identified so far (the one that has the minimum total board sum in one of its terminal leaves). Then our algorithm is guaranteed to run in O(3^X) time, but it is not guaranteed to get the correct answer. However, we can always increase X and test empirically if the trade off between increased computation and better answers is worthwhile.

evaluation function, total sum:

 int f (int ** masortingx, int width, int height, int x, int y) { int m[3][3] = { 0 }; m[1][1] = masortingx[x][y]; if (x > 0) m[0][1] = masortingx[x-1][y]; if (x < width-1) m[2][1] = matrix[x+1][y]; if (y > 0) { m[1][0] = masortingx[x][y-1]; if (x > 0) m[0][0] = masortingx[x-1][y-1]; if (x < width-1) m[2][0] = matrix[x+1][y-1]; } if (y < height-1) { m[1][2] = matrix[x][y+1]; if (x > 0) m[0][2] = masortingx[x-1][y+1]; if (x < width-1) m[2][2] = matrix[x+1][y+1]; } return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2]; } 

objective function:

 Point bestState (int ** masortingx, int width, int height) { Point p = new Point(0,0); int bestScore = 0; int b = 0; for (int i=0; i bestScore) { bestScore = best; p = new Point(i,j); } } retunr p; } 

destroy function:

 void destroy (int ** masortingx, int width, int height, Point p) { int x = px; int y = py; if(masortingx[x][y] > 0) masortingx[x][y]--; if (x > 0) if(masortingx[x-1][y] > 0) masortingx[x-1][y]--; if (x < width-1) if(matrix[x+1][y] > 0) masortingx[x+1][y]--; if (y > 0) { if(masortingx[x][y-1] > 0) masortingx[x][y-1]--; if (x > 0) if(masortingx[x-1][y-1] > 0) masortingx[x-1][y-1]--; if (x < width-1) if(matrix[x+1][y-1] > 0) masortingx[x+1][y-1]--; } if (y < height-1) { if(matrix[x][y] > 0) masortingx[x][y+1]--; if (x > 0) if(masortingx[x-1][y+1] > 0) masortingx[x-1][y+1]--; if (x < width-1) if(matrix[x+1][y+1] > 0) masortingx[x+1][y+1]--; } } 

goal function:

 bool isGoal (int ** masortingx, int width, int height) { for (int i=0; i 0) return false; return true; } 

linear maximization function:

 void solve (int ** masortingx, int width, int height) { while (!isGoal(masortingx,width,height)) { destroy(masortingx,width,height, bestState(masortingx,width,height)); } } 

This is not optimal, but can be optimized through finding a better evaluation function ..

.. but thinking about this problem, I was thinking that one of the main issues is getting abandoned figures in the middle of zeroes at some point, so I'd take another approach .. which is dominate minimal values into zero, then try to escape zeroes as possible, which lead to general minimization of minimal existing value(s) or so

All this problem boils down to is computing an edit distance. Simply calculate a variant of the Levenshtein distance between the given masortingx and the zero masortingx, where edits are replaced with bombings, using dynamic programming to store the distances between intermediate arrays. I suggest using a hash of the masortingces as a key. In pseudo-Python:

 memo = {} def bomb(masortingx,i,j): # bomb masortingx at i,j def bombsRequired(masortingx,i,j): # bombs required to zero masortingx[i,j] def distance(m1, i, len1, m2, j, len2): key = hash(m1) if memo[key] != None: return memo[key] if len1 == 0: return len2 if len2 == 0: return len1 cost = 0 if m1 != m2: cost = m1[i,j] m = bomb(m1,i,j) dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost) memo[key] = dist return dist 

This was an answer to the first asked question. I hadn’t noticed that he changed the parameters.

Create a list of all targets. Assign a value to the target based on the number of positive values impacted by a drop (itself, and all neighbors). Highest value would be a nine.

Sort the targets by the number of targets impacted (Descending), with a secondary descending sort on the sum of each impacted target.

Drop a bomb on the highest ranked target, then re-calculate targets and repeat until all target values are zero.

Agreed, this is not always the most optimal. Par exemple,

 100011 011100 011100 011100 000000 100011 

This approach would take 5 bombs to clear. Optimally, though, you could do it in 4. Still, pretty darn close and there is no backtracking. For most situations it will be optimal, or very close.

Using the original problem numbers, this approach solves in 28 bombs.

Adding code to demonstrate this approach (using a form with a button):

  private void button1_Click(object sender, EventArgs e) { int[,] masortingx = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3}, {17, 8, 15, 17, 12, 4, 5, 16, 8, 18}, { 4, 19, 12, 11, 9, 7, 4, 15, 14, 6}, { 17, 20, 4, 9, 19, 8, 17, 2, 10, 8}, { 3, 9, 10, 13, 8, 9, 12, 12, 6, 18}, {16, 16, 2, 10, 7, 12, 17, 11, 4, 15}, { 11, 1, 15, 1, 5, 11, 3, 12, 8, 3}, { 7, 11, 16, 19, 17, 11, 20, 2, 5, 19}, { 5, 18, 2, 17, 7, 14, 19, 11, 1, 6}, { 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}}; int value = 0; List Targets = GetTargets(masortingx); while (Targets.Count > 0) { BombTarget(ref masortingx, Targets[0]); value += 1; Targets = GetTargets(masortingx); } Console.WriteLine( value); MessageBox.Show("done: " + value); } private static void BombTarget(ref int[,] masortingx, Target t) { for (int a = tx - 1; a <= tx + 1; a++) { for (int b = ty - 1; b <= ty + 1; b++) { if (a >= 0 && a <= matrix.GetUpperBound(0)) { if (b >= 0 && b <= matrix.GetUpperBound(1)) { if (matrix[a, b] > 0) { masortingx[a, b] -= 1; } } } } } Console.WriteLine("Dropped bomb on " + tx + "," + ty); } private static List GetTargets(int[,] masortingx) { List Targets = new List(); int width = masortingx.GetUpperBound(0); int height = masortingx.GetUpperBound(1); for (int x = 0; x <= width; x++) { for (int y = 0; y <= height; y++) { Target t = new Target(); tx = x; ty = y; SetTargetValue(matrix, ref t); if (t.value > 0) Targets.Add(t); } } Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList(); return Targets; } private static void SetTargetValue(int[,] masortingx, ref Target t) { for (int a = tx - 1; a <= tx + 1; a++) { for (int b = ty - 1; b <= ty + 1; b++) { if (a >= 0 && a <= matrix.GetUpperBound(0)) { if (b >= 0 && b <= matrix.GetUpperBound(1)) { if (matrix[ a, b] > 0) { t.value += 1; t.sum += masortingx[a,b]; } } } } } } 

A class you will need:

  class Target { public int value; public int sum; public int x; public int y; }