标签: minesweeper

我正在尝试学习逆向工程,使用Minesweeper作为示例应用程序.我在一个简单的WinDbg命令上发现了这篇MSDN文章,它揭示了所有的地雷,但它已经很老了,没有详细解释,也不是我想要的.

我有IDA Pro反汇编程序和WinDbg调试程序,我已经将winmine.exe加载到它们中.在找到代表矿区的数据结构的位置方面,有人能为这些程序中的任何一个提供一些实用技巧吗？

在WinDbg中我可以设置断点,但是我很难想象在什么时候设置断点和什么内存位置.同样,当我在IDA Pro中查看静态代码时,我不知道在哪里开始找到代表矿区的函数或数据结构.

Stackoverflow上是否有任何反向工程师可以指向正确的方向？

这是来自Google Code Jam资格回合的问题(现已结束).如何解决这个问题呢？

注意:如果您的方法与答案中讨论的方法不同,请分享,以便我们扩展我们对解决此问题的不同方法的了解.

问题陈述:

扫雷是一种计算机游戏,在20世纪80年代开始流行,并且仍然包含在某些版本的Microsoft Windows操作系统中.这个问题有类似的想法,但它并不假设你玩过扫雷.

在这个问题中,您正在相同单元格的网格上玩游戏.最初隐藏每个单元格的内容.在M个不同的网格单元中隐藏着M个矿井.没有其他细胞包含地雷.您可以单击任何单元格以显示它.如果揭示的细胞包含一个矿,那么游戏就结束了,你输了.否则,显示的单元格将包含0到8之间的数字(包括0和8),这对应于包含地雷的相邻单元格的数量.如果两个单元共享一个角或边,则它们是邻居.另外,如果显示的单元格包含0,那么所揭示的单元格的所有邻居也会以递归方式自动显示.当所有不包含地雷的细胞都被揭露时,游戏结束,你就赢了.

例如,电路板的初始配置可能如下所示('*'表示我的,而'c'是第一个单击的单元格):

*..*...**.
....*.....
..c..*....
........*.
..........

点击的单元格旁边没有地雷,因此当它被显示时,它变为0,并且它的8个相邻单元也被显示出来.此过程继续,导致以下板:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时,仍有未显示的单元格不包含地雷(用'.'字符表示),因此玩家必须再次点击才能继续游戏.

你想尽快赢得比赛.没有什么比单击赢得更快.考虑到电路板的尺寸(R x C)和隐藏的地雷M的数量,是否有可能(但不太可能)一键获胜？您可以选择单击的位置.如果可能,则按照"输出"部分中的规范打印任何有效的矿井配置和点击坐标.否则,打印"不可能".

我试过的解决方案:

因此,对于解决方案,您需要确保每个非采矿节点与其他非采矿节点处于3x3矩阵中,或者如果节点位于网格边缘,则需要3x2或2x2矩阵; 我们称之为0Matrix.因此,0Matrix中的任何节点都具有所有非矿井邻居.

首先,检查是否需要更少的地雷,或更少的空节点

