多米诺骨牌是一种经典的双数字 tiles 游戏，每张骨牌由两个0-6的数字组成。游戏的核心玩法之一是”接龙”：将骨牌首尾相连形成最长的链，要求相邻骨牌接触端的数字相同。本文用 Java 实现多米诺骨牌的最长链求解系统，核心算法包括图论建模、欧拉路径判定、DFS 回溯搜索，以及动态规划优化。
一、问题建模：从骨牌到图
将每张骨牌 [a|b] 建模为图中的一条无向边，连接顶点 a 和 b。接龙问题转化为：
– 最长链问题：在多重图中寻找最长的路径（允许重复访问顶点，但不重复访问边）
– 完整环问题：判断是否存在欧拉回路（使用所有骨牌恰好一次的环）
– 完整链问题：判断是否存在欧拉路径（使用所有骨牌恰好一次的链）
对于 n 张骨牌，图有 7 个顶点（0-6），n 条边（允许重边和自环）。
二、核心算法
2.1 欧拉路径判定
无向图存在欧拉路径的充要条件：
– 图连通（忽略孤立点）
– 奇度顶点数为 0（欧拉回路）或 2（欧拉路径）
2.2 最长链搜索
当不存在欧拉路径时，需要寻找使用最多骨牌的路径。这是一个 NP-hard 问题（类似最长路径问题）。本文采用带剪枝的 DFS 回溯：
– 从每个顶点出发尝试所有未使用的边
– 记录当前最优解
– 剪枝：若剩余边数 + 当前链长 ≤ 最优解，则回溯
2.3 动态规划优化（小规模）
对于特定结构（如链状、树状），可用状态压缩 DP，但骨牌数量大时状态空间爆炸。
三、Java 完整实现
import java.util.*;
/**
* 多米诺骨牌最长链求解器
* 核心算法：图论建模 + DFS回溯 + 欧拉路径判定
*/
public class DominoSolver {
public static class Domino {
public final int a, b;
public final int id;
public Domino(int a, int b, int id) {
this.a = Math.min(a, b);
this.b = Math.max(a, b);
this.id = id;
}
public boolean hasNumber(int n) {
return a == n || b == n;
}
public int otherEnd(int n) {
return a == n ? b : a;
}
@Override
public String toString() {
return String.format("[%d|%d]", a, b);
}
}
private List<Domino> dominoes;
private int n;
private List<int[]> adj; // adj[v] = list of [neighbor, edgeId]
private boolean[] used;
private int bestLength;
private List<Domino> bestChain;
private List<Domino> currentChain;
public DominoSolver(List<Domino> dominoes) {
this.dominoes = dominoes;
this.n = dominoes.size();
this.adj = new ArrayList<>();
for (int i = 0; i < 7; i++) adj.add(new ArrayList<>());
for (Domino d : dominoes) {
adj.get(d.a).add(new int[]{d.b, d.id});
if (d.a != d.b) {
adj.get(d.b).add(new int[]{d.a, d.id});
}
}
this.used = new boolean[n];
this.currentChain = new ArrayList<>();
}
/**
* 欧拉路径判定：返回起始顶点，若不存在返回 -1
*/
public int eulerPathStart() {
int[] degree = new int[7];
for (Domino d : dominoes) {
degree[d.a]++;
if (d.a != d.b) degree[d.b]++;
}
// 检查连通性
boolean[] visited = new boolean[7];
int startVertex = -1;
for (int i = 0; i < 7; i++) {
if (degree[i] > 0) {
startVertex = i;
break;
}
}
if (startVertex == -1) return 0; // 空图
dfsConnectivity(startVertex, visited);
for (int i = 0; i < 7; i++) {
if (degree[i] > 0 && !visited[i]) return -1; // 不连通
}
// 统计奇度顶点
int oddCount = 0;
int oddVertex = startVertex;
for (int i = 0; i < 7; i++) {
if (degree[i] % 2 == 1) {
oddCount++;
oddVertex = i;
}
}
if (oddCount == 0 || oddCount == 2) {
return oddVertex;
}
return -1;
}
private void dfsConnectivity(int v, boolean[] visited) {
visited[v] = true;
for (int[] edge : adj.get(v)) {
int u = edge[0];
if (!visited[u]) dfsConnectivity(u, visited);
}
}
/**
* Hierholzer 算法求欧拉路径
*/
public List<Domino> findEulerPath(int start) {
List<Domino> path = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
Stack<Integer> edgeStack = new Stack<>();
boolean[] localUsed = new boolean[n];
stack.push(start);
while (!stack.isEmpty()) {
int v = stack.peek();
boolean found = false;
for (int[] edge : adj.get(v)) {
int u = edge[0];
int eid = edge[1];
if (!localUsed[eid]) {
localUsed[eid] = true;
edgeStack.push(eid);
stack.push(u);
found = true;
break;
}
}
if (!found) {
stack.pop();
if (!edgeStack.isEmpty()) {
int eid = edgeStack.pop();
path.add(dominoes.get(eid));
}
}
}
Collections.reverse(path);
return path;
}
/**
* DFS 回溯搜索最长链（带剪枝）
*/
public void findLongestChain() {
bestLength = 0;
bestChain = new ArrayList<>();
// 尝试从每个顶点出发
for (int start = 0; start < 7; start++) {
if (adj.get(start).isEmpty()) continue;
Arrays.fill(used, false);
currentChain.clear();
dfsLongest(start);
}
}
private void dfsLongest(int currentVertex) {
// 剪枝：剩余可能的最大长度
int remaining = 0;
for (boolean u : used) if (!u) remaining++;
if (currentChain.size() + remaining <= bestLength) return;
// 更新最优解
if (currentChain.size() > bestLength) {
bestLength = currentChain.size();
bestChain = new ArrayList<>(currentChain);
}
// 尝试所有未使用的邻接边
for (int[] edge : adj.get(currentVertex)) {
int nextVertex = edge[0];
int eid = edge[1];
if (used[eid]) continue;
used[eid] = true;
currentChain.add(dominoes.get(eid));
dfsLongest(nextVertex);
currentChain.remove(currentChain.size() - 1);
used[eid] = false;
}
}
/**
* 打印骨牌链
*/
public void printChain(List<Domino> chain) {
if (chain.isEmpty()) {
System.out.println("空链");
return;
}
StringBuilder sb = new StringBuilder();
int current = chain.get(0).a;
for (Domino d : chain) {
if (d.a == current) {
sb.append(d);
current = d.b;
} else {
sb.append("[").append(d.b).append("|").append(d.a).append("]");
current = d.a;
}
sb.append(" -> ");
}
sb.setLength(sb.length() - 4);
System.out.println(sb.toString());
System.out.println("长度: " + chain.size() + " 张骨牌");
}
/**
* 生成随机骨牌集合
*/
public static List<Domino> generateRandom(int count) {
List<Domino> list = new ArrayList<>();
Random rand = new Random();
for (int i = 0; i < count; i++) {
int a = rand.nextInt(7);
int b = rand.nextInt(7);
list.add(new Domino(a, b, i));
}
return list;
}
/**
* 生成标准双六骨牌全集合（28张）
*/
public static List<Domino> generateFullSet() {
List<Domino> list = new ArrayList<>();
int id = 0;
for (int i = 0; i <= 6; i++) {
for (int j = i; j <= 6; j++) {
list.add(new Domino(i, j, id++));
}
}
return list;
}
public static void main(String[] args) {
// 测试1：标准28张骨牌集合
System.out.println("=== 测试1：标准双六骨牌集合 ===");
List<Domino> fullSet = generateFullSet();
DominoSolver solver1 = new DominoSolver(fullSet);
int eulerStart = solver1.eulerPathStart();
if (eulerStart != -1) {
System.out.println("存在欧拉路径，起点: " + eulerStart);
List<Domino> eulerPath = solver1.findEulerPath(eulerStart);
solver1.printChain(eulerPath);
} else {
System.out.println("不存在欧拉路径，搜索最长链...");
solver1.findLongestChain();
solver1.printChain(solver1.bestChain);
}
// 测试2：随机骨牌集合
System.out.println("\n=== 测试2：随机15张骨牌 ===");
List<Domino> randomSet = generateRandom(15);
System.out.println("骨牌列表: " + randomSet);
DominoSolver solver2 = new DominoSolver(randomSet);
eulerStart = solver2.eulerPathStart();
if (eulerStart != -1) {
System.out.println("存在欧拉路径");
List<Domino> eulerPath = solver2.findEulerPath(eulerStart);
solver2.printChain(eulerPath);
} else {
System.out.println("搜索最长链...");
solver2.findLongestChain();
solver2.printChain(solver2.bestChain);
}
// 测试3：小规模精确解 vs 欧拉路径
System.out.println("\n=== 测试3：存在欧拉回路的构造数据 ===");
List<Domino> cycleSet = Arrays.asList(
new Domino(0, 1, 0), new Domino(1, 2, 1),
new Domino(2, 3, 2), new Domino(3, 0, 3)
);
DominoSolver solver3 = new DominoSolver(cycleSet);
eulerStart = solver3.eulerPathStart();
System.out.println("欧拉起点: " + eulerStart);
List<Domino> path = solver3.findEulerPath(eulerStart);
solver3.printChain(path);
}
}
四、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 欧拉路径判定 | O(V + E) | O(V + E) | 快速判定是否存在完整链 |
| Hierholzer | O(E) | O(E) | 求欧拉路径（存在时） |
| DFS回溯 | O(E!) 最坏 | O(E) | 最长链（精确解） |
| 带剪枝DFS | O(α^E), α < E | O(E) | 最长链（实践中大幅优化） |
其中 V=7（固定），E 为骨牌数。由于顶点数极少，DFS 剪枝效果极佳，对于 E ≤ 30 可秒级求解。
五、算法优化技巧
- 重边优先：在 DFS 中优先尝试连接更多未使用边的顶点，增加找到长链的概率
- 双向搜索：从两端同时扩展链，在中间汇合
- 度数启发：优先从奇度顶点出发（若存在），因为欧拉路径必然从奇度顶点开始
- 连通分量分解：若图不连通，在各连通分量分别求最长链后拼接
六、扩展应用
多米诺骨牌的图论建模思想可推广至：
– DNA 序列拼接：将 reads 建模为 de Bruijn 图的边，寻找覆盖所有 reads 的最短超串
– 旅行商问题（TSP）变体：在特定图结构下的路径优化
– 电路板走线：寻找连接所有焊点的最短路径
– 笔画问题：判断汉字能否一笔写成（欧拉路径应用）
