我也有28招。我使用了两个测试来确定最佳下一步:第一个是产生最小棋盘和的一步。其次，对于相等的和，产生最大密度的移动，定义为:

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

我是哈斯克尔。“解决板”显示引擎的解决方案。你可以通过输入“main”来玩游戏，然后输入目标点，“best”作为推荐，或者“quit”退出。

输出: *主>解决板 [(4, 4),(3、6),(3),(2,2),(2,2),(4、6)(4、6),(2,6),(2),(4,2)(2,6),(3),(4,3)(2,6)(4,2)(4、6)(4、6),(3、6),(2,6)(2,6)(2、4)(2、4)(2,6),(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 (\a b -> max 0 (a-b)) 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)

有一种方法可以把这个问题简化为一个简单的子问题。

解释分为两部分，算法和算法的原因 提供最优解决方案。没有第二个，第一个就说不通了，所以我 从为什么开始。

如果你想轰炸矩形(假设一个大矩形-还没有边缘情况) 你可以看到，只有这样才能减少空心矩形上的正方形 周长到0的意思是炸毁周长或者炸毁的空心矩形 就在外围的方块里。我称周长为图层1，其中的矩形为图层2。

一个重要的观点是，没有点轰炸层1，因为 你这样做得到的“爆炸半径”总是包含在爆炸半径内 另一个来自第2层的正方形。你应该很容易就能说服自己。

所以，我们可以把问题简化为找到一个最优的方法来炸开周长，然后我们可以重复这个过程，直到所有的平方都为0。

但当然了，如果有爆炸的可能，并不总能找到最优解 以一种不太理想的方式远离周边，但通过使用X个额外的炸弹制造 用>X炸弹减少内层的问题。如果我们调用 第一层，如果我们在第二层的某个地方放置一个额外的X炸弹(只是 在第1层内，我们可以减少之后轰炸第2层的努力吗 X ?换句话说，我们必须证明我们可以贪心化简外部 周长。

但是，我们知道我们可以贪婪。因为第2层的炸弹永远不会更多 有效减少第2层到0比战略上放置炸弹在第3层。和 因为和之前一样的原因-总有一个炸弹我们可以放在第3层 将影响第2层的每一个方块，炸弹放在第2层可以。所以，它可以 永远不要伤害我们的贪婪(在这个意义上的贪婪)。

所以，我们要做的就是找到最优的方法，通过轰炸将许可值降为0 下一个内层。

我们永远不会因为先把角落炸到0而受伤，因为只有内层的角落可以到达，所以我们真的没有选择(并且，任何可以到达角落的周长炸弹的爆炸半径都包含在内层角落的爆炸半径中)。

一旦我们这样做了，与0角相邻的周长上的正方形只能由内层的2个正方形到达:

0       A       B

C       X       Y

D       Z

在这一点上，周长实际上是一个封闭的1维环，因为任何炸弹都会减少3个相邻的正方形。除了角落附近的一些奇怪之处——X可以“击中”A、B、C和D。

Now we can't use any blast radius tricks - the situation of each square is symmetric, except for the weird corners, and even there no blast radius is a subset of another. Note that if this were a line (as Colonel Panic discusses) instead of a closed loop the solution is trivial. The end points must be reduced to 0, and it never harms you to bomb the points adjacent to the end points, again because the blast radius is a superset. Once you have made your endpoint 0, you still have a new endpoint, so repeat (until the line is all 0).

所以，如果我们可以优化地将层中的单个正方形减少到0，我们就有了一个算法(因为我们已经切断了循环，现在有了一条带有端点的直线)。我相信轰炸与最小值相邻的正方形(给你2个选项)，这样在最小值的2个正方形内的最大值就是最小值(你可能不得不分割你的轰炸来管理这一点)将是最优的，但我还没有证明。

如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你

现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:

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))

对于每个相邻的高于0的单元格，单元格值+1

生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。

