扫雷与算法：如何随机化的布雷（一）

怼烎@ 2022-01-23 13:43 203阅读 0赞

程序员小吴

读完需要

5分钟

速读仅需2分钟

> 这是通过「扫雷与算法」小程序来讲解算法的第一章：如何随机化的进行布雷，主要介绍了三种不那么好的方法，希望通过这些不好的方法能让大家明白第二章要讲解的「洗牌算法」有多牛逼。
> 
> 补充：「扫雷与算法」小程序会在写完后进行开源，发布在我的 GitHub 上面。

### 方法一 ###

最想当然的方法就是随机的在二维区间寻找一个点布雷即可，代码如下：

for (var i = 0; i < mineNumber; i++) {       var row = this.rangeRandom(0, this.rowCount - 1);       var col = this.rangeRandom(0, this.colCount - 1);       //使用数字 9 表示该区域有雷       tmpMineMap[row][col] = 9; }var i = 0; i < mineNumber; i++) {
        
           var row = this.rangeRandom(0, this.rowCount - 1);
           var col = this.rangeRandom(0, this.colCount - 1);
           //使用数字 9 表示该区域有雷
           tmpMineMap[row][col] = 9;
     }

这种实现逻辑的一个弊端就是会在已经布雷的位置再度布雷，进而导致整个区域的布雷数量与要求不符合。

![640?wx\_fmt=gif][640_wx_fmt_gif]

如上图所示，需要布雷的个数为 5 ，但在最后一次的随机布雷过程中只埋了 4 颗雷。

### 方法二 ###

方法二是对方法一的改善：既然会重复埋雷，那么只需要再埋雷的过程中判断一下该位置是否已经埋雷即可。

代码如下：

for (var i = 0; i < mineNumber; i++) {      //通过死循环来实现不停的寻找，直到安置好雷      while (true) {        var row = this.rangeRandom(0, this.rowCount - 1);        var col = this.rangeRandom(0, this.colCount - 1);        //用数字 9 表示该区域有雷，如果该位置没有布雷，那么则放置        if (tmpMineMap[row][col] != 9) {           tmpMineMap[row][col] = 9;           //跳出循环           break;        }      }    }var i = 0; i < mineNumber; i++) {
        
          //通过死循环来实现不停的寻找，直到安置好雷
          while (true) {
        
            var row = this.rangeRandom(0, this.rowCount - 1);
            var col = this.rangeRandom(0, this.colCount - 1);
            //用数字 9 表示该区域有雷，如果该位置没有布雷，那么则放置
            if (tmpMineMap[row][col] != 9) {
        
               tmpMineMap[row][col] = 9;
               //跳出循环
               break;
            }
          }
        }

使用效果如下：

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

效果貌似挺好的，但小伙伴们可能已经注意到了，上面的代码中有一段 **死循环** 代码，这就意味着如果棋盘很大，雷区很多，并且你的运气还不够好的话，那么就有可能一直在执行这段 **死循环** 代码，进而导致程序的卡死崩溃。

![640?wx\_fmt=gif][640_wx_fmt_gif 2]

虽然没有卡死，但执行时间很久，再多的话就会出问题

### 方法三 ###

第三种方法是先将雷布置在最前面，然后再不停的打乱。

实现代码如下：

//先按顺序排列for (var i = 0; i < mineNumber; i++) {    var row = parseInt(i / this.colCount);    var col = i % this.colCount;    //使用数字 9 表示该区域有雷    tmpMineMap[row][col] = 9;}//定义交换的次数，次数越多越混乱随机var swapTime = 100;for (var i = 0; i < swapTime; i++) {    //随机位置1    var row1 = this.rangeRandom(0, this.rowCount - 1);    var col1 = this.rangeRandom(0, this.colCount - 1);    //随机位置2    var row2 = this.rangeRandom(0, this.rowCount - 1);    var col2 = this.rangeRandom(0, this.colCount - 1);    //交换两个位置    var temp = tmpMineMap[row1][col1];    tmpMineMap[row1][col1] = tmpMineMap[row2][col2];    tmpMineMap[row2][col2] = temp;}
    for (var i = 0; i < mineNumber; i++) {
        
        var row = parseInt(i / this.colCount);
        var col = i % this.colCount;
        //使用数字 9 表示该区域有雷
        tmpMineMap[row][col] = 9;
    }
    
    //定义交换的次数，次数越多越混乱随机
    var swapTime = 100;
    for (var i = 0; i < swapTime; i++) {
        
        //随机位置1
        var row1 = this.rangeRandom(0, this.rowCount - 1);
        var col1 = this.rangeRandom(0, this.colCount - 1);
        //随机位置2
        var row2 = this.rangeRandom(0, this.rowCount - 1);
        var col2 = this.rangeRandom(0, this.colCount - 1);
        //交换两个位置
        var temp = tmpMineMap[row1][col1];
        tmpMineMap[row1][col1] = tmpMineMap[row2][col2];
        tmpMineMap[row2][col2] = temp;
    }

![640?wx\_fmt=gif][640_wx_fmt_gif 3]

这种方法的一个弊端就是对于 **swapTime** 的依赖程度很高，如果设置的交互次数少了，大部分雷都还是按照一开始的顺序安置，都在最前面的位置，全部的雷并不是随机排放。

最重要的一点是：**每个位置安置雷的概率并不是等可能的**，也就意味着它不能做到随机化。

> 我尝试过在小程序上进行概率模拟，搞了半天也没弄好，每次都会卡死，后续发现能优化继续模拟出概率来的话再补上。

### 总结 ###

在大部分情况下，**方法二** 与 **方法三** 是可以满足我们随机化处理的过程的，但方法二有可能运行卡死崩溃，方法三中每个位置安置雷的概率并不是等可能的。

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_gif]: /images/20220123/555e4208e6b848318579b9674baf4be6.png
[640_wx_fmt_gif 1]: /images/20220123/c7ba3ac4a78d4096a1af727ece8f1207.png
[640_wx_fmt_gif 2]: /images/20220123/85af448735de49b4b868b2c1c44785c5.png
[640_wx_fmt_gif 3]: /images/20220123/2579f23bfa51401ea8a5c8734e4b83a3.png
[640_wx_fmt_png]: /images/20220123/5df3bef8586040fca9298e03120e1b12.png