Masyu（真珠迷宫，日语「ましゅ」）是 Nikoli 公司在 2000 年前后推出的一款逻辑推理谜题。规则只有三条，但难度层次极其丰富：
- 盘面上散布着白珠和黑珠，你要画出一条闭合回路；
- 回路经过白珠时必须直行穿过，但进入白珠的前一格和离开白珠的后一格必须转弯；
- 回路经过黑珠时必须转弯，且转弯前后各再走一格都必须直行。
再加两条隐含规则：回路不能与自己交叉或重叠；不必经过所有空格（空格可以不被回路穿过）。
这三条规则的表述方式非常”局部”——全部是关于”某个格子处必须转弯还是必须直行”。但最终要求是”整条路径构成一个闭合的环”。局部约束与全局约束的这层张力，正是它适合用算法求解的原因。本文用 Java 把 Masyu 建模成网格上的 DFA（确定性有限自动机）路径搜索，再叠加单环全局判定，构造一个能解任意难度题目的求解器。
一、为什么”Masyu 求解”本质是状态机搜索
考虑在盘面上”画回路”这个过程。你站在某个格子上，知道自己是从哪个方向进来的。决定下一步往哪走时，唯一需要的信息是：
- 当前格子的类型（空白 / 白珠 / 黑珠）；
- 进入方向；
- （隐含）这个格子之前是否已被经过。
“当前格 + 进入方向”构成了一个有限的状态集，状态总数是 格子数 × 4（4 个进入方向）。每个状态下的”可行动作”（向哪个方向离开）由珠子类型唯一确定：
| 当前格 | 进入方向 | 允许离开方向 |
|---|---|---|
| 空白 | 任意 | 直行（同方向）或转弯（左右 90°），但不能掉头 |
| 白珠 | 任意 | 只能直行（同方向） |
| 黑珠 | 任意 | 只能转弯（左右 90°），不能直行、不能掉头 |
这就是一个标准的 DFA：状态 = (位置, 进入方向)，转移函数由上表给定。Masyu 的求解 = 在这个 DFA 上找一条从某状态出发、最终回到自身的、覆盖所有珠子且不自交的路径。
换个角度：DFA 的转移关系是完全局部的，这让问题可以高效地用”约束传播”来剪枝——每个状态的可行转移只有 2~3 个，比自由路径搜索的 4 个方向（去掉掉头剩 3 个）少得多。
而”白珠前后必须转弯”这条规则，进一步把相邻状态之间的转移也约束住了：白珠状态只能直行，但它前一个格子必须转弯进入它，后一个格子必须从它转弯离开。这意味着白珠的约束不是”一个状态”，而是”三个连续状态的三元约束”。这类”跨状态的转移约束”，正是 DFA 建模比单纯的图搜索更有表达力的地方。
二、把三条规则翻译成状态转移表
先把格子坐标 (r, c) 和方向 d（0=上, 1=右, 2=下, 3=左）编码。定义：
stateId(r, c, d)=((r * W + c) << 2) | d，表示”在 (r,c) 格、从 d 方向进入”。- 该状态的”离开方向”集合
exitSet(type, d)。
根据规则：
/** 给定格子类型与进入方向，返回允许的离开方向位掩码（bit d = 1 表示允许） */
static int exitMask(CellType type, int d) {
int straight = 1 << d;
int left = 1 << ((d + 1) & 3); // 左转 90°
int right = 1 << ((d + 3) & 3); // 右转 90°
switch (type) {
case EMPTY:
// 空白：可直行也可转弯，不可掉头
return straight | left | right;
case WHITE:
// 白珠：必须直行穿过
return straight;
case BLACK:
// 黑珠：必须转弯
return left | right;
default:
return 0;
}
}
注意方向编码方向：d 表示”从 d 方向进入”，也就是”移动方向是从 d 的反向指向当前格”。当从上方（d=0）进入时，直行意味着继续向下方离开，即 exit = 2。这里我把 d 定义成”进入方向的反向”，即 d=0 表示”来自上方、正在向下移动”，这样 straight = d 最简洁。这个编码约定必须在全代码中一致，否则转弯方向会整体错 90°，是这类实现最常见的 bug。
再处理”白珠前后必须转弯”的跨状态约束。白珠在 (r,c)，从 d 进入、直行从 d 离开（到达 (r’, c’) 即 (r,c) 沿 d 方向的下一个格子）。那么：
- 进入白珠的转移必须是转弯：即”前一个格子 p 处，从 d_in 进入、向 d 离开”，其中 d 与 d_in 的夹角必须是 90°；
- 离开白珠的转移必须是直行——这个已由白珠的 exitMask 保证；
- 白珠的下一个格子处必须转弯：即”在 (r’,c’) 从 d 进入时，离开方向必须与 d 成 90°”。
后一条约束最容易漏。它意味着：你不能只对珠子格子本身施加约束，还要对珠子的”邻居格子”施加约束。实现上，我把它编码成”预处理阶段的位掩码修正”：当判断 (r',c') 这个格子的合法 exitMask 时，如果它刚从一个白珠直行而来，就把 mask 与”转弯 allowed”做与运算。
三、单环约束：全局性质如何判定
局部 DFA 只能保证”每步合法”，但 Masyu 要求最终所有已画的路径构成恰好一个环。这是纯全局约束，DFA 层面完全看不到它。处理它有三种工程路径：
- 求解时用”路径是单一环”的充要条件：画出的路径图中，每个被使用格子的度数恰好为 2（进出各有一次），且全图只有 1 个连通分量。度数条件由 DFA 转移天然满足（每次经过都一进一出），所以唯一需要额外检查的是”连通分量数 = 1″。
- 在搜索过程中不检查，最后统一验证。但这样会让搜索器在”画出一个 8 字形（两个环）”的中间状态上浪费大量时间。
- 增量式维护：用一个并查集，每当画一条边就合并两端；若两端已在同一集合则说明成环——此时必须检查”这个环是否已经覆盖了所有还需覆盖的边”，否则就是提前闭合（会形成多个环）。
生产级求解器通常采用第 3 条，配合两类剪枝：提前闭合检测（成环时若还有未使用格则立即失败）和死角检测（某格剩余可用边数 < 2 时立即失败）。
本文给出一条更简洁但同样有效的实现：度数约束 + 并查集分量计数，配合”必须覆盖全部珠子”这一条硬约束。
/**
* 单环判定：给定已选中的边集合，检查
* 1) 每个被使用格子的度数为 2（或 0，表示未使用）
* 2) 所有被使用的格子属于同一个并查集分量
* 3) 所有珠子格子都已被使用
*/
boolean isSingleLoop(List<int[]> chosenEdges, int rows, int cols, CellType[][] grid) {
int[] deg = new int[rows * cols];
DSU dsu = new DSU(rows * cols);
boolean[] used = new boolean[rows * cols];
for (int[] e : chosenEdges) {
int a = e[0], b = e[1];
deg[a]++; deg[b]++;
used[a] = used[b] = true;
dsu.union(a, b);
}
// 条件 1：度数要么 0（未用）要么 2
for (int i = 0; i < rows * cols; i++) {
if (deg[i] != 0 && deg[i] != 2) return false;
}
// 条件 2：所有用到的格子在同一分量
int root = -1;
for (int i = 0; i < rows * cols; i++) {
if (!used[i]) continue;
if (root == -1) root = dsu.find(i);
else if (dsu.find(i) != root) return false;
}
// 条件 3：所有珠子被覆盖
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (grid[r][c] != CellType.EMPTY && !used[r * cols + c]) return false;
return true;
}
这里的三个条件互相独立、缺一不可。条件 1 保证”没有分叉、没有悬空端点”；条件 2 保证”不是多个环”；条件 3 保证”珠子都走到”。特别值得注意的是条件 1 的”度数恰好为 2″用的是已选边而不是 DFA 转移——这两者在正确实现下等价，但用度数检查更容易发现实现错误。
四、完整项目结构
masyu-dfa/
├── src/com/example/masyu/
│ ├── CellType.java // 格子类型枚举
│ ├── DSU.java // 并查集（单环判定用）
│ ├── MasyuSolver.java // DFA 建模 + 回溯搜索 + 剪枝
│ └── Main.java // 入口：解一道示例题并打印回路
└── README.md
4.1 核心求解器
package com.example.masyu;
import java.util.*;
public class MasyuSolver {
final int rows, cols;
final CellType[][] grid;
// 边集合：把相邻格子的边编码为 (minId, maxId) 对，用 Set<Integer> 快速判重
final Set<Integer> usedEdges = new HashSet<>();
// 每格的已使用度数
final int[] deg;
// 每格的进入方向记录（bit d 置位表示"已从 d 方向进入过"）
final int[] enterMask;
final DSU dsu;
int usedCells = 0;
long nodes = 0;
static final int[] DR = {-1, 0, 1, 0}; // 上行右列下行左列
static final int[] DC = {0, 1, 0, -1};
public MasyuSolver(CellType[][] grid) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
deg = new int[rows * cols];
enterMask = new int[rows * cols];
dsu = new DSU(rows * cols);
}
int id(int r, int c) { return r * cols + c; }
/** 边编码：无向边 (a,b) 用 a * N + b（a<b）唯一表示 */
int edgeKey(int a, int b) {
int n = rows * cols;
return a < b ? a * n + b : b * n + a;
}
/** 检查当前已用边是否可能"提前闭合形成多余的环" */
boolean hasPrematureCycle(int a, int b) {
// 若 a、b 已在同一分量，加这条边就会成环
if (dsu.find(a) == dsu.find(b)) {
// 成环时必须已经覆盖所有珠子，否则这个环是"多余的"
return !allBeadsCovered();
}
return false;
}
boolean allBeadsCovered() {
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (grid[r][c] != CellType.EMPTY && deg[id(r, c)] == 0) return false;
return true;
}
/**
* 从 (r,c) 以方向 d（进入方向的反向）继续推演。
* d 语义：0=向上移动, 1=向右, 2=向下, 3=向左（即"我正朝 d 方向走"）。
*/
boolean search(int r, int c, int d) {
nodes++;
// 确定当前格允许的离开方向
int mask = exitMaskLocal(r, c, d);
if (mask == 0) return false;
for (int out = 0; out < 4; out++) {
if ((mask & (1 << out)) == 0) continue;
int nr = r + DR[out], nc = c + DC[out];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int a = id(r, c), b = id(nr, nc);
// 边不能重复使用（避免自交）
if (usedEdges.contains(edgeKey(a, b))) continue;
// 目标格度数不能超过 2
if (deg[b] >= 2) continue;
// 做决策
usedEdges.add(edgeKey(a, b));
deg[a]++; deg[b]++;
int savedMaskB = enterMask[b];
enterMask[b] |= (1 << out);
int rootA = dsu.find(a), rootB = dsu.find(b);
boolean merged = false;
if (rootA != rootB) { dsu.union(a, b); merged = true; }
// 若合并后成环（即 a、b 原本同分量），检查全局条件
boolean cycleOk = true;
if (!merged) {
cycleOk = isSingleLoop();
}
if (cycleOk && search(nr, nc, out)) return true;
// 回溯
if (merged) dsu.undo();
enterMask[b] = savedMaskB;
deg[a]--; deg[b]--;
usedEdges.remove(edgeKey(a, b));
}
return false;
}
/** 本格允许的离开方向掩码；叠加"从白珠直行而来则必须转弯"的约束 */
int exitMaskLocal(int r, int c, int d) {
int mask = exitMask(grid[r][c], d);
// 反向约束：若上一格是白珠且本次是从它直行过来，
// 那么本格必须转弯。这个信息通过 enterMask 不方便存，
// 改为在进入前由调用方传 "cameFromWhiteStraight" 标志（见下）
return mask;
}
上面的 exitMaskLocal 留下了一个”白珠后续必须转弯”的尾巴没接上。正确做法是把”上一格是白珠且直行”这个信息作为搜索参数显式传递，而不是试图从 enterMask 反推。修改后的签名：
/**
* @param forceTurn 若为 true，表示"我是从白珠直行过来的"，本格必须转弯
*/
boolean search(int r, int c, int d, boolean forceTurn) {
nodes++;
int mask = exitMask(grid[r][c], d);
if (forceTurn) {
// 只保留转弯位，剔除直行
mask &= ~(1 << d);
}
// 若本格是白珠，则离开方向必须直行（exitMask 已保证），
// 且下一格 forceTurn = true
boolean nextForceTurn = (grid[r][c] == CellType.WHITE);
for (int out = 0; out < 4; out++) {
if ((mask & (1 << out)) == 0) continue;
int nr = r + DR[out], nc = c + DC[out];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
// 黑珠约束的完整版：黑珠除"必须转弯"外，转弯前后各再走一格必须直行。
// 这里用 nextForceTurn2 传递"刚从黑珠转弯出来，所以本格必须直行"
...
}
}
为避免参数爆炸，实际工程里更常用的做法是在预处理阶段直接把三元约束固化进每个状态的 exitMask。具体做法：对每个”白珠”，把它四个邻居格子的 exitMask 都预先与”转弯 allowed”做与运算；对每个”黑珠”，把它四个邻居格子的 exitMask 都预先与”直行 allowed”做与运算。这样就把”跨状态的转移约束”编译进了”单状态约束”，搜索时完全不需要额外传参。
这一步叫做约束编译（constraint compilation），是逻辑谜题求解器的标准优化手段：
/** 预处理：把珠子邻居的三元约束编译进各自的 exitMask */
void compileConstraints() {
// 邻居掩码：与白珠相邻的格子必须转弯，与黑珠相邻的格子必须直行
int[][] forcedTurn = new int[rows][cols]; // bit d 置位：从 d 进入时必须转弯
int[][] forcedStraight = new int[rows][cols];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
if (grid[r][c] != CellType.EMPTY) continue;
for (int d = 0; d < 4; d++) {
int pr = r + DR[d], pc = c + DC[d];
if (pr < 0 || pr >= rows || pc < 0 || pc >= cols) continue;
// 若邻居是白珠，本格必须转弯
if (grid[pr][pc] == CellType.WHITE) forcedTurn[r][c] |= (1 << d);
// 若邻居是黑珠，本格必须直行
if (grid[pr][pc] == CellType.BLACK) forcedStraight[r][c] |= (1 << d);
}
}
// 应用到 exitMask 查询函数
this.preTurn = forcedTurn;
this.preStraight = forcedStraight;
}
这段”约束编译”的价值在于：它把三元约束（涉及三个格子的连续状态）降维成单状态约束，让搜索器的每个节点只需算一个局部掩码。代价是一次性的 O(rows × cols) 预处理。这个思想在数独（行列宫约束编译成候选数表）、Kakuro（和值约束编译成位掩码）里都有对应物。
4.2 并查集的撤销支持
单环判定需要并查集支持回溯撤销，这是 DFA 路径搜索特有的需求（普通并查集不支持 undo）：
package com.example.masyu;
/** 支持撤销的并查集：不做路径压缩，只用按秩合并，便于记录 merge 历史 */
public class DSU {
final int[] parent, rank;
final Deque<int[]> history = new ArrayDeque<>();
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
while (parent[x] != x) x = parent[x]; // 无路径压缩，保证可撤销
return x;
}
/** 返回是否真的合并了 */
public boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) { history.push(new int[]{-1, -1}); return false; }
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) { rank[ra]++; history.push(new int[]{ra, 1}); }
else history.push(new int[]{ra, 0});
history.push(new int[]{rb, ra}); // 记录被挂到谁下面
return true;
}
/** 撤销最近一次 union */
public void undo() {
if (history.isEmpty()) return;
int[] e1 = history.pop();
if (e1[0] == -1) return;
int[] e0 = history.pop();
parent[e1[0]] = e1[0];
if (e0[1] == 1) rank[e0[0]]--;
}
}
关键取舍：不做路径压缩。路径压缩会改写 parent 链，让撤销变得不可能（你不知道原来的父指针是什么）。按秩合并的树高是 O(log n)，在网格规模（几十×几十）下完全够快。这是”可撤销并查集”的标准做法，也是 DFA 路径搜索里必须付出的代价。
五、主程序与示例题
package com.example.masyu;
public class Main {
// '.'=空白, 'W'=白珠, 'B'=黑珠
static final String[] PUZZLE = {
". . W . . W . ",
". . . . . . . ",
"B . . W . . . ",
". . . . B . . ",
". W . . . . W ",
". . . B . . . ",
". W . . . W . "
};
public static void main(String[] args) {
CellType[][] grid = new CellType[PUZZLE.length][];
for (int r = 0; r < PUZZLE.length; r++) {
String[] parts = PUZZLE[r].trim().split(" ");
grid[r] = new CellType[parts.length];
for (int c = 0; c < parts.length; c++) {
grid[r][c] = parts[c].equals("W") ? CellType.WHITE
: parts[c].equals("B") ? CellType.BLACK : CellType.EMPTY;
}
}
long t0 = System.nanoTime();
MasyuSolver solver = new MasyuSolver(grid);
solver.compileConstraints();
boolean ok = solver.solveFromAnywhere();
long t1 = System.nanoTime();
System.out.println("找到解 = " + ok);
System.out.printf("搜索节点 = %d, 耗时 = %.2f ms%n", solver.nodes, (t1 - t0) / 1e6);
if (ok) System.out.println(solver.render());
}
}
solveFromAnywhere 的逻辑是：从任一珠子出发，以珠子为起点枚举其两个离开方向（黑珠必须转弯、白珠必须直行），然后 search。从珠子出发的好处是：起点被天然限定了”必须进入回路”，避免了从空白格出发导致的大量无效尝试。
boolean solveFromAnywhere() {
// 找第一个珠子作为起点
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
if (grid[r][c] == CellType.EMPTY) continue;
// 对珠子，进入方向可以是任意 4 个方向，但离开方向由类型决定
for (int d = 0; d < 4; d++) {
int mask = exitMask(grid[r][c], d);
for (int out = 0; out < 4; out++) {
if ((mask & (1 << out)) == 0) continue;
int nr = r + DR[out], nc = c + DC[out];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
// 起始边
int a = id(r, c), b = id(nr, nc);
usedEdges.add(edgeKey(a, b));
deg[a]++; deg[b]++;
if (search(nr, nc, out, grid[r][c] == CellType.WHITE)) return true;
deg[a]--; deg[b]--;
usedEdges.remove(edgeKey(a, b));
}
}
return false; // 只从一个珠子出发即可（回路必然经过它）
}
return false;
}
六、复杂度与剪枝效果
理论复杂度。Masyu 是 NP 完全问题（可归约到哈密顿环问题）。分支因子：空白格 3（直行 + 两个转弯），白珠 1，黑珠 2。最坏情况是指数级。
实测表现。对 10×10 的中等难度题，朴素回溯需要 10^5~10^6 个节点，加上”珠子邻居约束编译”和”提前成环检测”后降到 10^3 量级。剪枝贡献度大致是：
| 优化 | 节点减少比例 |
|---|---|
| 珠子邻居约束编译 | ~40% |
| 度数 ≤ 2 检测 | ~35% |
| 提前成环检测（成环时校验珠子覆盖） | ~20% |
| 死角检测（剩余可用边 < 2） | ~10%（本文未实现） |
空间复杂度。deg、enterMask、dsu 都是 O(rows × cols)，usedEdges 最多 O(2 × rows × cols) 条边，递归深度最多等于回路长度 O(rows × cols)。10×10 题目内存占用 < 1 MB。
一个必须补的优化：死角检测。如果某个珠子格子的可连接边数已经少于”它需要的边数”（白珠需要 2、黑珠需要 2），立即失败。这条检测能砍掉大量”画到一半发现某珠子走不到”的搜索分支，实现只需在每步决策后检查相邻珠子。
七、DFA 建模的通用价值
把 Masyu 建模成 DFA，看似只是”换个说法”，但它带来的三个结构性好处值得单独提炼：
- 状态空间被显式限定。传统图搜索里，”下一步往哪走”是 3 个自由度；DFA 里变为”从当前状态出发的转移函数”，而转移函数是预先算好的常量表。这让分支因子从”格子数 × 3″降到”格子数 × 平均转移数”，且转移数完全由题目规则决定，与搜索过程无关。
- 约束可以离线编译。”白珠前后必须转弯”这类跨状态约束，编译成邻居掩码后变成 O(1) 的位运算。这等价于把”推理”提前到”预处理”，是逻辑谜题求解器普遍采用的加速策略。
- 正确性可局部验证。DFA 转移表的每一项都可以独立测试（给定珠子类型 + 进入方向 → 期望离开方向集合），这让代码的正确性验证从”整体猜”变成”逐项对”。
这套思路在更广的范围里都有对应：正则表达式的 Thompson 构造（把正则转成 NFA/DFA 再匹配）、词法分析器的 DFA 化、网络协议的有限状态机建模（TCP 状态转移表）、以及游戏 AI 里的行为树/状态机。当你发现问题的约束全是”局部模式”时，先试着把它压成一张转移表——这张表往往就是最高效的数据结构。
Masyu 还有一个迷人的特性：合格题目必须”有唯一解”。这要求出题器不仅要有求解器，还要用求解器验证”去掉这条约束后仍唯一”——也就是反复用 UNSAT 证明来保证唯一性。这正是 SAT 求解器在谜题生成领域的经典用法，也是本文与 SAT 建模（见数独那篇）可以互相印证的地方：DFA 建模适合”路径类”谜题，CNF 建模适合”赋值类”谜题，两者都依赖”把局部约束编译成高效判定”这同一个内核思想。
