Minesweeprs

本项目是将 @mrgriscom 的扫雷求解算法移植到 Rust，旨在提高性能，并允许通过 WebAssembly 在浏览器中运行。

求解

要解一个棋盘，你需要提供一些描述游戏状态的抽象“规则”以及关于整个棋盘的信息：单元格总数和地雷总数。原始项目的“单元格地雷概率”功能也得到实现，但支持程度较低。

每条规则代表从棋盘未揭开的单元格中获得的信息。单个 Rule 由一组单元格和该组中要找到的地雷数量组成。因此，对于给定的一个未揭开的单元格（比如我们揭开了3），我们会生成以下内容： Rule::new(3, [相邻单元格集合])。

求解器没有网格或棋盘几何的概念，它只知道特定的单元格集合。

以下是一个示例（ASCII 图来自原始 README 文件）

..1Axxxxxx
..2Bxxxxxx
..3Cxxxxxx
..2Dxxxxxx
112Exxxxxx
IHGFxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx

这是一个简单模式的棋盘；10x10，有10个地雷。我们为每个覆盖的单元格分配了一个唯一的标签（A，B，C，……），这些单元格位于未揭开的区域旁边（以下简称“前方”）。

以下代码可以解这个棋盘

use std::rc::Rc;
use minesweeprs::{solve, BoardInfo, Rule};
let output = solve(
    &[
        Rule::new(1, ['A', 'B']),
        Rule::new(2, ['A', 'B', 'C']),
        Rule::new(3, ['B', 'C', 'D']),
        Rule::new(2, ['C', 'D', 'E']),
        Rule::new(2, ['D', 'E', 'F', 'G', 'H']),
        Rule::new(1, ['G', 'H', 'I']),
        Rule::new(1, ['H', 'I']),
    ],
    BoardInfo { total_cells: 85, total_mines: 10 },
    '.',
);
// The board is solvable, so the below should hold:
assert_eq!(
    output,
    Ok(
        [
            ('A', 0.0),
            ('B', 1.0),
            ('C', 1.0),
            ('D', 1.0),
            ('E', 0.0),
            ('F', 0.07792207792207793),
            ('G', 0.0),
            ('H', 0.9220779220779222),
            ('I', 0.07792207792207793),
            ('.', 0.07792207792207792),
        ].into(),
    )
);

这将返回一个Result<HashMap<char, f64>, InconsistencyError> - 一个标签到概率的映射。如果棋盘可解，则Result将是Ok，如果不能解（例如，如果状态不一致/矛盾，或者没有可能的解决方案），则将是Err。

（尽管键的顺序将是随机的）

从这些中我们可以看到，B、C和D一定是地雷，A、E和G一定是安全的，H有92.21%可能是地雷，而F、I以及所有其他单元格（由标签.表示）都有7.79%可能是地雷。

请注意，total_cells被传递为85而不是100。这是因为有15个单元格已被揭开，并且不包括在任何规则中。求解器不知道网格的几何形状，因此这些单元格只是从单元格总数中减去，求解器甚至不需要知道它们的存在。或者，可以有一个规则Rule::new(0, [所有未揭开单元格的集合])并将total_cells设置为100。技术上，可以为每个单独的未揭开单元格制作一个单独的Rule，但这既麻烦又低效。

通常，total_cells必须等于网格中所有覆盖单元格的数量，加上恰好包含在规则中的未覆盖单元格数量。total_mines必须等于网格中所有地雷的总数，减去任何已被识别但未在任何Rule中提及的地雷（否则求解器将尝试将它们放置在未覆盖的单元格中）！

您可以看到，为solve()生成适当参数的具体逻辑相当复杂（假设您不采用简单的路线）。幸运的是，提供了可以为您处理这些过程的实用代码。请参阅minesweepr::util::Board::generate_rules()。您还可以使用minesweepr::util::read_board()（没有像上面为了说明目的所执行的显式标记A、B、C）。