创建N次应用bomp的函数 为所有炸弹放置/炸弹计数可能性创建循环(当矩阵==0时停止) 记住最好的解决方案。 在循环的最后，你得到了最好的解决方案 不仅是炸弹的数量，还有它们的位置

代码可以是这样的:

void copy(int **A,int **B,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
       A[i][j]=B[i][j];
    }

bool is_zero(int **M,int m,int n)
    {
    for (int i=0;i<m;i++)
     for (int j=0;i<n;j++)
      if (M[i][j]) return 0;
    return 1;
    }

void drop_bomb(int **M,int m,int n,int i,int j,int N)
    {
    int ii,jj;
    ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i  ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j  ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
    }

void solve_problem(int **M,int m,int n)
    {
    int i,j,k,max=0;
    // you probably will need to allocate matrices P,TP,TM yourself instead of this:
    int P[m][n],min;             // solution: placement,min bomb count
    int TM[m][n],TP[m][n],cnt;   // temp
    for (i=0;i<m;i++)            // max count of bomb necessary to test
     for (j=0;j<n;j++)
      if (max<M[i][j]) max=M[i][j];
    for (i=0;i<m;i++)            // reset solution
     for (j=0;j<n;j++)
      P[i][j]=max;
    min=m*n*max; 
        copy(TP,P,m,n); cnt=min;

    for (;;)  // generate all possibilities
        {
        copy(TM,M,m,n);
        for (i=0;i<m;i++)   // test solution
         for (j=0;j<n;j++)
          drop_bomb(TM,m,n,TP[i][j]);
        if (is_zero(TM,m,n))// is solution
         if (min>cnt)       // is better solution -> store it
            {
            copy(P,TP,m,n); 
            min=cnt;    
            }
        // go to next possibility
        for (i=0,j=0;;)
            {
            TP[i][j]--;
            if (TP[i][j]>=0) break;
            TP[i][j]=max;
                 i++; if (i<m) break;
            i=0; j++; if (j<n) break;
            break;
            }
        if (is_zero(TP,m,n)) break;
        }
    //result is in P,min
    }

这可以通过很多方式进行优化，……最简单的是用M矩阵重置解，但你需要改变最大值和TP[][]递减代码

这可以用深度为O(3^(n))的树来求解。其中n是所有平方和。

首先考虑用O(9^n)树来解决问题是很简单的，只需考虑所有可能的爆炸位置。有关示例，请参阅Alfe的实现。

接下来我们意识到，我们可以从下往上轰炸，仍然得到一个最小的轰炸模式。

Start from the bottom left corner. Bomb it to oblivion with the only plays that make sense (up and to the right). Move one square to the right. 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. Move another to the right. 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. Repeat steps 5 and 6 until the row is eliminated. Move up a row and repeat steps 1 to 7 until the puzzle is solved.

这个算法是正确的，因为

有必要在某一时刻完成每一行。 完成一行总是需要一个游戏，一个在上面，一个在下面，或者在这一行内。 选择在未清除的最低行之上的玩法总是比选择在该行之上或该行之下的玩法更好。

在实践中，这个算法通常会比它的理论最大值做得更好，因为它会定期轰炸邻居并减少搜索的大小。如果我们假设每次轰炸都会减少4个额外目标的价值，那么我们的算法将运行在O(3^(n/4))或大约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 branches 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.

为了尽量减少炸弹的数量，我们必须最大化每个炸弹的效果。要做到这一点，每一步我们都要选择最好的目标。对于每一个点，它和它的八个邻居的总和，可以被用作轰炸这一点的效率量。这将提供接近最佳的炸弹序列。

UPD:我们还应该考虑到零的数量，因为轰炸它们效率很低。事实上，问题是最小化击中零的数量。但我们不知道每一步如何使我们更接近这个目标。我同意这个问题是np完全的。我建议用贪婪的方法，它会给出一个接近真实的答案。