algorithm - 扫雷生成背后的算法是什么

Question

好吧，我访问过很多网站，教他们如何解决它，但我想知道如何创建它。我对它的编码方面不太感兴趣，但想更多地了解它背后的算法。例如，当网格生成有 10 个左右的地雷时，我会使用任何随机函数将其自身分布在网格中，但是我又如何设置与其关联的数字并决定打开哪个框？我无法构建任何关于我将如何去做的通用算法。

Answer 1

也许是这样的:

grid = [n,m]   // initialize all cells to 0
for k = 1 to number_of_mines
   get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine
   for x = -1 to 1
      for y = -1 to 1
         if x = 0 and y = 0 then
            grid[mine_x, mine_y] = -number_of_mines  // negative value = mine
         else 
            increment grid[mine_x + x, mine_y + y] by 1

差不多就是这样了

** 编辑 **

因为此算法可能会导致创建的棋盘中一些地雷过于集中在一起，或者更糟的是非常分散(因此求解起来很无聊)，因此您可以在生成 mine_x 时添加额外的验证 和 mine_y 号码。例如，确保至少 3 个相邻的单元格不是地雷，或者甚至可能倾向于限制彼此距离太远的地雷的数量等。

** 更新 **

我冒昧地玩了一下 JS bin 在这里想出了一个功能 Minesweeper game demo .这只是为了演示此答案中描述的算法。我没有优化生成地雷位置的随机性，因此有些游戏可能是不可能的或者太容易了。此外，没有关于网格中有多少地雷的验证，因此您实际上可以创建一个包含 1000 个地雷的 2 x 2 网格……但这只会导致无限循环 :) 尽情享受吧!