用 Rust + WebAssembly 构建 Slitherlink 谜题引擎

Source: Dev.to

请提供您希望翻译的具体文本内容，我将为您翻译成简体中文并保持原有的格式、Markdown 语法以及技术术语不变。

为什么选择 Rust？

Slitherlink 生成的计算量非常大。一个 10×10 的网格有 220 条可能的边。引擎需要：

• 生成一个有效的闭合回路
• 放置数字线索
• 验证谜题恰好只有唯一解
• 根据所需的求解技巧评估难度

JavaScript 无法高效处理这些任务。Java 是我们的第一次尝试（它能工作），但 Rust 为我们带来了 10–50 倍的加速，并且可以编译成 WebAssembly 用于客户端求解。

架构概述

第 1 阶段：环路生成

从一个空网格开始。构造一条随机的类似哈密顿路径，使其形成一个闭合环：

·───·   ·───·───·
│       │       │
·   ·───·   ·   ·
│   │       │   │
·   ·   ·───·   ·
│   │   │       │
·───·   ·───·───·

该算法使用带回溯的随机深度优先搜索。关键约束： 环路触及的每个顶点必须恰好有度数 2（进入一条线，离开一条线）。

第 2 阶段：线索放置

统计每个单元格周围的边数以生成数字：

·───·   ·───·───·
│ 2   1 │ 2   3 │
·   ·───·   ·   ·
│ 2 │ 2     2 │ 2
·   ·   ·───·   ·
│ 1 │ 1 │ 2   2 │
·───·   ·───·───·

随后有选择地去除部分数字以形成谜题。去除更多数字会让谜题更难，但难度取决于保留了哪些数字，而不仅仅是数量。

第 3 阶段：唯一性验证

这是耗时的部分。求解器必须通过以下方式确认恰好只有一个解：

• 约束传播——穷尽所有已知模式（角落规则、相邻 3‑3、顶点度等）。
• 回溯——当传播停滞时，挑选一个未决定的边，尝试两种状态（有线 / 无线），并对每个分支继续传播。
• 唯一性检查——如果两个分支都得到有效解，则该谜题有多个解，需被舍弃。

fn solve(puzzle: &Puzzle) -> usize {
    propagate_all_constraints(puzzle);
    if puzzle.is_contradictory() {
        return 0; // no solution
    }
    if puzzle.is_fully_decided() {
        return 1; // one solution found
    }
    let e = puzzle.pick_undecided_edge();
    let mut count = 0;
    // try edge = line
    let mut p1 = puzzle.clone();
    p1.set_edge(e, true);
    count += solve(&p1);
    // try edge = no line
    let mut p2 = puzzle.clone();
    p2.set_edge(e, false);
    count += solve(&p2);
    count // total solutions
}

如果总数超过 1，则该谜题模糊不清，被丢弃。

第 4 阶段：难度评级（10 级）

我们不仅仅计数线索——还衡量求解所需的技巧：

评级引擎模拟人类求解者：按复杂度顺序应用技巧，记录为取得进展所需的最高技巧级别。该最高技巧级别即为谜题的难度。

fn rate_puzzle(puzzle: &Puzzle) -> u8 {
    let mut max_level = 1;
    let mut state = SolverState::new(puzzle);

    loop {
        if state.apply_corner_rules() { max_level = max(max_level, 1); continue; }
        if state.apply_adjacent_patterns() { max_level = max(max_level, 3); continue; }
        if state.apply_vertex_degree() { max_level = max(max_level, 5); continue; }
        if state.apply_loop_closure() { max_level = max(max_level, 7); continue; }
        if state.apply_bifurcation() { max_level = max(max_level, 9); continue; }
        break;
    }
    max_level
}

编译为 WebAssembly

Rust 引擎通过 wasm-pack 编译为 WASM：

wasm-pack build --target web --release

生成的 .wasm 二进制文件约 200 KB，可在浏览器中运行，用于：

• 客户端谜题校验（防作弊）
• 提示生成
• 解答验证

对于批量生成（我们预生成 3000+ 谜题），使用本地二进制：

./slitherlink-engine gen --grid-size 10 --level 6 --count 100

它会将 JSON 输出到 stdout——每行一个谜题，包含 grid_size、clues、solution 和 difficulty 评级。

生产流水线

Rust engine (batch generate)
    → JSON puzzles
    → Import to Cloudflare D1 database
    → CF Worker API serves puzzles
    → Next.js frontend renders with Phaser 3

数据库中保存了 3000 多个谜题，涵盖 5 种网格尺寸（5×5、7×7、8×8、10×10、12×12）和 10 个难度等级。API 支持按尺寸和难度过滤的随机谜题选择、每日挑战和排行榜。

数字

• 生成速度：~50 题/分钟，适用于 10×10 Level 5‑6
• WASM 包：200 KB gzipped
• 求解时间（WASM，10×10）：. 难度评级是真实的：Level 1 感觉温和；Level 8 会让你汗流浃背。