我也有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)

对于更新后的问题，简单的贪心算法可以得到最优结果。

向单元格A[1,1]投掷A[0,0]炸弹，然后向单元格A[2,1]投掷A[1,0]炸弹，并继续向下此过程。要清除左下角，向单元格A[n -2,1]投掷max(A[n -1,0]， A[n -2,0]， A[n -3,0])炸弹。这将完全清除前3列。

用同样的方法清除第3、4、5列，然后是第6、7、8列，等等。

不幸的是，这并不能帮助找到最初问题的解决方案。

“更大”的问题(没有“非增加”约束)可能被证明是np困难的。这是证明的草图。

假设我们有一个度为3的平面图形。我们来求这个图的最小顶点覆盖。根据维基百科的文章，这个问题对于3次以下的平面图形是np困难的。这可以通过平面3SAT的简化来证明。平面3SAT的硬度由3SAT降低而成。这两个证明都在Erik Demaine教授最近的“算法下界”讲座(第7和第9讲)中提出。

如果我们分割原始图的一些边(图中左边的图)，每条边都有偶数个额外的节点，结果图(图中右边的图)应该对原始顶点具有完全相同的最小顶点覆盖。这样的转换允许将图顶点对齐到网格上的任意位置。

如果我们将图顶点只放置在偶数行和列上(这样就不会有两条边与一个顶点形成锐角)，在有边的地方插入“1”，在其他网格位置插入“0”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。

你的新问题，有跨行不递减的值，很容易解决。

Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.

现在，一旦左边的列归零，我们只要剪掉最左边的三列现在归零，然后对现在化简的矩阵重复这一步骤。这必须给我们一个最优的解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。

Well, suppose we number the board positions 1, 2, ..., n x 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 n x m 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 n x m numbers the "key".

你可以试着先计算1个炸弹投下的所有板子状态，然后用这些来计算2个炸弹投下的所有板子状态，等等，直到你得到所有的0。但是在每一步中，您都将使用上面定义的键缓存状态，因此您可以在计算下一步时使用这些结果(一种“动态规划”方法)。

但是根据n、m的大小和网格中的数字，这种方法的内存需求可能会过多。一旦你计算了N + 1的所有结果，你就可以抛弃N个炸弹投掷的所有结果，所以这里有一些节省。当然，您不能以花费更长的时间为代价缓存任何东西——动态编程方法以内存换取速度。

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

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

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 X m的“score”矩阵，其中score[i][j]是如果位置(i,j)被炸毁，则矩阵中各点的总扣除额。(一个点的最高分数是9分，最低分数是0分) 逐行移动，找到并选择第一个得分最高的位置(例如(i,j))。 炸弹(i, j)。增加炸弹数量。 如果原矩阵的所有元素都不为零，则转到1。

但我怀疑这是否是最佳解决方案。

编辑:

我上面提到的贪心方法，虽然有效，但很可能不能给我们最优的解决方案。所以我想应该添加一些DP的元素。

我想我们可以同意，在任何时候，具有最高“分数”(分数[I][j] =总扣分，如果(I,j)被炸)的位置之一必须被瞄准。从这个假设开始，下面是新的方法:

NumOfBombs(M):(返回所需的最小炸弹数量)

给定一个矩阵M (n X M)，如果M中的所有元素都为0，则返回0。 计算“分数”矩阵M。 设k个不同的位置P1 P2…Pk (1 <= k <= n*m)，为m中得分最高的位置。 return (1 + min(NumOfBombs(M1)， NumOfBombs(M2)，…， NumOfBombs(Mk)) M1, M2,……，Mk是我们轰炸位置P1, P2，…， Pk。

此外，如果我们想在此基础上破坏位置的顺序，我们必须跟踪“min”的结果。