扫雷算法解决方案

Question

这是一个关于 this codefight callenge 的问题。

要求参赛者检查以二维数组表示的扫雷场是否有效。

详情：扫雷游戏板的每个单元格可以是：

一个地雷（显示为 9）
或代表其周围单元格中地雷数量的数字（当该单元格在至少一个角上与该单元格相遇时，该单元格被视为围绕另一个单元格）（显示为 0 - 8）

我的方法（有效）：

遍历所有项目
检查邻居是否有地雷（并计算地雷的数量，如果有的话）
将找到的地雷数量与图块上的数量进行比较
return false，如果数字不相等，否则继续

有人可以向我解释一下这种方法是如何工作的吗？

minesweeper1 = g =>
!g.some((r,i) =>
      r.some((c,j) =>
            c < 9 && (f = d => d-- ? f(d) - ((g[i + ~-(d/3)] || 0)[j + d%3 - 1] > 8) : c)(9)
           )
     )

我了解多少：

g是二维数组，代表场
.some 将测试，如果数组中的元素将通过测试
r 是字段中的单行
c 是每行中的每个元素
i 和 j 是什么？柜台？
什么是d？
代码写的这么隐晦有什么好处？

Answer 1

minesweeper1 = mainarray => // an arrow function, that gets the two d array passed
!mainarray.some((row,rownumber) =>
  row.some((field,columnumber) =>//checking the 2d array if some of the fields
        field < 9 && (//is not a mine
          recursive = d => //and the magic recursive function is true
            d-- 
            ? recursive(d) /* get the value of one lower d*/ - ((mainarray[rownumber + ~-(d/3)] || 0)[columnnumber + d%3 - 1] > 8) /* subtract one if this magic is true */
             : field//if d=-1 it returns field
         )(9)//the starting point of the recursive function d=9
   ))

所以它基本上检查，如果某些字段不是地雷（字段<9）并且递归函数成功。递归函数从 0 到 9 并处理以下步骤：

field //the current value as start value

//d=0
- (mainarray[rownumber - Math.floor(d/3)-1][columnnumber + d%3 ] >8)
//d=1
 - (mainarray[rownumber - Math.floor(d/3)-1][columnnumber + d%3 ] >8)
//...
//repeat until d=9

( 如果您对 ~-(d/3) 感到疑惑，它会执行以下操作：

0-2: ~-([0,1,2]/3) = ~-0 = -(-0)-1 = -1
3-5: ~-([3,4,5]/3) = ~-1 = -(-1)-1 = 0
6-8: ~-([6,7,8]/3) = ~-2 = -(-2)-1 = 1

)

所以基本上函数将通过这种模式（0 是 field ，X 是当前检查的位置）

d=0
X - -
- 0 -
- - -

d=1
- X -
- 0 -
- - -

d=2
- - X
- 0 -
- - -

d=3
- - -
X 0 -
- - -

...

然后如果有地雷 (>8)，它会从字段中减去 1 (true)。所以如果字段是4并且周围有4个地雷，它会做4-1-1-1-1，所以整个是0，这是假的：

两个例子（中间那个字段）：

9 9 9
9 4 1
1 1 0

所以递归函数将return 0 (falsy) ( 4-1-1-1-1)

9 9 9
2 4 1
0 0 0

这将 return 1 (truthy) (4-1-1-1)

所以这个递归函数可以重命名为 countaroundiswrong :

!mainarray.some((row,rownumber) =>
  row.some((field,columnumber) =>
    fieldismine() && countaroundiswrong(mainarray,field,rownumber,columnumber)
  )
)

所以如果有地雷，并且周围的计数是错误的，那么找到了一些字段并且整个事情都是真的，倒置并且结果是错误的。一种非神秘的方式：

function countaroundiswrong(mainarray,field,col,row){
 for(var x=-1;x<2;x++){
  for(var y=-1;y<2;y++){
    if(mainarray[row+x] && mainarray[row+x][col+y]){
      if(mainarray[row+x][col+y] >8){
         field--;
      }
    }
   }
  }
  return field;
}

扫雷算法解决方案

Minesweaper algorithm solution

javascript

arrays

algorithm

minesweeper

ecmascript-6