if(# mines required < 1/3 of total grid size)
    // Initialize the grid to all clear nodes and populate the mines
    foreach (Node A : the set of non-mine nodes)
        foreach (Node AN : A.neighbors)
            if AN forms a OMatrix with it's neighbors, continue
            else break;
        // If we got here means …

我很确定大多数人都知道扫雷游戏.我想编码(在C#中)我自己的扫雷游戏,并且正在寻找一些关于该游戏的优秀算法的输入.我一直在浏览网页很长一段时间,但找不到一个好的解决方案.任何人都可以帮助我吗？

我正在设计类似扫雷的游戏(带有修改过的规则),我想阻止玩家猜测.我的目标是:生成的棋盘上只有很少的显示方块,玩家可以毫无猜测地解决整个拼图.

维基百科提到:

Minesweeper的一些实现将通过从未在显示的第一个方块上放置一个矿,或者通过安排板以使解决方案不需要猜测来设置板.

但是,我无法弄清楚算法.

此外,在另一个StackOverflow问题:扫雷解决算法

改进:在生成器旁边运行求解器,确保拼图具有独特的解决方案.这需要一些聪明,并且在大多数变体中都没有.

我怀疑这是否真的有效.众所周知,解决扫雷是NP完全的.

总之,我的问题是:

• 如何生成一个不需要猜测的扫雷板？
• 如果可以的话,具体的算法是什么？
• 我们能否确定性地在多项式时间内解决这个问题？这个问题NP完全吗？怎么证明呢？

好吧,我已经通过许多网站教授如何解决它,但想知道如何创建它.我对它的编码方面不感兴趣,但想了解更多关于它背后的算法.例如,当网格生成10个左右时,我会使用任何随机函数在网格上分布自己,但是我又如何设置与之关联的数字并决定打开哪个框？我无法构建任何通用算法,我将如何做到这一点.

我用Python实现了一个解决游戏"扫雷"的算法.该计划的工作原理如下:

假设求解器单击名为"a"的正方形.为了举例,让这样揭示的数字等于2.尚未被点击的正方形的邻居(再次作为示例)被命名为"b"和"c".程序然后将正方形与表达式[2,{'b','c'}]相关联,并从所有其他表达式中删除'a'.在两种情况下,通过成对简化这些表达式来推断哪些正方形是地雷并且不进行收益.

• 如果一个表达式中的正方形是另一个表达式的正方形的子集:

  [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}]
  

  Run Code Online (Sandbox Code Playgroud)

• 如果一个表达式中的所有正方形都被确定为地雷:

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}]
  

  Run Code Online (Sandbox Code Playgroud)

然后,对于某些表达式X,如果X[0] == 0,我们可以自由地点击命名的所有正方形X[1],如果X[0] == len(X[1]),那么我们可以标记它们.

但是,我正在努力确定哪些表达式试图简化.我目前的做法是保持一堆正方形; 无论何时单击一个正方形,或者已成功简化其表达式,都会将其添加到堆栈中(如果它尚未存在).当方从堆栈中弹出,简化尝试其表达(之间X),以及任何其他表达式Y,使得X[1] & Y[1] != set().当堆栈耗尽时,算法终止.然而,目前虽然这很有效,但它无法正确解决所有明确的配置,如果我用队列替换堆栈,或者使用某种算法确定要弹出哪个方块,它在给定板上的执行情况会有显着变化!

对于我的方法的先例或潜在探索的途径,我将非常感激.

编辑:这是一段时间以前,我已经开始工作,如果你想看到它包含在github.com/LewisGaul/minegaulerQt的代码.

我正在尝试编写一个程序来计算游戏扫雷的概率,并且在如何最好地构建它时遇到了一些困难.虽然首先使用下面的示例看起来很简单,但我想知道允许更复杂配置的最佳方法.注意我不是在寻找有关如何计算概率的帮助 - 我知道方法,我只需要实现它!

为了清楚我想要计算的内容,我将通过一个简单的例子来完成,这个例子可以手工完成.考虑扫雷配置
# # # #
# 1 2 #
# # # #
,其中#表示未被单击的单元格.该1告诉我们有在最左边的7个未点击的细胞正好1矿山,2告诉我们恰好有2在最右边7.要计算含矿每个单独的小区的概率,我们需要确定所有不同的情况下(仅2在这个简单的情况下):

1. 在最左边3个细胞中有1个矿井,在最右边3个细胞中有2个矿井(总共3个矿井,3x3 = 9个组合).

2. 中心4个单元中的1个矿井,最右边3个单元中的1个矿井(总共2个矿井,4x3 = 12个组合).

鉴于矿井在随机单元格中的概率约为0.2,它(在随机选择的单元格中)总共2个地雷的可能性大约是4倍,而不是总共3个,所以地雷总数在配置方面,以及每种配置的组合数量.所以在这种情况下,情况1的概率是9 /(9 + 4x12)= 0.158,因此在给定的最左边单元格中存在矿的概率约为0.158/3 = 0.05,因为这些单元格实际上是等价的(它们分享完全相同的透露邻居).

我用Tkinter创建了一个GUI,它允许我轻松输入配置,例如示例中的配置,它将网格存储为numpy数组.然后我创建了一个NumberGroup类,它隔离了每个被点击/编号的单元格,存储了未被点击的邻居的数量和一组坐标.可以减去这些以获得等价组...虽然如果有三个或更多数字而不是两个数字,这不会那么简单.但我不确定如何从这里获得不同的配置.我玩弄了一Configuration堂课,但我并不十分熟悉不同班级应该如何合作.请参阅下面的工作代码(需要numpy).

