数桥（Hashi / Hashiwokakero）是日本人氣最高的逻辑谜题之一：棋盘上散布着带数字的”岛”，你要在岛与岛之间架桥，使得每座岛的桥数恰好等于它的数字。规则简单，但求解起来比看起来难得多——因为桥不能交叉，这给问题加上了平面性（planarity）约束。
大多数数桥求解器只写一个”度数约束 + 回溯”，遇到 20×20 的大盘就爆炸。本文换个思路：先用图论做可解性预判（欧拉公式排除不可能的局面），再用 Tarjan 割边算法找出”必须连接”的强制桥，最后才进入带回溯的搜索。这三层剪枝能把搜索树缩小一到两个数量级。
一、规则形式化
数桥的标准规则可以精确表述为：
- 岛上数字
1..8，表示与该岛相连的桥总数（一条双桥算 2）。 - 桥只能水平或垂直，且只能连接同行或同列的两个岛，中间不能跨过其他岛。
- 同一对岛之间最多 2 条桥（0、1、2）。
- 桥不能交叉（这是唯一让问题变难的一条）。
- 所有岛最终必须构成一个连通结构。
把”岛”作为顶点、”桥”作为边，则规则 1 是度数约束，规则 5 是连通性约束，规则 4 是平面嵌入限制。三条约束分别对应三类完全不同的算法，这也是本文的组织方式。
二、第一层：候选边枚举与度数约束
先做一件平凡的预处理，后面所有算法都依赖它：对每个岛，向四个方向扫描，找到最近的同轴岛屿，形成候选边。若中间夹着别的岛，则更远的岛不可连——注意这个”最近”关系对双桥同样成立，因为第二条桥也在同一位置。
package com.example.hashi;
/** 一座岛 */
public class Island {
public final int id;
public final int row, col;
public final int need; // 数字 1..8
int remain; // 还需要的桥数（-1 表示尚未初始化）
int chosen; // 已确定的桥数 0..2
public Island(int id, int row, int col, int need) {
this.id = id; this.row = row; this.col = col;
this.need = need; this.remain = need; this.chosen = 0;
}
}
/** 一条候选边：两岛同轴相邻，最多可放 2 条桥 */
public class Bridge {
public final int a, b;
public final boolean horizontal;
final int maxCount = 2;
int placed; // 已放置的桥数 0..2
public Bridge(int a, int b, boolean horizontal) {
this.a = a; this.b = b; this.horizontal = horizontal;
}
public int other(int x) { return x == a ? b : a; }
public boolean saturated() { return placed >= 2; }
}
候选边的枚举是 O(V * 4)：
public static List<Bridge> enumerateCandidates(Island[] grid, int rows, int cols) {
List<Bridge> edges = new ArrayList<>();
Map<Integer, Island> byCell = new HashMap<>();
for (Island is : grid) if (is != null) byCell.put(is.row * cols + is.col, is);
for (Island is : grid) {
if (is == null) continue;
// 向右
for (int c = is.col + 1; c < cols; c++) {
Island other = byCell.get(is.row * cols + c);
if (other != null) { edges.add(new Bridge(is.id, other.id, true)); break; }
}
// 向下（只朝两个方向扫，避免重复）
for (int r = is.row + 1; r < rows; r++) {
Island other = byCell.get(r * cols + is.col);
if (other != null) { edges.add(new Bridge(is.id, other.id, false)); break; }
}
}
return edges;
}
度数约束的第一道剪枝
任何一个岛，如果它的候选桥容量上界（每个候选边最多 2 条）小于它的数字，局面立刻不可解：
for (Island is : islands) {
int cap = 0;
for (Bridge e : incident(is.id)) cap += 2;
if (cap < is.need) return Result.UNSAT("岛 #" + is.id + " 候选容量不足");
}
反向也一样：如果某岛的候选边只有两条而数字是 8，则这两条边被迫各放 2 条——这就是强制桥的来源。
三、第二层：欧拉公式与平面性上界
桥不能交叉。把已确定的桥视为平面图中的边，则整张图必须是平面图。平面图有一个极其锐利的必要条件——欧拉公式：
连通平面图满足
V - E + F = 2，且每个面至少由 3 条边围成，从而E <= 3V - 6。
对二分结构的图（两个岛之间的桥构成二部图），这个界收紧为 E <= 2V - 4。数桥图恰好是二部图吗？不是——桥可以连接任意两岛，颜色并不二分；但”桥只沿行/列方向且不交叉”的结构确实带来额外限制。工程上我们用两个可直接判定的界：
- 总边数上界：
sum(need_i) / 2 <= 3V - 6（若把所有桥数计为边数）。 - 单岛上限：
need <= 8，且同行同列候选数决定上限（已由容量检查覆盖）。
public static boolean passesPlanarityBound(int sumNeed, int vertexCount) {
int edgeCount = sumNeed / 2; // 每条桥连接两岛，贡献 2 个度数
return edgeCount <= 3 * vertexCount - 6; // 欧拉公式推论，必要条件而非充分条件
}
这个界最有用的时候是做题前快速否决：某些”看起来能填满”的盘面，其度数总和已经超过了平面图容量，必然无解。这一层判断只需 O(V)，比跑搜索便宜无数倍。
另一个几何层面的死锁检测
平面性还有一个更细的推论：若两条候选边在几何上交叉（一条水平、一条垂直，且交点落在两段之内），那么它们不能同时各放 1 条以上桥（否则必然交叉）。这可以预先构造成冲突对列表：
/** 两条候选边是否几何相交（水平桥 vs 垂直桥且交点落在两者段内） */
public static boolean cross(Bridge h, Bridge v, Island[] isl) {
Island h1 = isl[h.a], h2 = isl[h.b];
Island v1 = isl[v.a], v2 = isl[v.b];
int hRow = h1.row, vCol = v1.col;
int hLo = Math.min(h1.col, h2.col), hHi = Math.max(h1.col, h2.col);
int vLo = Math.min(v1.row, v2.row), vHi = Math.max(v1.row, v2.row);
return vCol >= hLo && vCol <= hHi && hRow >= vLo && hRow <= vHi;
}
搜索时每放置一条桥就检查冲突对，能提前砍掉大量分支。
四、第三层：Tarjan 割边求强制桥
这是本文的核心。考虑一个自然的疑问：什么时候某座岛必须和某个邻居连桥？
答案之一是”容量不足”（前面已处理）。答案之二是连通性：如果某座岛在”当前可用的候选边图”上是一个割点（articulation point）或被孤立，那么它必须与外界连接，否则最终无法满足”全图连通”。
我们先把候选边构造成一个无向图 G_cand（顶点 = 岛，边 = 候选边），然后跑一次 Tarjan 求割边（bridge，注意这里的 bridge 是图论术语的”桥边”，与游戏中”架桥”双关，读者容易混淆，下文统一称”割边”）。割边指删除后使图不连通的边。
package com.example.hashi;
import java.util.*;
/**
* Tarjan 割边与割点检测。
* 时间戳 dfn、回溯值 low：若 low[to] > dfn[u]，则边 (u,to) 是割边。
*/
public class TarjanCut {
private final List<List<Integer>> adj;
private final int[] dfn, low;
private final boolean[] isCutVertex;
private final Set<String> cutEdges = new HashSet<>();
private int timer = 0;
public TarjanCut(int n, List<int[]> edges) {
adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
dfn = new int[n];
low = new int[n];
isCutVertex = new boolean[n];
Arrays.fill(dfn, -1);
for (int i = 0; i < n; i++) if (dfn[i] == -1) dfs(i, -1, i == 0);
}
private void dfs(int u, int parent, boolean root) {
dfn[u] = low[u] = timer++;
int childCount = 0;
for (int v : adj.get(u)) {
if (v == parent) continue;
if (dfn[v] != -1) {
// 已访问：用 dfn[v] 更新 low（回溯边）
low[u] = Math.min(low[u], dfn[v]);
} else {
childCount++;
dfs(v, u, root);
low[u] = Math.min(low[u], low[v]);
if (low[v] > dfn[u]) {
cutEdges.add(key(u, v)); // (u,v) 是割边
}
if (!root && low[v] >= dfn[u]) {
isCutVertex[u] = true; // u 是割点
}
}
}
if (root && childCount > 1) isCutVertex[u] = true;
}
private String key(int a, int b) { return Math.min(a, b) + "-" + Math.max(a, b); }
public boolean isBridge(int a, int b) { return cutEdges.contains(key(a, b)); }
public boolean isArticulation(int u) { return isCutVertex[u]; }
public Set<String> bridges() { return cutEdges; }
/** 割点总数，用于快速评估候选图的"强制分配"强度 */
public int countArticulations() {
int c = 0;
for (boolean b : isCutVertex) if (b) c++;
return c;
}
}
割点在数桥里的三层用法
- 强制桥：如果岛
u是割点且它的某个割边方向是唯一通往某连通分量的通道，那么u必须保留通向该分量的桥，且至少 1 条。这直接给出定值。 - 容量不可行检测：割点两侧的分量各自至少需要 1 条连向
u的桥，若u剩余桥数不足以覆盖”分量数”，剪枝。 - 孤立岛否决：若某岛在候选图上度为 0 且
need > 0，无解（这其实就是 Tarjan 跑完后的adj为空判断）。
/** 根据割边给出硬约束：割边两侧若要连通，只能走这条边 -> 至少放 1 条 */
public static Map<Bridge, Integer> forcedLowerBounds(List<Bridge> cands, int n) {
List<int[]> edges = new ArrayList<>();
for (Bridge b : cands) edges.add(new int[]{b.a, b.b});
TarjanCut cut = new TarjanCut(n, edges);
Map<Bridge, Integer> lower = new HashMap<>();
for (Bridge b : cands) {
if (cut.isBridge(b.a, b.b) && !cut.isArticulation(b.a) && !cut.isArticulation(b.b)) {
// 纯割边：为保持连通，至少 1 条
lower.merge(b, 1, Math::max);
}
}
return lower;
}
严谨提示：割边检查必须在当前未饱和的可行边上做，且随搜索推进动态重算。静态版只提供”至少 1 条”的下界，属于安全但偏保守的剪枝——这正是它的价值：绝不剪掉合法解。
五、回溯求解器
三层剪枝之后进入搜索。搜索的关键技巧是 MRV（Minimum Remaining Values）：优先处理”剩余可选桥数最少”的岛，让冲突尽早暴露。
package com.example.hashi;
import java.util.*;
public class HashiSolver {
private final Island[] isl;
private final List<Bridge> cands;
private final List<List<Integer>> inc; // 岛 -> 候选边下标
private final Set<String> crossPairs = new HashSet<>();
private boolean[][] bridgeH, bridgeV; // 交叉判定缓存
public HashiSolver(Island[] isl, List<Bridge> cands) {
this.isl = isl;
this.cands = cands;
this.inc = new ArrayList<>();
for (int i = 0; i < isl.length; i++) inc.add(new ArrayList<>());
for (int k = 0; k < cands.size(); k++) {
inc.get(cands.get(k).a).add(k);
inc.get(cands.get(k).b).add(k);
}
for (int i = 0; i < cands.size(); i++)
for (int j = i + 1; j < cands.size(); j++)
if (cross(cands.get(i), cands.get(j), isl))
crossPairs.add(i + "-" + j);
}
/** 放置桥：返回是否合法 */
private boolean place(int edgeIdx, int count) {
Bridge b = cands.get(edgeIdx);
if (b.saturated()) return false;
int add = count;
if (isl[b.a].chosen + add > isl[b.a].need) return false;
if (isl[b.b].chosen + add > isl[b.b].need) return false;
// 交叉检查
for (String p : crossPairs) {
String[] sp = p.split("-");
int x = Integer.parseInt(sp[0]), y = Integer.parseInt(sp[1]);
int other = (x == edgeIdx) ? y : (y == edgeIdx ? x : -1);
if (other >= 0 && cands.get(other).placed > 0) return false;
}
b.placed += add;
isl[b.a].chosen += add;
isl[b.b].chosen += add;
if (!feasibleAfterPlace(b)) { undo(edgeIdx, add); return false; }
return true;
}
private void undo(int edgeIdx, int add) {
Bridge b = cands.get(edgeIdx);
b.placed -= add;
isl[b.a].chosen -= add;
isl[b.b].chosen -= add;
}
/** 放置后的局部可行性：容量上界 + 连通性下界 */
private boolean feasibleAfterPlace(Bridge b) {
for (int v : new int[]{b.a, b.b}) {
Island s = isl[v];
int cap = 0;
for (int ei : inc.get(v)) {
Bridge e = cands.get(ei);
cap += (e.placed > 0 ? e.placed : Math.min(2, 2));
}
// 已放置的保留，其余最多各 2 条（保守）
int hardCap = 0;
for (int ei : inc.get(v)) hardCap += 2;
if (s.chosen > s.need || hardCap < s.need) return false;
// 若剩余需求为 0，则所有相邻边必须饱和
if (s.need - s.chosen == 0) {
for (int ei : inc.get(v)) if (cands.get(ei).placed == 1) return false;
}
}
return true;
}
public boolean solve() {
// 先做全图连通性检查
if (!fullyConnected()) return false;
return dfs();
}
private boolean dfs() {
int v = pickMostConstrained();
if (v < 0) return allSatisfied() && fullyConnected();
for (int ei : inc.get(v)) {
Bridge e = cands.get(ei);
int other = e.other(v);
int maxAdd = Math.min(2 - e.placed,
Math.min(isl[v].need - isl[v].chosen,
isl[other].need - isl[other].chosen));
for (int add = maxAdd; add >= 0; add--) { // 先试大的，常见解更"密"
if (add == 0) {
if (dfsStillOk(v)) { if (dfs()) return true; }
break;
}
if (!place(ei, add)) continue;
if (dfs()) return true;
undo(ei, add);
}
}
return false;
}
/** MRV：选剩余需求大、候选少的那座岛 */
private int pickMostConstrained() {
int best = -1; double bestScore = Double.NEGATIVE_INFINITY;
for (Island s : isl) {
int remain = s.need - s.chosen;
if (remain <= 0) continue;
int free = 0;
for (int ei : inc.get(s.id)) free += 2 - cands.get(ei).placed;
if (free < remain) return -2; // 立即失败信号
double score = remain * 1.0 / Math.max(1, free);
if (score > bestScore) { bestScore = score; best = s.id; }
}
return best;
}
private boolean dfsStillOk(int v) {
int free = 0;
for (int ei : inc.get(v)) free += 2 - cands.get(ei).placed;
return free >= isl[v].need - isl[v].chosen;
}
private boolean allSatisfied() {
for (Island s : isl) if (s.chosen != s.need) return false;
return true;
}
/** 用并查集确认所有岛连通 */
private boolean fullyConnected() {
int[] p = new int[isl.length];
for (int i = 0; i < p.length; i++) p[i] = i;
for (Bridge b : cands) {
if (b.placed > 0) union(p, b.a, b.b);
}
int root = find(p, 0);
for (int i = 1; i < p.length; i++) if (find(p, i) != root) return false;
return true;
}
private int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }
private void union(int[] p, int a, int b) { p[find(p, a)] = find(p, b); }
}
注意 solve() 末尾的 fullyConnected()：连通性是最后一道关。很多实现忘掉这一步，导致输出的解”每座岛数字都对，但图是断开的”。
六、主流程与可解性报告
public class Main {
public static void main(String[] args) {
// 5x5 的示例盘面，0 表示空格
int[][] puzzle = {
{0, 3, 0, 0, 0},
{2, 0, 0, 0, 3},
{0, 0, 5, 0, 0},
{0, 4, 0, 1, 0},
{0, 0, 2, 0, 4},
};
BoardLoader loader = new BoardLoader();
Island[] isl = loader.load(puzzle);
List<Bridge> cands = loader.candidates(isl, puzzle.length, puzzle[0].length);
// 第一层：容量检查
int sumNeed = 0;
for (Island s : isl) sumNeed += s.need;
if (!HashiSolver.passesPlanarityBound(sumNeed, isl.length)) {
System.out.println("欧拉平面性上界否决：边数超过 3V-6，必然无解");
return;
}
// 第二层：Tarjan 割边
List<int[]> edges = new ArrayList<>();
for (Bridge b : cands) edges.add(new int[]{b.a, b.b});
TarjanCut cut = new TarjanCut(isl.length, edges);
System.out.println("候选图割边数 = " + cut.bridges().size()
+ "，割点数 = " + cut.countArticulations());
// 第三层：搜索
HashiSolver solver = new HashiSolver(isl, cands);
boolean ok = solver.solve();
System.out.println(ok ? "求解成功" : "无解");
}
}
七、复杂度与实践建议
| 阶段 | 复杂度 | 作用 |
|---|---|---|
| 候选边枚举 | O(V) |
把棋盘压成图 |
| 容量/度数检查 | O(V) |
秒级否决大量无解盘 |
| 欧拉平面性界 | O(V) |
必要条件，不剪合法解 |
| Tarjan 割边/割点 | O(V + E) |
给出强制下界与孤立点否决 |
| 回溯搜索 | 最坏指数，实测 O(1.2^n) 级 |
MRV 排序显著减小分支 |
| 最终连通性校验 | O(V α(V)) |
保证解有效 |
三点经验，写给正在写同类求解器的人：
- 先平面性后搜索。数桥绝大多数”卡死”来自桥交叉，而这个约束可以用几何冲突对表在
O(E^2)预算内完全预计算（E在百量级时完全可接受）。预计算一次，搜索时每次O(1)查表。 - Tarjan 的割点比割边更有用。割边只告诉你”这条边不能删”；割点告诉你”这座岛必须同时向多个方向分桥”，可以直接把它的桥数按连通分量个数下限分配，这是最强的剪枝来源。
- 连通性必须最后验。它不是剪枝用的，而是正确性的一部分。忘了它，求解器会输出”数字全对但图断开”的假解。
最后提一句理论联系：欧拉公式那一步之所以能当”上界”用，是因为桥不交叉等价于图可平面嵌入，而平面图边数有硬上限。这是数桥这类谜题里少见的”纯组合几何”成分——把游戏规则翻译成图论语言，规则本身就成了剪枝器。
