扫雷是NP完全问题
本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP完全的...
结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题。作者还有一个非常直观的PPT演示证明过程，比如下图展示如何编码AND逻辑门：
它是NP完全问题说明如果程序要想完全正确，所费的时间最坏情况下将是指数的。不过我猜测对于大部分的扫雷的实例还是很容易的，而且NPC所用的规约实例特别大，所以编一个能较快速度解决大部分windows自带的那个高级难度的扫雷问题还是可行的，不知道是否已经有这方面的程序。
怎么知道的？上TCS课知道的？
不是的。我是在网上无意中看到的。
Nice
有点意思
我是50多秒……
不知道网上游戏时有的人会用挂一两秒内解决那是怎么实现的呢？
这个证明思路挺有启发性的 剑走偏锋
扫雷大概是世界上最多人参加解决的npc问题了吧
已经有这样的程序了。而且是很早之前就有了，所谓外挂。
在启动扫雷的后, 按 xyzzy 再按 shift 后开始游戏, 这时鼠标指到格子上时, 观察屏幕的左上角会有一个针尖大小的亮点, 当亮点熄灭时表明该格子是地雷, 亮点亮时则不是地雷 (最好先把墙纸关掉, 桌面设为黑色).
好像不行啊
你需要非常仔细的观察左上角，最好把你的背景调一调，就一个像素那么大
我看到了.
怎么感觉NPC问题无处不在呢！
这个是不是就是节一个线性方程组？
是的。不过是求整数解，而整数规划也是NPC的。
貌似有这种程序哦,我以前都试过.
但是往往接到一半就需要自己动手点几下
这种从算法上就很复杂了，不过如果从内部数据结构下手（crack)，就很简单了。
可以通过寻找tiles即某些固定模式作为经验求解
分享一个秒杀xp扫雷的程序，用python实现，有兴趣的可以改成C，挺简单的，主要是调用win32API。
import win32gui
import win32process
import win32con
import win32api
from ctypes import *
MAX_ROWS = 24
MAX_COLUMNS = 30
MINE_BEGIN_X = 0xC
MINE_BEGIN_Y = 0x37
MINE_GRID_WIDTH = 0x10
MINE_GRID_HEIGHT = 0x10
MINE_BOARDER = 0x10
MINE_SAFE = 0x0F
MINE_DANGER = 0x8F
BOARD_ADDR = 0x1005340
class SMineCtrl(Structure):
_fields_ = [("hWnd", c_uint),
("board", (c_byte * (MAX_COLUMNS + 2)) * (MAX_ROWS + 2)),
("rows", c_byte),
("columns", c_byte)
]
kernel32 = windll.LoadLibrary("kernel32.dll")
ReadProcessMemory = kernel32.ReadProcessMemory
WriteProcessMemory = kernel32.WriteProcessMemory
OpenProcess = kernel32.OpenProcess
ctrlData = SMineCtrl()
try:
ctrlData.hWnd = win32gui.FindWindow("扫雷".decode('utf-8'), "扫雷".decode('utf-8'))
except:
win32api.MessageBox(0, "请先运行扫雷程序".decode('utf-8'), "错误！".decode('utf-8'), win32con.MB_ICONERROR)
exit(0)
hreadID, processID = win32process.GetWindowThreadProcessId(ctrlData.hWnd)
hProc = OpenProcess(win32con.PROCESS_ALL_ACCESS, 0, processID)
bytesRead = c_ulong(0)
ReadProcessMemory(hProc, BOARD_ADDR, byref(ctrlData.board), SMineCtrl.board.size, byref(bytesRead))
if(bytesRead.value != SMineCtrl.board.size):
str = "ReadProcessMemory error, only read ", bytesRead.value, " should read ", SMineCtrl.board.size
win32api.MessageBox(0, str, "错误！".decode('utf-8'), win32con.MB_ICONERROR)
exit()
ctrlData.rows = 0
ctrlData.columns = 0
for i in range(0, MAX_COLUMNS + 2):
if MINE_BOARDER == ctrlData.board[0][i]:
ctrlData.columns += 1
else :
break
ctrlData.columns -= 2
for i in range(1, MAX_ROWS + 1):
if MINE_BOARDER != ctrlData.board[i][1]:
ctrlData.rows += 1
else:
break
for i in range(0, ctrlData.rows):
for j in range(0, ctrlData.columns):
if MINE_SAFE == ctrlData.board[i + 1][j + 1]:
win32api.SendMessage(ctrlData.hWnd,
win32con.WM_LBUTTONDOWN,
win32con.MK_LBUTTON,
win32api.MAKELONG(MINE_BEGIN_X + MINE_GRID_WIDTH * j + MINE_GRID_WIDTH / 2,
MINE_BEGIN_Y + MINE_GRID_HEIGHT * i + MINE_GRID_HEIGHT / 2))
win32api.SendMessage(ctrlData.hWnd,
win32con.WM_LBUTTONUP,
win32con.MK_LBUTTON,
win32api.MAKELONG(MINE_BEGIN_X + MINE_GRID_WIDTH * j + MINE_GRID_WIDTH / 2,
MINE_BEGIN_Y + MINE_GRID_HEIGHT * i + MINE_GRID_HEIGHT / 2))
win32api.MessageBox(0, "搞定！".decode('utf-8'), "信息".decode('utf-8'), win32con.MB_ICONINFORMATION)
你做个是读系统数据，然后模拟鼠标把雷点开而已。这东西冇什么意思。
如果要锻炼算法功底的话，你可以尝试写一个不作弊，利用推理把雷扫出来的程序。