注意:我知道我本可以尝试使用蛮力方法,但如果可能的话我想避免这种情况,保持等效组分开(在上面的例子中有3个等价组,最左边3个,中间4个,最右边的3).我想听听你对此的看法.

import numpy as np

grid = np.array(
    [[0, 0, 0, 0],
     [0, 2, 1, 0],
     [0, 0, 0, 0]]
    )
dims = (3, 4) #Dimensions of the grid

class …

我需要实现扫雷解算器.我已经开始实现基于规则的代理.我已经实施了一些规则.我有一个启发式函数,用于为当前单元格(有关周围单元格的信息)选择最佳匹配规则.因此,对于每个选定的细胞,它可以决定8个环境细胞打开它们,标记它们或什么都不做.我的意思是.此时,代理人将一些显示的细胞作为输入,并决定如何处理周围的细胞(此时,代理人不知道,如何决定要治疗哪个细胞).

我的问题是,用什么算法来决定要处理哪个细胞？

假设,对于第一次移动,代理将显示角落单元格(或根据某些规则进行第一次移动).那后该怎么办？

我知道我需要实现某种搜索.我知道很多搜索算法(BFS,DFS,A-STAR等),这不是问题,我只是不明白我怎么能在这里使用这些搜索.

我需要在人工智能原理中实现它:一种现代方法.

我在javascript中制作了一个扫雷游戏,最后运行起来非常顺利,直到我添加了"expand()"功能(见下文).我有3个问题:

1. 当它扩展时,它会增加太多"flippedCount"(见下面的代码) - 在右下方div中的图像显示"flippedCount",而它的39则代替35.
2. 结果,如果玩家在"展开()"期间超过90格(赢得金额),则获胜屏幕不会显示.
3. 它也没有正确扩展(见下图).

相关代码和链接低于这两个图像

var flippedCount = 0;
var alreadySetAsZero = [];
var columnAmount = 10;

function processClick(clicked) { //i use a "(this)" to pass as "(clicked)"
  nextToBombCheck( parseInt(clicked.id) );
  checkWin();
}

nextToBombCheck( boxNum ) { 
  flippedCount++;
  document.getElementById("flipped").innerHTML = flippedCount;  
  //long function setting "bombCount" to # bombs around clicked square goes here
  if ( bombCount !== 0 ) { 
    //blah blah blah
  } else {
    alreadySetAsZero[ boxNum ] = "yes";
    expand(boxNum);
  } 
}

function expand( emptyBoxId ) …

我试图用JavaScript进行扫雷,我遇到了一个让我困住了好几天的问题.我知道已有关于这个主题的帖子,但是我已经阅读了它们并试了一下,我没有运气.

我遇到的问题是当用户按下一个空白方块时,我希望它能够发现每个触摸它的空白方块(空白方块意味着网格上有一个正方形1个方块的正方形或对角线的正方形).

该程序现在几乎清除了每个相距一个方格的空白方块,但它仍然缺少一些随机的方块,我无法弄清楚原因.

我在调用runOffset()时尝试添加其他组合,例如runOffset(25,25)和runOffset(-25,-25)但是这并没有改变任何东西.这是一个简单的修复,还是我错了？

带圆圈的正方形是应该已经清除但不是正方形的正方形,X是用户点击的位置.

•我写错了吗？(我写出函数的方式会按照我想要的方式执行吗？)

•函数checkBlanks()是否因错误原因而退回？

•我错过了错过上图中圈出的方块的错误？

完整代码(第297行)

function borderingBombs(safeSquareCoords) {
    var minesNext = 0;
    for (var i = 0; i < mines.length; i++) {
        var mineCoords = mines[i].split(",");
        if (mineCoords[0] - 25 == safeSquareCoords[0]) {
            if (mineCoords[1] == safeSquareCoords[1]) {
                // Left
                minesNext++;
            } else if (mineCoords[1] - 25 == safeSquareCoords[1]) {
                // Top Left
                minesNext++;
            } else if (mineCoords[1] == safeSquareCoords[1] - 25) {
                // Bottom Left
                minesNext++;
            }
        } else if (safeSquareCoords[0] - 25 == …