玩扫雷的数学解法

凸优化

---

1. 定义

该部分的定义是为了将扫雷的已知情况数据化、符号化，方便将其抽象成一个数学问题。

• m=扫雷区域高度。
• n=扫雷区域宽度。
• 第$i \in \lbrace 0,1,\dots,m-1 \rbrace$行，第$j \in \lbrace 0,1,\dots,n-1 \rbrace$列的格子称为第$i\times c+j$号格子。
• 扫雷区域状态：$b=(b_0,b_1,\dots,b_n)^T$，其中$b_i$表示第$i$号格子周围地雷的个数。
• 扫雷解向量：$x=(x_0,x_1,\dots,x_n)^T$，其中$x_i \in [0,1]$表示第$i$号格子有雷的概率。
• 格子相邻关系$R$，$iRj$表示$i$号格子与第$j$号格子相邻。写成关系矩阵的形式$A_{mn \times mn}=[a_{ij}]$，
  $$a_{ij}=\begin{cases} 1 & iRi\\ 0 & else \end{cases}$$

2. 算法

$Ax=b$去掉$b_i$的值未知的行，去掉$x_i=0$的列，构成线性约束：

$$A'x=b'$$
$$\begin{array}\\ &\min &\frac{1}{2}||(x-\frac{1}{2}\mathbf{1})||^2\\ &s.t. &A'x=b'\\ & &x\ge \mathbf{0}\\ & &x\le \mathbf{1} \end{array}$$

3. 推导过程

4. 改进

在加入一个等式约束条件：

$$\mathbf{1}^Tx=\text{总累数}$$